排序大法

1、基本概念

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

2、分类

内部排序

  • 插入排序

    • 直接插入排序

      时间复杂度:最好:O(n)O(n),最坏:O(n2)O(n^2),平均:O(n2)O(n^2)

      空间复杂度:O(1)O(1)

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

    • 折半插入排序

      时间复杂度:最坏:O(n2)O(n^2),平均:O(n2)O(n^2)

      空间复杂度:O(1)O(1)

      稳定排序

    • 希尔排序

      时间复杂度:最坏:O(n2)O(n^2),平均:O(n1.3)O(n^{1.3})(现代数学没法证明)

      空间复杂度:O(1)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),最坏:O(n2)O(n^2),平均:O(n2)O(n^2)

      空间复杂度:O(1)O(1)

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

      • 快速排序

        时间复杂度:最坏:O(n2)O(n^2),平均:O(nlog2n)O(nlog_2n)

        空间复杂度:最好:O(log2n)O(log_2n),最坏:O(n)O(n),平均:O(log2n)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(n2)O(n^2)

      空间复杂度:O(1)O(1)

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

    • 堆排序

      时间复杂度:O(nlog2n)O(nlog_2n),其中建堆的时间复杂度为O(n)O(n)

      空间复杂度:O(1)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(nlog2n)O(nlog_2n)

    空间复杂度:O(n)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(r)

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

    稳定排序

外部排序

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

败者树

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

置换-选择排序

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

最佳归并树

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

  • 步骤:设n0n_0为度为0节点个数,也就是归并段的数量。k为归并路数

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

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