10大常见的排序方法比较

1.分类

• 比较类排序 ：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破$O(n\log n)O(n\backslash log\; \{n\})$O(nlogn)，因此也称为非线性时间比较类排序。
• 非比较类排序 ：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此也称为线性时间非比较类排序。

性能对比

代码实现

1. 冒泡排序

每一趟冒泡，将相邻两个数中最大或最小的放到后面，则一趟结束最大/小的就放到了最后。优化：记录本次第一次交换的位置，下一趟只需要从该位置向后做冒泡即可，最好的时间复杂度为O(n)。

2. 归并排序 Merge Sort

1. 递归实现

void MergeSort(int *arr, int begin, int end)
{
    if(begin == end) {
        return;
    }else {
        int temp[end-begin+1];
        MergeSort(arr, begin, (begin + end)/2);
        MergeSort(arr, (begin + end)/2+1, end);
        
        int i,j,n;
        for(i=begin, j = (begin + end)/2+1,n=0; i<=(begin + end)/2 && j<=end;n++){
            temp[n] = (arr[i] <= arr[j])?arr[i++]:arr[j++];
        }
        while(i<=(begin + end)/2) temp[n++] = arr[i++];
        while(j<=end) temp[n++] = arr[j++];

        memcpy(arr+begin, temp, sizeof(temp));
        /*
        for(i = 0; i < end-begin+1; i++){
            arr[begin+i] = temp[i];
        }
        */
    }
}

2. 非递归实现：自底向上，两两合并

void MergeSort(int *arr, int begin, int end)
{
    int len = end-begin+1;
    int *temp = (int *)calloc(len, sizeof(int));
    int seg, merge;
    for(seg = 1; seg < len; seg <<= 1){		//依次将长度为1、2、4、8...的组两兩合并
        for(merge = 0; merge < len; merge += 2*seg){
            int begin1 = merge, end1 = (begin1 + seg -1 <= end)?begin1 + seg -1 : end;
            int begin2 = (end1+1 <= end)?end1+1 : end, end2 = (merge + 2*seg -1 <= end)?merge + 2*seg -1 : end; 
            int i,j,n;
            for(i=begin1, j=begin2, n=begin1; end1!=end && i<=end1 && j<=end2;n++){
                temp[n] = (arr[i] <= arr[j])?arr[i++]:arr[j++];
            }
            while(i<=end1) temp[n++] = arr[i++];
            while(j<=end2 && end1!=end) temp[n++] = arr[j++];

            memcpy(arr+begin1, temp+begin1, sizeof(int)*(end2-begin1+1));
            // for(i = 0; i < end2-begin1+1; i++){
            //     arr[begin1+i] = temp[begin1+i];
            // }
        }
    }

    free(temp);
}

3. 应用：逆序对数量

int anti_order(int *arr, int begin, int end)
{
    // 使用归并排序统计数组中逆序对(0<=i<j<len, arr[i]>arr[j])的数量
    int result=0;
    if(begin >= end) result=0;
    else{
        result += anti_order(arr, begin, (begin+end)/2);
        result += anti_order(arr, (begin+end)/2+1, end);
        int len = end-begin+1;
        int temp_arr[len], i, j, k;
        for(i=begin, j=(begin+end)/2+1, k=0; i<=(begin+end)/2 && j<=end && k<len; k++){
            result += (arr[i]<=arr[j])?0:(begin+end)/2-i+1;
            temp_arr[k] = (arr[i]<=arr[j])?arr[i++]:arr[j++];
        }
        while(i<=(begin+end)/2) temp_arr[k++] = arr[i++];
        while(j<=end) temp_arr[k++] = arr[j++];
        memcpy(arr+begin, temp_arr, sizeof(temp_arr));
    }
    return result;
}

3. 快排 Quick Sort

C++ algorithm提供了sor函数，其中第一个参数为排序第一个元素地址，第二个参数为最后一个元素的下一个地址，最后一个参数可选，没有时默认升序排序，也可以自定义函数，然后传入函数指针（即函数名）。

#include <algorithm>
sort(first_pointer,first_pointer+n,cmp)；
bool cmp(int a,int b)
{
    return a<b; //升序排列，如果改为return a>b，则为降序
}

1. 代码实现

//升序
void quick_sort(int *arr, int begin, int end)
{
    if(begin>=end) return;
    int left=begin, right=end;
    int base=arr[end];			//选择哨兵
    while(left<right){
        while(arr[left]<=base && left<right) ++left;	//找到左边第一个大于base的
        if(left < right) arr[right--] = arr[left];
        while(arr[right]>=base && left<right) --right;	//找到右边第一个小于base的
        if(left < right) arr[left++] = arr[right];
    }
    arr[left] = base;

    quick_sort(arr, begin, left-1);
    quick_sort(arr, left+1, end);
}

2. 应用：查询第k大/小的数

int k_big(int *arr, int n, int begin, int end)
{
    // 求数组中第k大的元素
    if(begin >= end) return arr[end];
    int result;
    int left=begin, right=end,base=arr[end];
    while(left<right){
        while(arr[left]>=base && left<right) ++left;
        if(left<right) arr[right--] = arr[left];
        while(arr[right]<=base && left<right) --right;
        if(left<right) arr[left++] = arr[right];
    }
    arr[left] = base;
    if(left+1 == n) result = arr[left];
    else if(left+1 > n) result = k_big(arr, n, begin, left-1);
    else if(left+1 < n) result = k_big(arr, n, left+1, end);
    return result;
}

3. 快排的优化

思想：优化哨兵的选择，尽可能选择数组的中位数。如每5个为一组，找到各组中位数，然后选出这些中位数的中位数作为哨兵。

4. 堆排序 Heap Sort

1. 代码实现

//大顶堆
void heap_shift_up(int *arr, int k)
{
    // 对第k个元素做上浮处理——插入元素/构建堆
    // 时间复杂度O(log_n)
    while (k>1 && arr[k] > arr[k>>1])
    {
        int temp = arr[k>>1];
        arr[k>>1] = arr[k];
        arr[k] = temp;
        k >>= 1;
    }
}
void heap_shift_down(int *arr, int len, int k)
{
    // 对第k个元素做下沉处理——删除元素/按序输出
    // 时间复杂度O(log_n)
    while ((2*k<=len && arr[k]<arr[2*k]) || (2*k+1<=len && arr[k]<arr[2*k+1]))
    {
        int max_child_id;
        if(2*k+1>len) max_child_id = 2*k;
        else max_child_id = (arr[2*k]>=arr[2*k+1]) ? 2*k : 2*k+1;

        int temp = arr[k];
        arr[k] = arr[max_child_id];
        arr[max_child_id] = temp;

        k = max_child_id;
    }
}
void heap_sort(int *arr, int len)
{
    while(len>1){	//每次将堆顶元素和末尾交换，然后维护堆
        int temp = arr[1];
        arr[1] = arr[len];
        arr[len] = temp;
        --len;
        heap_shift_down(arr, len, 1);
    }
}

5. 插入排序 Insertion Sort

从原数组中依次取出元素，插入到已经排好序的数组中。只有当插入元素优先级大于数组尾部元素时向前插入，所以是稳定排序。

最好时：原数组有序，时间复杂度为$O\left(n\right)O(n)$O(n)

最坏时：原数组逆序，时间复杂度为$O\left(n^2\right)O(n^\{2\})$O(n2)

空间复杂度$O\left(1\right)O(1)$O(1)

6. 希尔排序（缩小增量排序）Shell Sort

插入排序的改进。

算法流程：

1. 选择一个增量序列t1、t2...tk=1
2. 进行k轮排序
3. 每轮排序按增量ti，间隔为ti的数为一组（索引%ti相同），一组内做插入排序。

7. 选择排序 Selection Sort

每次选择最大/小的元素放到数组头部有序部分的末尾，可以直接和无序部分第一个元素交换。不稳定排序

每次选择的时间为$O\left(n\right)O(n)$O(n)，选择$nn$n次，时间复杂度为$O\left(n^2\right)O(n^\{2\})$O(n2)

8. 计数排序 Counting Sort

条件：输入数据是有确定范围的整数。

算法：设一个计数数组C，将值为i的数出现的次数记录在C[i]中，然后根据C依次输出。

9. 桶排序 Bin/Bucket Sort

对计数排序的改进。

算法：将输入数据的范围[min, max]区间等分成n份，每份长度为d，每一份分配一个桶，则第i个桶的区间为[min+d*(i-1), min+d*i]。将数据分配到对应区间的桶中，然后对每个桶内进行排序。最后按序将各个桶中数据输出即可。

10. 基数排序 Radix Sort

先按低位排序（如十进制的个位），然后按排序后的顺序合并；然后按高位排序（如十位、百位），在合并。

引用内容 https://www.cnblogs.com/onepixel/articles/7674659.html