非常完整的排序算法加练习题

排序算法

何衍泓

所有的排序测试的头文件 0.sort_test.h

#pragma once#include#include#define SMALL_DATA_N 5000#define BIG_DATA_N 1000000void __init_Rand__(){printf("init rand\n");}bool check(int* arr, int l, int r){for (int i = l + 1; i  
选择排序(selection_sort)
 

• 将数组分成“已排序区”和“待排序区”
• 每一轮在“待排序区”选择一个最小值放入“已排序区”
• 直到“待排序区”没有元素为止

  #define _CRT_SECURE_NO_WARNINGS 1#include#include#include#include"0.sort_test.h"#include#include#include//每次在待排序区中选择一个最小值放到已排序区的最后void selection_sort(int* arr, int l, int r){for (int i = l; i  
  正常版本的插入排序(insert_sort)
   

  • 将待排序区的第一个值与前面已排序区一个一个往前插队
  • 直到遇到比自己还小的就停止插队

    #define _CRT_SECURE_NO_WARNINGS 1#include#include#include#include"0.sort_test.h"#include#include#include//每次在将当前值向前插队void insert_sort(int* arr, int l, int r){for (int i = l + 1; i  l && arr[j]  
    无监督插入排序(unguarded_insert_sort)
     

    • 无监督版本主要是通过先把最小值放到前面来减少 j > l 的判断

      void unguarded_insert_sort(int* arr, int l, int r){int ind = l;for (int i = l + 1; i  arr[i]) ind = i;}while (ind > l)//为了插入算法的稳定性，一个一个向前交换{swap(arr[ind], arr[ind - 1]);ind--;}for (int i = l + 1; i  
      希尔排序(shell_sort)
       

      • 分组插入排序
      • 首先设置一个合适的步长序列，有希尔序列和hibbard序列
      • 希尔排序没有固定的时间复杂度，他的时间复杂度和步长序列有关
      • 按照步长对每个分组进行无监督插入排序
      • 直到执行到步长为 1 为止

        #define _CRT_SECURE_NO_WARNINGS 1#include#include#include#include"0.sort_test.h"#include#include#include//分组插入排序（希尔排序）void unguarded_insert_sort(int* arr, int l, int r, int step){int ind = l;for (int i = l + step; i  arr[i]) ind = i;}while (ind > l){swap(arr[ind], arr[ind - step]);ind -= step;}for (int i = l + 2 * step; i  
        冒泡排序(bubble_sort)
         

        • 外层循环 i 代表当前轮需要将待排序区的最大值放到 i 位置
        • 内层遍历待排序区，一个一个交换，将待排序区的最大值交换到 i 位置（稳定排序）
        • 优化：若遍历的时候没有发生任何一次交换则说明有序了，这个时候直接 break 即可

          #define _CRT_SECURE_NO_WARNINGS 1#include#include#include#include"0.sort_test.h"#include#include#includeusing namespace std;void bubble_sort(int* arr, int l, int r){for (int i = r - 1, cnt; i >= l + 1; i--)//执行 (n - 1) 轮{cnt = 0;for (int j = l; j  arr[j + 1]){swap(arr[j], arr[j + 1]);cnt = 1;}}if (cnt == 0) break;}return;}int main(){int* arr = getRandData(SMALL_DATA_N);TEST(bubble_sort, arr, SMALL_DATA_N);free(arr);return 0;}

          快速排序(quick_sort)

          • 首先在待排序区域找到一个基准值
          • 按照基准值大小分成两个区域
          • 递归对两个区域排序

            #define _CRT_SECURE_NO_WARNINGS 1#include#include#include#include"0.sort_test.h"//选择第一个作为基准值,并且一个一个交换来分区void quick_sort(int* arr, int l, int r){if (r - l val);            r = max(r,p->val);            p = p->next;        }        if(l == r) return head;        //注意不要向0取整，要向下取整（避免负数出现导致***循环）        int mid = (l + r)>> 1;        //使用链表头插法        ListNode *h1 = nullptr ,*h2 = nullptr,*q;        p = head;        while(p)        {            q = p->next;            if(p->valnext = h1;                h1 = p;            }else{                p->next = h2;                h2 = p;            }            p = q;        }        h1 = sortList(h1);        h2 = sortList(h2);        p = h1;        while(p->next) p = p->next;        p->next = h2;        return h1;    }};

            方法三：归并排序

            • 分治将链表对半切开
            • 可以利用虚拟头结点将两个链表串起来
            • 最后返回虚拟头结点的下一位即可

              /** * Definition for singly-linked list. * struct ListNode { *     int val; *     ListNode *next; *     ListNode() : val(0), next(nullptr) {} *     ListNode(int x) : val(x), next(nullptr) {} *     ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */class Solution {public:    ListNode* merge_sort(ListNode* head,int n)    {        if(n next;        p->next = nullptr;        p = merge_sort(head,l);        q = merge_sort(q,r);        ListNode ret;        ListNode *new_head = &ret;        while(p || q)        {            if(q == nullptr || (p && p->valval)){                new_head->next = p;                new_head = p;                p = p->next;            }else{                new_head->next = q;                new_head = q;                q = q->next;            }        }        return ret.next;    }    ListNode* sortList(ListNode* head) {        if(head == nullptr || head->next == nullptr) return head;        int n = 0;        ListNode* p = head;        while(p)         {            n++;            p = p->next;        }        return merge_sort(head,n);    }};

              合并两个有序数组

              https://leetcode.cn/problems/merge-sorted-array/description/

              方法一：开辟一个额外数组

              • 开辟一个temp数组
              • 将 nums1 的数据放到 temp 里面
              • 归并排序到 nums1 中即可

                class Solution {public:    void merge(vector& nums1, int m, vector& nums2, int n) {        if(n == 0) return ;        vector temp;        for(int i=0;ivalval)){                p->next = list1;                p = list1;                list1 = list1->next;            }else{                p->next = list2;                p = list2;                list2 = list2->next;            }        }        return ret.next;    }};

                两个正序数组的中位数

                https://leetcode.cn/problems/median-of-two-sorted-arrays/description/

                • 先合并成一个正序数组
                • 然后再在里面找到中位数即可

                  class Solution {public:    double findMedianSortedArrays(vector& nums1, vector& nums2) {        int n1 = nums1.size(),n2 = nums2.size();        double ans = 0.0;        vector temp;        int p1 = 0,p2 = 0;        while(p1