摘要

冒泡排序、插入排序、希尔排序、选择排序、堆排序、桶排序、快速排序

原地排序算法：特指空间复杂度是O(1)的排序算法。
线性排序：把时间复杂度是线性的排序算法叫作线性排序(Linear sort)常见的线性算法有: 桶排序、计数排序、基数排序（特点: 非基于比较的排序算法 ）

分类

稳定&非稳定

相同元素的相对在排序前后是否会发生改变，如果会，就是不稳定的，否则就是稳定的。

类型

冒泡排序 BubbleSort

算法描述

每趟确定一个，从第1个元素开始，从左往右依次比较，若左边大于右边则交换并移动，直到将未排序集合中的最大值归位
总共趟数：n-1，第i趟比较次数：n-1-i，n为元素个数

动图演示

排序算法 - 图1

代码实现

  1. void BubbleSort(int arr[], int length) {
  2.     int i, j, tmp;
  4.     for (i = 0; i < length - 1; i++) {                // 遍历的趟数：n-1次
  5.         for (j = 0; j < length - 1 - i; j++) {        // 每趟比较次数：n-1-i次，i当前趟数
  6.             if ( arr[j] > arr[j+1] ) {
  7.                 tmp = arr[j];
  8.                 arr[j] = arr[j+1];
  9.                 arr[j+1] = tmp;
  10.             }
  11.         }
  12.     }
  13. }

算法分析

稳定性

稳定：当左边与右边相等时，不用交换

时间复杂度

比较次数
image.png
最好：O(n)
最坏：
平均：O(n2)

进阶优化

解决“最后几趟已有序却仍需要比较”的问题

方案：设置一个标记flag，如果某趟中无元素交换则说明数据已有序，直接跳出大循环（最后几趟不再执行）

  1. void BubbleSort1(int arr[], int length) {
  2.     int i, j, tmp;
  3.     int flag = 0;
  4.     int counts = 0;         // 记录比较次数
  6.     for (i = 0; i < length - 1; i++) {
  7.         flag = 1;                                   // 每趟先标记为有序
  8.         for (j = 0; j < length - 1 - i; j++) {
  9.             if ( arr[j] > arr[j+1] ) {
  10.                 counts++;
  11.                 flag = 0;                           // 只要交换元素则标记为无序
  12.                 tmp = arr[j];
  13.                 arr[j] = arr[j+1];
  14.                 arr[j+1] = tmp;
  15.             }
  16.         }
  18.         if (flag) {
  19.             break;
  20.         }
  21.     }
  23.     printf("counts: %d\n", counts);
  24. }

解决“数据后半部已经有序即前几趟会无效比较”问题

方案：设置一个标记flag，

选择排序 SelectSort

从未排序集合中选出最大/小放置到已排序的起始/末尾位置，冒泡的改进版

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

动图演示

849589-20171015224719590-1433219824.gif

代码实现

  1. for(int i=0; i < len-1; i++) {
  2.     min = i;
  3.     for (int j=i+1; j < len; j++) {
  4.         if (arr[j] < arr[min]) {
  5.             min = j;
  6.         }
  7.     }
  8.     swap(arr, i, min);
  9. }

算法分析

稳定
时间复杂度：$O(n^2)$
空间复杂度：$O(1)$

特点：不占用额外内存空间
适用：数据规模越小越好

插入排序 InsertSort

插入排序（Insertion-Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

算法描述

  1. 将待排序分成已排序和未排序两部分，选择第一个元素为已排序
  2. 从第二元素（即遍历未排序数组）开始，选择已排序中合适位置插入（对已排序数组从后往前扫描）
  3. 重复上述过程直到最后一个元素插入有序子数组中

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

  • 从第一个元素开始，该元素可以认为已经被排序；
  • 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  • 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  • 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  • 将新元素插入到该位置后；
  • 重复步骤2~5。

动图展示

849589-20171015225645277-1151100000.gif

代码实现

  1. // 从小到大
  2. for (int i=1; i < len; i++) {
  3.     temp = arr[i];
  4.     j = i - 1;
  5.     while (j >= 0 && arr[j] > temp) {
  6.         arr[j+1] = arr[j];
  7.         j--;
  8.     }
  9.     arr[j+1] = temp;
  10. }

算法分析

稳定
复杂度
时间复杂度：O(n^2)
空间复杂度：O(1)，原地排序in-place

特点：不占用额外内存空间
适用：数据规模越小越好

稳定性
当两数相等时可选择不交换位置——稳定
适用场景
数组较大的时候不适用。
在数据比较少，一般做为快速排序的扩充。如STL的sort算法、stdlib的qsort算法、JDK 7 java.util.Arrays所用的sort。

希尔排序ShellSort

第一个突破$O(n^2)$的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序

动图演示

代码实现

  1. for (int gap = len/2; gap > 0; gap = gap/2) {
  2.     for (int i = gap; i < len; i++) {
  3.         current = arr[i];
  4.         j = i - gap;
  5.         while (j >= 0 && arr[j] > current) {
  6.             arr[j+gap] = arr[j];
  7.             j -= gap;
  8.         }
  9.         arr[j+gap] = current;  
  10.     }
  11. }

算法分析

不稳定

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

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

希尔排序的核心在于间隔序列的设定。既可以提前设定好间隔序列，也可以动态的定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的。

特点：不占用额外内存空间
适用：数据规模越小越好

归并排序MergeSort

采用分治法（Divide and Conquer）的一个非常典型的应用，且各层分治递归可以同时进行。归并排序思路简单，速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列
归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

算法描述

  • 把长度为n的输入序列分成两个长度为n/2的子序列；
  • 对这两个子序列分别采用归并排序；
  • 将两个排序好的子序列合并成一个最终的排序序列。

递归法（Top-down）

动图演示

849589-20171015230557043-37375010-0466189.gif

代码实现

算法分析

稳定

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

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

特点：不占用额外内存空间

适用：数据规模越小越好

快速排序 QuickSort

基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
优点：其对于大数据的优秀排序性能和相同复杂度算法中相对简单的实现

算法描述

  1. 从数列中选择一个元素，称为“基准pivot”
  2. 重新排列，所有比pivot小的放前面，所有比pivot大的放后面——分区操作partition
  3. 递归地排序前子序列和后子序列

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

  • 从数列中挑出一个元素，称为 “基准”（pivot）；
  • 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  • 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

    动图展示

    849589-20171015230936371-1413523412.gif

    代码实现

算法分析

稳定

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

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

2.5 评价

特点：不占用额外内存空间

适用：数据规模越小越好

桶排序

思想

将数据集分散到几个有序的桶里，每个桶中的数据单独排序。最后将桶里的数据依序取出即可。

特性

  1. 桶有序，且数据易划分
  2. 数据在桶内尽量均匀分布
  3. 适合外部排序——数据存储在磁盘，数据量较大，内存有限，无法加载全部数据到内存

示例
image.png

参考资料

动图展示：https://visualgo.net/zh/sorting