排序大法

1、基本概念

• 排序，就是重新排列表中的元素，使得表中的元素按照关键字有序的过程。
• 算法稳定性：如果两个元素关键字相同，排完序后在表中位置先后顺序和排序前一样，则称其排序为稳定的。

2、分类

内部排序

• 插入排序

  • 直接插入排序

    时间复杂度：最好：$O(n)$，最坏：$O(n^2)$，平均：$O(n^2)$

    空间复杂度：$O(1)$

    稳定排序，适用线性表和链式表

  • 折半插入排序

    时间复杂度：最坏：$O(n^2)$，平均：$O(n^2)$

    空间复杂度：$O(1)$

    稳定排序

  • 希尔排序

    时间复杂度：最坏：$O(n^2)$，平均：$O(n^{1.3})$（现代数学没法证明）

    空间复杂度：$O(1)$

    不稳定排序，只适用于线性表

class Solution {
public:

    vector<int> sortArray(vector<int>& nums) {
        for(int d = nums.size() / 2; d >= 1 ; d/=2){
            for(int m = 0; m < d; m++){
                for(int i = m+d; i < nums.size(); i+=d){
                    int j = i-d;
                    int temp = nums[i];
                    for(; j >= 0 && nums[j] > temp;j-=d){
                        nums[j+d]= nums[j];
                    }
                    nums[j+d] = temp;
                }
            }
        }
        return nums;
    }
};

• 交换排序

  • 冒泡排序

    时间复杂度：最好：$O(n)$，最坏：$O(n^2)$，平均：$O(n^2)$

    空间复杂度：$O(1)$

    稳定排序：适用于线性表和链式表

    • 快速排序

      时间复杂度：最坏：$O(n^2)$，平均：$O(nlog_2n)$

      空间复杂度：最好：$O(log_2n)$，最坏：$O(n)$，平均：$O(log_2n)$

      不稳定排序

class Solution {
public:
    int quick(vector<int> &nums, int left, int right){
        swap(nums[left], nums[rand()%(right-left+1)+left]);
        int pivot = nums[left];
        while(left < right){
            while(left <right && nums[right] > pivot) right--;
            nums[left] = nums[right];
            if(left < right && nums[left] == pivot) left++;
            while(left < right && nums[left] < pivot) left++;
            nums[right] = nums[left];
            if(left < right && nums[right] == pivot) right--;
        }
        nums[left] = pivot;
        return left;
    }

    void quickSort(vector<int> &nums,int left, int right){
        if(left < right){
            int mid = quick(nums, left, right);
            quickSort(nums, left , mid-1);
            quickSort(nums, mid+1, right);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        quickSort(nums, 0, nums.size()-1);
        return nums;
    }
};

• 选择排序

  • 简单选择排序

    时间复杂度：$O(n^2)$

    空间复杂度：$O(1)$

    不稳定排序：很明显没有元素的移动，那么交换很有可能导致后面的元素交换到前面来了

  • 堆排序

    时间复杂度：$O(nlog_2n)$，其中建堆的时间复杂度为$O(n)$

    空间复杂度：$O(1)$

    不稳定排序：选择排序都不是稳定的，因为没有整体后移

class Solution {
public:
    void buildMaxHeap(vector<int> &nums){
        for(int i = nums.size() /2-1; i>=0;i--)
            maxHeapify(nums, i, nums.size()-1);
    }

    void maxHeapify(vector<int> &nums, int root, int right){
        int rval = nums[root];
        for(int i = 2*root+1; i <= right; root = i,i = 2*root+1){
            if(i < right && nums[i] < nums[i+1]) i++;
            if(rval >= nums[i]) break;
            nums[root] = nums[i];
        }
        nums[root] = rval;
    }

    vector<int> sortArray(vector<int>& nums) {
        buildMaxHeap(nums);
        for(int i = nums.size()-1; i > 0; i--){
            swap(nums[0], nums[i]);
            maxHeapify(nums, 0,i-1);
        }
        return nums;
    }
};

• 归并排序

  时间复杂度：$O(nlog_2n)$

  空间复杂度：$O(n)$

  稳定排序

class Solution {
public:
    vector<int> space;
    void merge(vector<int> &nums, int left,int mid, int right){
        for(int i = left; i<= right;i++) space[i] = nums[i];
        int l = left, r = mid+1, i = left;
        while(l <= mid && r <= right){
            if(space[r] < space[l]) nums[i++] = space[r++];
            else nums[i++] = space[l++];
        }
        while(l <= mid) nums[i++] = space[l++];
        while(r <= right) nums[i++] = space[r++];
    }

    void mergeSort(vector<int> &nums,int left, int right){
        if(left < right){
            int mid = (left + right)/2;
            mergeSort(nums, left, mid);
            mergeSort(nums, mid+1, right);
            merge(nums, left, mid, right);
        }
    }

    vector<int> sortArray(vector<int>& nums) {
        space.resize(nums.size());
        mergeSort(nums, 0, nums.size()-1);
        return nums;
    }
};

• 基数排序

  时间复杂度：$O(r)$

  空间复杂度：$O(d(n+r))$

  稳定排序

外部排序

 常用的是归并排序的方法，并且不仅仅是二路归并，常用的是多路归并。

败者树

• 作用：优化多个归并段在内存中的比较次数
• 设归并路数为k，归并趟数为S，每趟归并的元素有n个（每次输出到磁盘中），总共有r个归并段，计算
• 使用败者树后，内部比较次数与归并路数k无关了，所以可以增加归并路数k
• 但是，如果归并路数k太大，那么由于内存不够，会导致缓冲区数量减少，最终还是会影响比较次数

置换-选择排序

• 作用：用于生成更长的归并段，以缩小归并段的数量

最佳归并树

• 作用：将若干的归并段生成读写次数最少的归并树，使用哈夫曼树

• 步骤：设$n_0$为度为0节点个数，也就是归并段的数量。k为归并路数

  1、如果$(n_0 - 1) \% (k-1) = 0$，正好可以构成k叉归并树，直接使用构造哈夫曼树的方法构造即可

  2、如果$(n_0 - 1) \% (k-1) = u \neq 0$，则再加上k-u-1个空的虚拟归并段进行构造哈夫曼树