"排序算法总结"

  "算法"

Posted by Xu on March 6, 2018

排序算法

排序算法参考

稳定性

  • 排序算法的稳定性:若待排序的序列中,存在多个具有相同关键字的记录,经过排序, 这些记录的相对次序保持不变,则称该算法是稳定的;若经排序后,记录的相对 次序发生了改变,则称该算法是不稳定的。
    • 稳定性的好处:排序算法如果是稳定的,那么从一个键上排序,然后再从另一个键上排序,第一个键排序的结果可以为第二个键排序所用。基数排序就是这样,先按低位排序,逐次按高位排序,低位相同的元素其顺序再高位也相同时是不会改变的。另外,如果排序算法稳定,可以避免多余的比较;
  • 稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序
  • 不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序

sort_stable

时间复杂度

时间复杂度来说:

  1. 平方阶(O(n2))排序
    • 各类简单排序:直接插入、直接选择和冒泡排序;
  2. 线性对数阶(O(nlog2n))排序
    • 快速排序、堆排序和归并排序;
  3. O(n1+§))排序,§是介于0和1之间的常数。
    • 希尔排序
  4. 线性阶(O(n))排序
    • 基数排序,此外还有桶、箱排序。

说明:

  • 当原表有序或基本有序时,直接插入排序和冒泡排序将大大减少比较次数和移动记录的次数,时间复杂度可降至O(n);

  • 而快速排序则相反,当原表基本有序时,将蜕化为冒泡排序,时间复杂度提高为O(n2);

  • 原表是否有序,对简单选择排序、堆排序、归并排序和基数排序的时间复杂度影响不大。

sort

初级排序算法

选择排序

  1. 首先在整个数组中找到最小值,与数组的第一个元素交换位置。
  2. 继续在剩下的元素中找到最小值,与第二个元素交换位置,如此循环往复,直到将整个数组排序。

选择排序需要大约N^2/2次比较和N次交换

N^2/2次比较:第一次要找到最小值,需要和N个值进行比较,第二次需要比较N-1次。。。

比较次数为 N+N-1+N-2+N-3…+3+2+1 = N(N-1)/2 ~ N^2/2

特点:

  1. 运行时间和输入无关,运行时间固定,因为每次在N个元素中找到最小值必然要进行N次比较
  2. 数据移动最少,交换次数和数组大小呈线性关系

插入排序

将元素插入到数组前面已经排好序的合适位置,插入后,有序元素中插入元素后面的所有元素都要向后移动一位

平均需要N^2/4次比较和N^2/4次交换,最坏需要N^2/2次比较和N^2/2次交换,最好只需要N-1次比较和0次交换

插入排序的比较次数和交换次数和输入密切相关

插入排序需要的交换操作次数和数组中倒置的数量相同(因为每一次交换只能解决一个倒置元素对),需要比较的次数大于等于倒置的数量,小于等于倒置的数量加上数组大小减1.

希尔排序

希尔排序是一种基于插入排序的排序算法,也叫做缩小增量算法,我们依据增量序列(hn,hn-1…h3,h2,h1),最后h1为1,这样的序列保证,每hn个元素有序,然后每hn-1个元素有序,…一直到h1后就可以保证所有元素有序,保证有序是通过插入排序实现的

增量序列有多种:

  1. 希尔增量: ht = N/2,hk = (hk+1)/2 最坏情况时间复杂度为O(N^2)
  2. Hibbard增量(相邻的增量没有公因子):1,3,7,2^k-1。 最坏情况时间复杂度为O(N^(3/2))

特点:

  1. 优于插入排序和选择排序,对于一般的中等大小的数组排序时间可以接受
  2. 代码量小,不需要额外的内存空间

归并排序

自顶向下归并排序:递归地将一个数组分成两半分别排序,然后将排序结果合并merge

sort(a,0,s.length-1);
void sort(array a,int lo,int high){
   if hi<=lo
      return;
   mid = (lo+hi)/2;   
   sort(a,lo,mid);//左半数组排序
   sort(a,mid+1,hi);//右半数组排序
   merge(a,lo,mid,hi);//合并左右数组

}

命题:

  1. 对于长度为N的任意数组,自顶向下的归并排序需要(1/2)NlgN至NlgN次比较
  2. 对于长度为N的任意数组,自顶向下归并排序最多要访问数组6NlgN次

改进:

  1. 对小规模数组使用插入排序
  2. 测试数组是否已经有序,比较a[mid]<=a[mid+1]?
  3. 不将元素复制到辅助数组:在递归调用过程中交换输入数组和辅助数组的角色(不理解)

自底向上的归并排序:首先将每个元素想象成一个大小为1的数组,然后两两归并,然后四四归并,直到将整个数组排序完成。

for(int sz = 1;sz< N;sz *=2 )
   for(int lo = 0;lo<N-sz;lo+=sz+sz){
       merge(a,lo,lo+sz-1,Math.min(lo+sz+sz-1,N-1));
   }

自顶向下的命题在这里也成立

快速排序

**最后切割点元素插入到正确的位置

和归并排序互补,归并排序是将一个数组等分为两个子数组,当所有等分子数组有序后,整个数组也就有序了,而快速排序则是根据切分点来将数组划分成两个子数组,然后所有子数组有序后整个数组也有序

sort(a,0,a.length-1);

void sort(array a,int lo,int hi){
    if (hi<=lo)
        return;
    int partition_num = partition(a,lo,hi);//获取划分点
    sort(a,lo,partition_num-1);
    sort(a,partition_num+1,hi);
    
    
}

快速排序的关键在于如何找到切分点,因为每一次切分都可以将切分点放到正确的位置,一般的策略是随机取a[lo]作为切分元素,然后寻找到它的正确位置,并将所有小于它的元素放到左侧,大于它的元素放到右侧。

int partition(array a, int lo,int hi){
    int i = lo,j = hi+1;
    int part_data = a[lo];//选取a[lo]为切分元素
    while(true){
        while(a[++i]<=part_data)
          if (i==hi) break;//边界考虑,如果直接遍历到数组末端该怎么处理
        while(a[--j]>part_data)
          if(j==lo) break;
        if(i>=j) break;
        exch(a,i,j);//交换大小元素的位置
    }
    exch(a,lo,j);//交换a[lo]到正确的位置
    return j;

}

c++实现:

  void quickSort(vector<int> & vec, int start, int end) {
    if (start == end)
      return;
    if (vec.empty())
      return;
    int pos = partition(vec, start, end);//找到切分点
    if(pos-1>=start)
      quickSort(vec, start, pos - 1);
    if(pos+1<=end)
      quickSort(vec, pos + 1, end);
  }

  int partition(vector<int> & vec,int lo,int high) {
    int div = vec[lo];
    int i = lo,j = high+1;
    while (true) {
      while (vec[++i] <= div)
        if (high == i)
          break;
      while (vec[--j] > div)
        if (lo == j)
          break;
      if (i >= j)//到最后结束循环,j在i的前面
        break;
      swap(vec[i],vec[j]);
    }

    swap(vec[lo],vec[j]);//将分割元素插入到合适的位置,从尾端遍历过来的指针最后循环结束会落在所有小于切割数的最后一个元素
    return j;
  }

partition

注意点:

  1. 原地切分,不要在每一次递归都创建一个新的数组来复制数据,直接在原数组上操作
  2. 别越界:数组访问不要控制越界的情况发生
  3. 保持随机性:保持切分元素的随机性
  4. 终止循环:考虑到数组中可能出现和切分元素相同的元素
  5. 处理有重复元素值的情况:左侧扫描使用>=,右侧扫描使用<=
  6. 终止递归:小心处理递归结束的情况

特点:

  1. 比较次数少,快速排序的最好情况是正好能将数组对半分
  2. 将长度为N的无重复数组排序,平均需要~2NlnN次比较
  3. 快速排序最多需要约N^2/2次比较

改进:

  1. 切换到插入排序,对于小数组快速排序比插入排序慢
  2. 三取样切分:使用子数组的一小部分元素的中位数来切分数据,可以提高排序速度
  3. 三向切分法(用于处理大量重复的元素):维护三个数组:lo~lt-1(均小于v),lt~i-1(均等于v),gt+1~hi(均大于v),剩下的i~gt中的元素还需要扫描处理

3D_partition

优先队列

优先队列的每一个元素都具有优先级,支持两种操作:删除最大元素和插入元素

我们可以用数据结构二叉堆来很好实现优先队列的基本操作

堆的定义:所有的父节点都大于(最大堆)或等于两个孩子节点

二叉堆可以用数组pq[]来表示:位置p[k]节点的父节点位置为pq[k/2],孩子节点的位置为p[2k]和p[2k+1],我们不使用pq[0],堆元素存放在1~N中

堆的有序化操作

  1. 由下至上的堆有序化(上浮):当一个叶子节点优先级变大,或者添加一个节点时大于当前父节点时,我们需要替换该节点和父节点的位置,保证堆的特性,然后验证替换后该节点和新的父节点的关系,如此循环直到节点被替换到正确的位置
  2. 由上至下的堆有序化(下沉):当一个父节点变小时,小于它的两个孩子节点,则选择两个孩子中较大者和该父节点替换,替换后继续和新的孩子节点比较,如此循环,直到该父节点下沉到正确的位置。

插入操作:我们在数组末尾添加一个元素,然后通过上浮操作插入到正确的位置

删除最大元素操作:我们删除数组第一个元素,然后将数组末尾的元素放到数组首端,然后对该元素进行下沉操作即可

堆排序

1.构建堆结构(只需要少于2N次比较和N次交换)

从右至左使用sink()下层操作,因为从右边开始,都是一个子堆的根节点,从一棵树的底部开始,直到N/2处开始才会出现下沉操作,因为只有位于N/2处的节点才有孩子节点,所以前半部分全部执行下层操作后,一个堆也就成功构建了

2.1 不断获取并删除最大值或最小值,得到的序列为有序数组

2.2 我们还可以将获取的最大值存放到数组末端,因为每次删除第一个节点后,会将数组末端的元素移动到第一个,这样数组末端的位置就空出来了,这样处理不需要额外的空间来存放排序数组

代码实现:(构建一个最小堆)

class Solution {
public:
  void sort_heap(vector<int> & vec) {
    make_heap(vec);
    int end = vec.size()-1;
    for (int i = 0; i < vec.size(); i++) {
      swap(vec[0],vec[end]);//将首元素和堆中最后一个元素互换
      down(vec,0,--end);//然后将首部元素下沉即可
    }
  }
  void make_heap(vector<int> & vec) {
    int len = vec.size();
    for (int i = len / 2 - 1; i >= 0; i--) {//对前N/2个元素进行下沉操作即可构建堆
      down(vec, i, len-1);
    }
  }
  void down(vector<int> & vec, int start, int end) {
    int pos = start;
    int child = 2*pos+1;
    while (child <= end) {//确定要交换的孩子节点的下标
      if (child+1 <=end && vec[child] > vec[child+1]) {
        child++;
      }

      if (vec[child] < vec[pos]) {//如果最小的孩子节点都小于该节点时,则交换位置
        swap(vec[child],vec[pos]);
      }
      else {
        break;//说明无需调整
      }
      pos = child;
      child = 2 * pos + 1;
    }
  }

};