排序

作者: 张_何 | 来源:发表于2021-09-24 18:00 被阅读0次

【恋上数据结构与算法二】(一)排序(Sorting)
排序-冒泡排序
排序
Java | 10种排序算法
常见的排序
002--20200409刷题
排序
排序 -- 选择/插入
前端基础整理 | 算法基础
Java 常见的 8 种排序算法（内排序）

排序分类

稳定排序与不稳定排序

待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中Ri领先于Rj（即i<j）.若在排序后的序列中Ri仍然领先于Rj，则称所用的方法是稳定的。比如int数组[1,1,1,6,4]中a[0],a[1],a[2]的值相等，在排序时不改变其序列，则称所用的方法是稳定的。
稳定的排序算法有:插入排序、基数排序、归并排序、冒泡排序、计数排序
不稳定的排序算法有: 快速排序、希尔排序、简单选择排序、堆排序

内排序与外排序

在内存中进行的排序我们成为内排序。而实际中,经常需要对大文件进行排序,因为文件中的记录很多,信息量庞大,无法将整个文件拷贝进内存进行排序,因此需要将排序的记录存储在外部内存上,排序时再把数据一部分一部分的调入内存进行排序,在排序中需要多次进行内存和外部存储的交互。对外存文件中的记录进行排序后的结果仍然被放到原有文件中。这种排序方法就称外部排序。

排序方法分类

按照排序方法分类可以分为: 插入类排序、交换类排序、选择类排序、归并排序、基数排序、

插入类排序

包括: 直接插入排序、希尔排序

交换类排序

包括: 冒泡排序、快速排序

选择类排序

包括: 简单选择排序、堆排序

归并排序

基数排序

桶排序

冒泡排序

执行步骤

1、从头开始比较每一对相邻元素,如果第一个比第二个大,就交换它们的位置,执行完一轮后,最末尾那个元素就是最大的元素。
2、忽略 1 中曾经找到的最大元素,重复执行步骤 1,直到全部元素有序

为了方便代码复用我们这里定义一个数组和两个函数,一个函数比较大小,一个函数交换数据

List<int> array = <int>[10,3,4,5,9,2,1];

int cmp(index1, index2){
  return array[index1] - array[index2];
}

swap(int index1, int index2) {
  int temp = array[index1];
  array[index1] = array[index2];
  array[index2] = temp;
}

  for(int end = array.length - 1; end > 0; end--){
    for(int begin = 1; begin <= end; begin++){
      if (cmp(begin, begin-1) < 0) {
        swap(begin,begin-1);
      }
    }
  }

优化 - 完全有序

如果序列已经完全有序,可以提前终止冒泡排序

  for(int end = array.length - 1; end > 0; end--){
    bool sorted = true;
    for(int begin = 1; begin <= end; begin++){
      if (cmp(begin, begin-1) < 0) {
        swap(begin, begin-1);
        sorted = false;
      }
    }
    if(sorted) break;
  }

优化 - 尾部局部有序

如果序列尾部已经局部有序,可以记录最后一次交换的位置,减少比较次数

  for(int end = array.length - 1; end > 0; end--){
    int sortedIndex = 1;
    for(int begin = 1; begin <= end; begin++){
      if (cmp(begin, begin-1) < 0) {
        swap(begin, begin-1);
        sortedIndex = begin;
      }
    }
    // 记录从那个索引开始有序的, 这里为什么不-1, 因为执行完这句,for循环就要执行 end-- 了
    end = sortedIndex;
  }

稳定性

冒泡排序属于稳定排序,但冒泡排序的稳定性与交换数据时的判断条件有关,如果两个数据相等时也交换数据,那么就是不稳定排序,如果两个数据相等时不交换,那就是稳定排序

复杂度

最坏、平均时间复杂度为: $O(n^2)$ , 最好时间复杂度为: $O(n)$ , 空间复杂度为 $O(1)$

简单选择排序

执行步骤

1、从序列中找出最大的那个元素,然后与最末尾的元素交换位置,执行完一轮后,最末尾的那个元素就是最大的元素。
2、忽略 1 中曾经找到的最大元素,重复执行步骤 1。

  for(int end = array.length - 1; end > 0; end--){
    int maxIndex = 0;
    for(int begin = 1; begin <= end; begin++){
      if (cmp(maxIndex, begin) < 0) {
        maxIndex = begin;
      }
    }
    swap(maxIndex,end);
  }

选择排序的交换次数要远远小于冒泡排序,平均性能优于冒泡排序。

优化

稳定性

简单选择排序属于不稳定排序

复杂度

最好、最坏、平均时间复杂度: $O(n^2)$ , 空间复杂度为 $O(1)$

堆排序

堆排序可以认为是对选择排序的一种优化

执行步骤

1、对序列进行原地建堆
2、重复执行一下操作,直到堆的元素数量为 1
交换堆顶元素与尾元素
堆的元素数量减 1
对 0 位置进行 1 次 siftDown 操作

  heapSize = array.length;
  for(int i = (heapSize >> 1) - 1; i >= 0; i--) {
    siftDown(i);
  }
  while(heapSize > 1) {
    swap(0, --heapSize);
    siftDown(0);
  }

void siftDown(int index) {
  T element = array[index];
  int half = heapSize >> 1;
  while(index < half){
    int childIndex = (index<<1) + 1;
    T child = array[childIndex];
    int rightIndex = childIndex + 1;
    if (rightIndex < heapSize && cmp(array[rightIndex], child) > 0) {
      child = array[childIndex = rightIndex];
    }
    if (cmp(element,child) >= 0) break;
    array[index] = child;
    index = childIndex;
  }
  array[index] = element;
}

稳定性

堆排序属于不稳定排序

复杂度

最好、最坏、平均时间复杂度为: $O(nlogn)$ , 空间复杂度 $O(1)$ ,

插入排序

执行步骤

1、在执行过程中,插入排序会将序列分为 2 部分,头部是已经排好序的,尾部是待排序的
2、从头开始扫描每一个元素,每当扫描到一个元素,就将它插入到头部合适的位置,使得头部数据依然保持有序

  for(int begin = 1; begin < array.length; begin ++){
    int cur = begin;
    while(cur > 0 && cmp(cur, cur-1) < 0){
      swap(cur,cur-1);
      cur--;
    }
  }

优化 - 挪动

思路是将'交换' 转为挪动, 先将待插入的元素备份,头部有序数据中比待插入元素大的,都朝尾部方向挪动 1 个位置,将待插入元素放到最终的合适位置

  for(int begin = 1; begin < array.length; begin++){
    int cur = begin;
    T v = array[cur];
    while(cur > 0 && cmp(v, array[cur - 1]) < 0){
      array[cur] = array[cur - 1];
      cur--;
    }
    array[cur] = v;
  }

优化 - 二分搜索

在元素 v 的插入过程中,可以先二分搜索出合适的插入位置,然后再将元素 v 插入, 这种优化是优化了查找的次数,挪动的次数还是不变的
要求二分搜索返回的插入位置: 第一个大于 v 的元素位置
思路:
假设在[begin, end)范围内搜索某个元素 v, mid = (begin + end) / 2
如果 v < m, 去[begin, mid) 范围内二分查找
如果 v ≥ m, 去[mid+1, end) 范围内二分查找
实现

void sort(){
  for(int begin = 1; begin < array.length; begin++){
    insert(begin, search(begin));
  }
}

void insert(int source, int dest) {
  int v = array[source];
  for(int i = source; i > dest; i--){
    array[i] = array[i - 1];
  }
  array[dest] = v;
}

int search(int index) {
  int begin = 0, end = index;
  while(begin < end) {
    int mid = (begin + end) >> 1;
    if (cmp(array[index], array[mid]) < 0) {
      end = mid;
    } else {
      begin = mid + 1;
    }
  }
  return begin;
}

需要注意的是,使用了二分搜索后,只是减少了比较次数,但插入排序的平均时间复杂度依然是 $o(n^2)$

复杂度

逆序对: 数组[2,3,8,6,1]的逆序对为:<2,1>、<3,1>、<8,1>、<8,6>、<6,1>共 5 个逆序对
插入排序的时间复杂度与逆序对的数量成正比关系,逆序对的数量越多,插入排序的时间复杂度越高
插入排序的最坏、平局时间复杂度为 $O(n^2)$
最好时间复杂度为: $O(n)$
插入排序的空间复杂度为: $O(1)$
当逆序对的数量极少时,插入排序的效率特别高,甚至速度比 $O(nlogn)$ 级别的快速排序还要快
数据量不是特别大的时候,插入排序的效率也是非常好的

稳定性

插入排序属于稳定排序, 但其稳定性同样与交换数据的触发条件有关系,在两个数据相等时不交换即是稳定排序,如果交换则为不稳定排序

希尔排序

思路

希尔排序把序列看作是一个矩阵,分成 m 列,逐列进行排序, m 从某个整数逐渐减为 1, 当 m 为 1 时,整个序列将完全有序
因此,希尔排序也被称为递减增量排序
矩阵的列数取决于步长序列,不同的步长序列,执行效率也不同。比如步长序列为{1,5,19,41,109,...},就代表依次分成 109 列、41 列、19 列、5 列、1 列进行排序

实例

希尔本人给出的步长序列是 $n/2^k$ ,比如n 为 16 时,步长序列是{1,2,4,8}
分成 8 列进行排序
分成 4 列进行排序
分成 2 列进行排序
分成 1 列进行排序
每次分列排序后逆序对的数量就会减少
假设有 11 个元素,步长序列是{1,2,5}

假设元素在 col 列、第 row 行,步长(总列数)是 step, 那么: 个元素在数组中的索引是 col + row * step
比如 9 在排序前是第 2 列、第 0 行,那么它排序前的索引是 2+0*5 = 2
比如 4 在排序前是第 2 列、第 1 行,那么它排序前的索引是 2+1*5 = 7

实现

List<int> array = [2,3,4,1,5,9,4,7];
void main()
  List<int> stepSequence = shellStepSequence();
  for(int step in stepSequence){
    sort(step);
  }
}
List<int> shellStepSequence(){
  List<int> stepSequence = List();
  int step = array.length;
  while((step >>= 1) > 0) {
    stepSequence.add(step);
  }
  return stepSequence;
}
void sort(int step){
  for(int col = 0; col < step; col++){
    for(int begin = col + step; begin < array.length; begin += step){
      int cur = begin;
      while(cur > col && cmp(cur,cur-step) < 0){
        swap(cur,cur-step);
        cur -= step;
      }
    }
  }
}

最优步长序列

希尔本人给出的步长序列,最坏情况时间复杂度是 $O(n^2)$
目前已知的最好的步长序列,最坏情况时间复杂度是 $O(n^m)$ , m = $4/3$ , 其计算方式如下:

当 k 为偶数时: 9(2^k - 2^(k/2)) + 1
当 k 为奇数时: 82^k - 62^((k+1)/2) + 1
其结果是: {1,5,19,41,109...}
其实现如下:

List<int> sedgewickStepSequence(){
  List<int> stepSequence = List();
  int k =0,step = 0;
  while(true) {
    if(k%2 == 0){
      int pow = (int) Math.pow(2,k>>1);
      step = 1+9*(pow * pow - pow);
    } else {
      int pow1 = (int) Math.pow(2,(k-1)>>1);
      int pow2 = (int) Math.pow(2,(k+1)>>1);
      step = 1 + 8*pow1*pow2 - 6*pow2;
    }
    if(step >= array.length) break;
    stepSequence.add(0,step);
  }
  return stepSequence;
}

稳定性

希尔排序属于不稳定排序

复杂度

希尔排序是在原地进行的,所以其空间复杂度是 O(1)
希尔排序最好时间复杂度是:O(n)
希尔排序最坏时间复杂度在: O(n^(4/3))~O(n2) 之间
希尔排序平均时间复杂度取决于步长序列

快速排序

执行步骤

1、从序列中选择一个轴点元素(pivot), 假设每次选择 0 位置的元素作为轴点元素
2、利用 pivot 将序列分割成 2 个子序列
将小于 pivot 的元素放在 pivot 前面(左侧)
将大于 pivot 的元素放在 pivot 后面(右侧)
等于 pivot 的元素放那边都可以
3、对子序列进行 1、2 操作,直到不能再分割(子序列中只剩下 1 个元素)
快速排序的本质是逐渐将每一个元素都转换成轴点元素

实现

List<int> array = [2,3,4,1,5,9,4,7];
void sort(int begin, int end){
  if(end-begin<2) return;
  int middle = pivotIndex(begin,end);
  sort(begin,middle);
  sort(middle+1,end);
}
int pivotIndex(int begin, int end){
  // 随机交换 begin 位置的元素
  swap(begin, begin+(int)(Math.random()*(end-begin)));
  int pivot = array[begin]; //备份begin 位置元素
  end--; // end 指向最后一个元素
  while(begin < end) {
    while(begin < end){
      if (cmp(pivot, array[end]) < 0) { // 注意这里是小于 0,为啥不是小于等于 0
        end--;
      } else {
        array[begin++] = array[end];
        break;
      }
    }
    while(begin < end){
      if (cmp(pivot, array[begin]) > 0) { // 注意这里是小于 0,为啥不是大于等于 0
        begin++;
      } else {
        array[end--] = array[begin];
        break;
      }
    }
  }
  array[begin] = pivot; //覆盖
  return begin; // 返回轴点位置
}

关于轴点的细节

上面算法的实现在我们比较两个元素时使用＜或＞而不是≤或≥, 这是为什么呢?
假设我们序列中的所有元素都相等,那么用＜或＞,轴点元素可以将序列分割成2 个均匀的子序列。
如果使用≤或≥,会出现轴点元素分隔出来的子序列极度不均匀的情况,导致出现最坏时间复杂度 $O(n^2)$

复杂度

由于递归调用的缘故,空间复杂度为 O(logn)
在轴点左右元素数量比较均匀的情况下,同时也是最好的情况: T(n)=2*T(n/2) + O(n) = O(nlogn)
如果轴点左右元素数量极度不均匀,则是最坏情况:T(n) = T(n-1)+O(n) = $O(n^2)$
为了降低最坏情况的出现概率,一般采取的做法是:随机选择轴点元素
最好、平均时间复杂度为:O(nlogn)
最坏时间复杂度为: $O(n^2)$

稳定性

快排属于不稳定排序

归并排序

执行步骤

1、不断地将当前序列平均分割成 2 个子序列,知道不能再分割(序列中只有一个元素)
2、不断地将 2 个子序列合并成一个有序序列,直到最终只剩 1 个有序序列。
细节: 需要 merge 的 2 组序列存在于同一个数组中,并且是挨在一起的。为了更好地完成 merge 操作,最好将其中 1 组序列备份出来,这里我们选择备份左半部分

实现

List<int> array = [1,3,9,4,2,8,7,5,6];
List<int>  leftArray = List(array.length >> 1); // 创建一个容量是数组长度一半的数组,用来备份数据
void sort(int begin, int end){
  if(end - begin < 2) return; // 至少需要两个元素
  
  int mid = (begin + end) >> 1;
  sort(begin,mid);
  sort(mid,end);
  merge(begin,mid,end);
}

void merge(int begin, int mid, int end) {
  int li = 0, le = mid - begin; // 左边数组(基于 leftArray)
  int ri = mid, re = end; // 右边数组(基于 array)
  int ai = begin; // array 的索引
  for(int i = li; i < le; i++) { // 拷贝左边数组到 leftArray
    leftArray[i] = array[begin + i];
  }
  while(li < le) {
    if (ri < re && cmp(array[ri], leftArray[li]) < 0) { // 改为 cmp() <=0 会失去稳定性
       array[ai++] = array[ri++]; // 拷贝右边数组到 array
    } else {
      array[ai++] = leftArray[li++]; // 拷贝左边数组到 array
    }
  }
}

复杂度

归并排序总是平均分隔子序列,所以最好最坏平均时间复杂度都是 $O(logn)$
归并排序需要创建一个长度为数组长度一半的新数组,所以其空间复杂度为 $O(n/2 + logn)=O(n)$ , n/2 用于临时存放左侧数组, logn 是因为递归调用

稳定性

归并排序属于稳定排序,但其稳定性同样与交换数据的触发条件有关系

计数排序

之前学习的冒泡、选择、插入、归并、快速、希尔、堆排序,都是基于比较的排序,平均时间复杂度目前最低是O(nlogn)
计数排序、桶排序、基数排序都不是基于比较的排序, 它们是典型的用空间换时间,在某些时候,平均时间复杂度可以比 O(nlogn)更低
计数排序于 1954 年提出,适合对一定范围内的整数进行排序
计数排序思想是: 统计每个整数在数列中出现的次数,进而推导出每个整数在有序序列中的索引

简单实现

void sort(){
  // 取出最大值,用来开辟数组的容量
  int max = array[0];
  for(int i = 1; i< array.length; i++){
    if(array[i] > max){
      max = array[i];
    }
  }
  // 统计元素出现的次数
  List<int> counts = List(max + 1);
  for(int i= 0; i< array.length; i++){
    counts[array[i]]++;
  }
  
  // 按顺序赋值
  int index = 0;
  for(int i= 0; i< counts.length; i++){
    while(counts[i]-- > 0){
      array[index++] = i;
    }
  }
}

上面实现有以下缺点:

无法对负整数进行排序
极其浪费内存空间
是个不稳定排序

优化思路

假设 array 中的最小值是 min

array 中的元素 k 对应的 counts 索引是 k-min
array 中的元素 k 在有序序列中的索引
counts[k - min] - p, p 代表着是倒数第几个 k

比如元素 8 在有序序列中的索引

counts[8-3]-1,结果为 7

倒数第1 个元素 7 在有序序列中的索引

counts[7-3]-1,结果为 6

倒数第 2 个元素 7 在有序序列中的索引

counts[7-3]-2,结果为 5

优化实现

void sort(){
  // 取出最大值,用来开辟数组的容量
  int max = array[0];
  int min = array[0];
  for(int i = 1; i< array.length; i++){
    if(array[i] > max){
      max = array[i];
    }
    if(array[i] < min){
      min = array[i];
    }
  }
  // 用于计数
  List<int> counts = List(max - min + 1);
  for(int i= 0; i< array.length; i++){
    counts[array[i]-min]++;
  }
  for(int i = 0; i< counts.length; i++){
    counts[i] += counts[i-1];
  }
  // 用于存放排好序的数据
  List<int> output = List(array.length);
  for(int i= array.length-1; i>= 0; i--){
    output[--counts[array[i]-min]] = array[i];
  }
  for(int i = 0; i < array.length; i++){
    array[i] = output[i];
  }
}

对自定义对象进行排序

如果自定义对象可以提供用以排序的整数类型,依然可以使用计数排序, 比如 Person 对象中有的 int 类型的 age 属性,Person 的排序就是根据 age 来排序的话是可以使用计数排序的

稳定性

计数排序属于稳定排序

复杂度

计数排序的空间复杂度为:O(n+k)
计数排序的最好、最坏、平均时间复杂度均为:O(n+k)

基数排序

基数排序非常适用于整数排序(尤其是非负整数)
执行流程: 依次对个位数、十位数、百位数、千位数、万位数...进行排序(从低位到高位)
个位数、十位数、百位数的取值范围都是固定的 0~9,可以使用计数排序对它们进行排序
如果先对高位排序,再对低位排序,是否可行? 不行

实现

void main() {
  int max = array[0];
  for(int i= 1; i< array.length; i++){
    if(array[i] > max){
      max = array[i];
    }    
  }
  List<int> output = List(array.length);
  List<int> counts = List(10);
  for(int divider = 1; divider <= max; divider *= 10){
    countingSort(divider, output, counts);
  }
}

void countingSort(int divider, List<int> output, List<int> counts){
  for(int i= 0; i< counts.length; i++){
    counts[i] = 0;
  }
  for(int i = 0; i< array.length; i++){
    counts[array[i] / divider % 10]++;
  }
  for(int i = 1; i< counts.length; i++){
    counts[i] += counts[i-1] ;
  }
  for(int i = array.length - 1; i >= 0; i--){
    output[--counts[array[i] / divider % 10]] = array[i];
  }
  for(int i = 0; i < array.length; i++){
    array[i] = output[i];
  }
}

稳定性

基数排序属于稳定排序

复杂度

最好、最坏、平均时间复杂度: O(d * (n+k)), d 是最大值的位数, k 是进制。
空间复杂度为:O(n+k) , k 是进制

桶排序

执行步骤

1、创建一定数量的桶(比如用数组、链表作为桶)
2、按照一定的规则(不同类型的数据,规则不同),将序列中的元素均匀分配到对应的桶
3、分别对每个桶进行单独排序
4、将所有非空桶的元素合并成有序序列
元素在桶中的索引: 元素值*元素数量

休眠排序

 List<int> array = [10,100,50,30,40];
 for(int i = 0; i < array.length; i++){
   SortThread(array[i].start());
 }

class SortThread extends Thread {
  int value;
  SortThread(int value) {
    this.value = value;
  }
  void run(){
    try{
      Thread.sleep(value);
      System.out.println(value);
    } catch (e) {

    }
  }
}

排序算法的比较

类别	排序方法	平均情况	最坏情况	空间复杂度	稳定性
插入排序	直接插入	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
插入排序	Shell 排序	$O(n^1.3)$	$O(n^2)$	$O(1)$	不稳定
选择排序	直接选择排序	$O(n^2)$	$O(n^2)$	$O(1)$	不稳定
选择排序	堆排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(1)$	不稳定
交换排序	冒泡排序	$O(n^2)$	$O(n^2)$	$O(1)$	稳定
交换排序	快速排序	$O(nlog_2n)$	$O(n^2)$	$O(nlog_2n)$	不稳定
归并排序	归并排序	$O(nlog_2n)$	$O(nlog_2n)$	$O(n)$	稳定
基数排序	基数排序	$O(d(r+n))$	$O(d(r+n))$	$O(r+n)$	稳定

原地算法

不依赖额外的资源或者依赖少数的额外资源,仅依靠输出来覆盖输入的算法称为原地算法。空间复杂度为 $O(1)$ 的都可以认为是原地算法

【恋上数据结构与算法二】(一)排序(Sorting)
排序方法冒泡排序选择排序堆排序插入排序归并排序快速排序希尔排序计数排序基数排序桶排序初识排序...
排序-冒泡排序
排序系列传递门排序—选择排序排序—快速排序排序—插入排序排序-希尔排序（待完善）排序—归并排序（待完善）排序—基...
排序
冒泡排序：冒泡排序选择排序：插入排序：希尔排序：归并排序：快速排序：堆排序：计数排序：桶排序： ...
Java | 10种排序算法
冒泡排序选择排序插入排序希尔排序计数排序基数排序堆排序归并排序快速排序桶排序
常见的排序
冒泡排序：选择排序: 插入排序：快速排序：希尔排序：归并排序：堆排序：计数排序：桶排序：基数排序：
002--20200409刷题
冒泡排序选择排序插入排序希尔排序归并排序快速排序堆排序计数排序桶排序基数排序
排序
排序符号：Θ 插入排序选择排序堆排序归并排序冒泡排序快速排序桶排序基数排序计数排序插入排序插...
排序 -- 选择/插入
聊聊排序吧冒泡排序选择排序插入排序快速排序归并排序计数排序桶排序堆排序本篇选择排序与插入排序 ...
前端基础整理 | 算法基础
排序算法冒泡排序选择排序插入排序希尔排序归并排序堆排序快速排序
Java 常见的 8 种排序算法（内排序）
排序分类内部排序插入排序：直接插入排序、希尔排序交换排序：冒泡排序、快速排序选择排序：直接选择排序、堆排序...

排序

排序分类

稳定排序与不稳定排序

内排序与外排序

排序方法分类

插入类排序

交换类排序

选择类排序

归并排序

基数排序

桶排序

冒泡排序

执行步骤

优化 - 完全有序

优化 - 尾部局部有序

稳定性

复杂度

简单选择排序

执行步骤

优化

稳定性

复杂度

堆排序

执行步骤

稳定性

复杂度

插入排序

执行步骤

优化 - 挪动

优化 - 二分搜索

复杂度

稳定性

希尔排序

思路

实例

实现

最优步长序列

稳定性

复杂度

快速排序

执行步骤

实现

关于轴点的细节

复杂度

稳定性

归并排序

执行步骤

实现

复杂度

稳定性

计数排序

简单实现

优化思路

优化实现

对自定义对象进行排序

稳定性

复杂度

基数排序

实现

稳定性

复杂度

桶排序

执行步骤

休眠排序

排序算法的比较

原地算法

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读