前言
一、各种排序算法比较
二、具体排序算法介绍
2.1 冒泡排序
2.2 选择排序
2.3 插入排序
2.4 快速排序
2.5 希尔排序
2.6 堆排序
2.7 归并排序
2.8 桶排序
2.9 计数排序
2.10 基数排序
三. 总结：
前言
我们在平时学习和工作中经常用到各种排序算法，不仅要考虑算法的时间空间复杂度也要注意稳定性问题。为更好的理解排序算法，在此整理出常见的排序算法，包括：选择排序、冒泡排序、插入排序、快速排序、归并排序、堆排序、希尔排序、桶排序、计数排序、基数排序。
一、各种排序算法比较
复杂度和稳定性的比较（来自维基百科）
这里给大家介绍马老师的口诀记忆法：
《忆排序》
选泡插，快归堆希桶计基
恩方恩老恩一三
对恩加K恩乘K
不稳稳稳不稳稳
不稳不稳稳稳稳
二、具体排序算法介绍
2.1 冒泡排序
2.1 冒泡排序
主要思想：冒泡排序的名字很形象，像水中的气泡一样，气泡大的会向上浮出水面，依次对两个数比较大小，大的数冒出来，小的数压下去。
优点：稳定
缺点：效率慢，每次只能移动相邻的俩个数据
冒泡排序的时间复杂度为O(n*n)，空间复杂度为O(1)，在数据有序的时候时间复杂度可以达到O(n)。适用的情景为数据量量不大，对稳定性有要求，且数据基本有序的情况下。
代码如下（示例）：
void bubble_sort (int a[], int n) {
int i, j, lastSwap, tmp;
for (j=n-1; j>0; j=lastSwap) {
lastSwap=0;
for (i=0; i a[i+1]) {
tmp=a[i];
a[i]=a[i+1];
a[i+1]=tmp;
//最后一次交换位置的坐标
lastSwap = i;
}
}
}
}
2.2 选择排序
主要思想：
（1）从待排序序列中，找到关键字最小的元素，如果最小元素不是待排序序列的第一个元素，将其和第一个元素互换。
（2）从余下的 N - 1 个元素中，找出关键字最小的元素。
重复(1)、(2)步，直到排序结束。
特点：比冒泡更快一些，但代价是跳跃性交换，排序不稳定。
选择排序的时间复杂度为O(n*n)，空间复杂度为O(1)，由于每次选出待排序数据中的最小值（增序）或最大值（降序）插入到当前的有序队列中，相对于冒泡排序减少了交换的次数。当数据量不大，且对稳定性没有要求的时候，适用于选择排序
代码如下（示例）：
void selection_sort (int a[], int n) {
int i,j,pos,tmp;
for (i=0; ia[j])
pos=j;
if (pos != i) {
tmp=a[i];
a[i]=a[pos];
a[pos]=tmp;
}
}
}
2.3 插入排序
主要思想：过程跟拿牌一样，依次拿N张牌，每次拿到到牌后，从后往前看，遇到合适位置就插进去。最终手上的牌从小到大。把N个待排的数据看作一个无序表和一个有序表，开始的时候有序表中只有一个元素，无序表中有N-1个元素，之后依次从无序表中取出元素插入到有序表中的适当位置，使之形成新的有序表。
特点：当数据规模较小或者数据基本有序时，效率较高。
插入排序的时间复杂度为O(n*n)，空间复杂度为O(1)，最好的情况下即当数据有序时可以达到O(n)的时间复杂度。适用于数据量不大，对算法的稳定性有要求，且数据局部或者整体有序的情况。
代码如下（示例）：
void insertion_sort (int a[], int n) {
int i,j,v;
for (i=1; i=0&&v
2.4 快速排序
主要思想：采用分治思想，通常选取第一个数作为基准元素（pivot），依次将剩余元素中比pivot小的数放置其左侧，大于该基准的数放置其右侧；然后取pivot前半部分和后半部分分别进行同样的处理，以此类推直至各子列元素中仅剩一个元素时，即排序完成。
优点：极快数据移动少；
缺点：不稳定；
注意：此排序算法的效率在序列越乱的时候，效率越高。在数据有序时，会退化成冒泡排序；对于小规模数据（n<100），快排由于用了递归，其效率可能还不如插入排序。因此通常可以定义一个阈值，当递归的数据量很小时停止递归，直接调用插排。
快速排序算发的时间复杂度为O(nlogn)，由于快速排序使用递归的方式实现，因此空间复杂度为O(nlogn)到O(n)之间。由于快速排序的原理，常用于查找数组中第k小的数。
将数组中某一个元素m作为划分依据,即m=arr[0]。若m前面的元素个数大于k，则第k小的数一定在m前面的元素中，这时我们只需要继续在m前面的元素中找第k小的数；若m前面的元素小于k，则第k小的数一定在m后面的元素中，这时我们只需要在m后面的元素中找第k小的数；
代码如下（示例）：
int mpartition(int a[], int l, int r) {
int pivot = a[l];
while (la[l]) l++;
if (l
2.5 希尔排序
主要思想：先根据特定步长将整个待排序元素序列分割成若干子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减步长再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。
特点：比较在希尔排序中是最主要的操作，而不是交换。希尔排序的时间复杂度和增量的选择策略有关，用已知最好的步长序列的希尔排序比直接插入排序要快，甚至在小数组中比快速排序和堆排序还快，但在涉及大量数据时希尔排序还是不如快排；
希尔排序时间复杂度为O(nlogn)到O(n*n)之间，空间复杂度为O(1)，其排序的效率受到比较距离大小的影响。和插入排序的过程相似，相对于插入排序而言，比较较远距离的数据，使得数据移动跨过多个元素，进行一次比较可能会消除多个元素的交换。
代码如下（示例）：
void shell_sort(int a[], int n)
{
int d, i, j, temp; //d为增量
for(d = n/2;d >= 1;d = d/2) //增量递减到1使完成排序
{
for(i = d; i < n;i++) //插入排序的一轮
{
temp = a[i];
for(j = i - d;(j >= 0) && (a[j] > temp);j = j-d)
{
a[j + d] = a[j];
}
a[j + d] = temp;
}
}
}
2.6 堆排序
主要思想：堆排序的第一步是建堆，然后是取堆顶元素进行调整。建堆的过程是自底向上不断调整的，当调整某个结点时，若其左右结点已满足条件，此时两结点不需要动则整个子树不需要调整，若需要调整，则父结点交换到子结点的位置，再以此结点继续调整。
堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
堆排序的时间复杂度为O(nlog)，空间复杂度为O(1)。实现原理是根据大顶堆或小顶堆得数据结构原理，对待排序数据进行调整，最终达到整体有序的效果，主要应用于寻找M个数中的前K个最小的数并保持有序。
代码如下（示例）：
void heapAdjust(int a[], int i, int nLength)
{
int nChild;
int nTemp;
for (nTemp = a[i]; 2 * i + 1 < nLength; i = nChild)
{
// 子结点的位置=2*（父结点位置）+ 1
nChild = 2 * i + 1;
// 得到子结点中较大的结点
if ( nChild < nLength-1 && a[nChild + 1] > a[nChild])
++nChild;
// 如果较大的子结点大于父结点那么把较大的子结点往上移动，替换它的父结点
if (nTemp < a[nChild])
{
a[i] = a[nChild];
a[nChild]= nTemp;
}
else
// 否则退出循环
break;
}
}
// 堆排序算法
void heap_sort(int a[],int length)
{
int tmp;
// 调整序列的前半部分元素，调整完之后第一个元素是序列的最大的元素
//length/2-1是第一个非叶节点，此处"/"为整除
for (int i = length / 2 - 1; i >= 0; --i)
heapAdjust(a, i, length);
// 从最后一个元素开始对序列进行调整，不断的缩小调整的范围直到第一个元素
for (int i = length - 1; i > 0; --i)
{
// 把第一个元素和当前的最后一个元素交换，
// 保证当前的最后一个位置的元素都是在现在的这个序列之中最大的
/// Swap(&a[0], &a[i]);
tmp = a[i];
a[i] = a[0];
a[0] = tmp;
// 不断缩小调整heap的范围，每一次调整完毕保证第一个元素是当前序列的最大值
heapAdjust(a, 0, i);
}
}
2.7 归并排序
主要思想：类似两个有序链表的合并，每次两两合并相邻的两个有序序列，直至整个序列有序。思考如何将两个有序数列合并，只要比较两个数列中最小的值，谁小谁先被取，之后再依次进行比较，若其中一个数列为空，则将另一个数列中的元素依次取出即可。
归并排序的时间复杂度为O(nlog)，空间复杂度为O(n)，其需要借助额外的存储空间，，当数据量较大时，要注意考虑内存空间的开销。
归并排序是采用分治法的一个非常典型的应用，归并算法需要两两比较不存在跳跃，因此归并算法属于稳定的算法，若n较大，并且要求排序稳定，则可以选择归并排序。
代码如下（示例）：
void mergearray(int a[], int first, int mid, int last, int temp[])
{
int i = first, j = mid + 1;
int m = mid, n = last;
int k = 0;
while (i <= m && j <= n)
{
if (a[i] <= a[j])
temp[k++] = a[i++];
else
temp[k++] = a[j++];
}
while (i <= m)
temp[k++] = a[i++];
while (j <= n)
temp[k++] = a[j++];
for (i = 0; i < k; i++)
a[first + i] = temp[i];
}
void merge_sort(int a[], int first, int last, int temp[])
{
if (first < last)
{
int mid = (first + last) / 2;
merge_sort(a, first, mid, temp); //左边有序
merge_sort(a, mid + 1, last, temp); //右边有序
mergearray(a, first, mid, last, temp); //再将二个有序数列合并
}
}
2.8 桶排序
主要思想：是一种简单快速的排序算法，也有较大的局限性，仅适用于数据的分布相对比较集中的时候，其原理是建立一个包含一定数目桶的表，将待排序的数据通过散列算法散列到桶中，然后再遍历桶的到有序的数据。
桶排序的时间复杂度为O(n)，利用函数的映射关系，减少了计划所有的比较操作，是一种Hash的思想，可以用在海量数据处理中。
计数排序也可以看作是桶排序的特例，数组关键字范围为N，划分为N个桶。
代码如下（示例）
def bucketSort(arr):
maximum, minimum = max(arr), min(arr)
bucketArr = [[] for i in range(maximum // 10 - minimum // 10 + 1)] # set the map rule and apply for space
for i in arr: # map every element in array to the corresponding bucket
index = i // 10 - minimum // 10
bucketArr[index].append(i)
arr.clear()
for i in bucketArr:
heapSort(i) # sort the elements in every bucket
arr.extend(i) # move the sorted elements in bucket to array
2.9 计数排序
主要思想：计数排序的思想是，考虑待排序数组中的某一个元素a，如果数组中比a小的元素有s个，那么a在最终排好序的数组中的位置将会是s+1，如何知道比a小的元素有多少个，肯定不是通过比较去觉得，而是通过数字本身的属性，即累加数组中最小值到a之间的每个数字出现的次数（未出现则为0），而每个数字出现的次数可以通过扫描一遍数组获得。
计数排序步骤：
1. 找出原数组中元素值最大的，记为max。
2. 创建一个新数组count，其长度是max加1，其元素默认值都为0。
3. 遍历原数组中的元素，以原数组中的元素作为count数组的索引，以原数组中的元素出现次数作为count数组的元素值。
4. 创建结果数组result，起始索引index。
5. 遍历count数组，找出其中元素值大于0的元素，将其对应的索引作为元素值填充到result数组中去，每处理一次，count中的该元素值减1，直到该元素值不大于0，依次处理count中剩下的元素。
6. 返回结果数组result。
代码如下（示例）：
public int[] countSort(int[] A) {
// 找出数组A中的最大值
int max = Integer.MIN_VALUE;
for (int num : A) {
max = Math.max(max, num);
}
// 初始化计数数组count
int[] count = new int[max+1];
// 对计数数组各元素赋值
for (int num : A) {
count[num]++;
}
// 创建结果数组
int[] result = new int[A.length];
// 创建结果数组的起始索引
int index = 0;
// 遍历计数数组，将计数数组的索引填充到结果数组中
for (int i=0; i0) {
result[index++] = i;
count[i]--;
}
}
// 返回结果数组
return result;
}
2.10 基数排序
主要思想：基数排序是按照低位先排序，然后收集；再按照高位排序，然后再收集；依次类推，直到最高位。
基数排序的步骤：以整数为例，将整数按十进制位划分，从低位到高位执行以下过程。
1. 从个位开始，根据0~9的值将数据分到10个桶桶，例如12会划分到2号桶中。
2. 将0~9的10个桶中的数据顺序放回到数组中。
重复上述过程，一直到最高位。
基数排序也可以看作一种桶排序，不断的使用不同的标准对数据划分到桶中，最终实现有序。基数排序的思想是对数据选择多种基数，对每一种基数依次使用桶排序。
基排序的主要适用场景是待排元素是非负整数，且位数相差不大。此外，整数也可以用字符串等表达，所以也可以用于字符串的排序。
代码如下（示例）：
int getNumInPos(int num,int pos) //获得某个数字的第pos位的值
{
int temp = 1;
for (int i = 0; i < pos - 1; i++)
temp *= 10;
return (num / temp) % 10;
}
#define RADIX_10 10 //十个桶，表示每一位的十个数字
#define KEYNUM 5 //整数位数
void radix_sort(int* pDataArray, int iDataNum)
{
int *radixArrays[RADIX_10]; //分别为0~9的序列空间
for (int i = 0; i < RADIX_10; i++)
{
radixArrays[i] = new int[iDataNum];
radixArrays[i][0] = 0; //index为0处记录这组数据的个数
}
for (int pos = 1; pos <= KEYNUM; pos++) //从个位开始到31位
{
for (int i = 0; i < iDataNum; i++) //分配过程
{
int num = getNumInPos(pDataArray[i], pos);
int index = ++radixArrays[num][0];
radixArrays[num][index] = pDataArray[i];
}
for (int i = 0, j =0; i < RADIX_10; i++) //写回到原数组中，复位radixArrays
{
for (int k = 1; k <= radixArrays[i][0]; k++)
pDataArray[j++] = radixArrays[i][k];
radixArrays[i][0] = 0;
}
}
}
三. 总结：
本文总结了常用十种排序算法的主要思想以及适用场景，并进行了算法代码的展示，在此特别感谢以下几篇文章对我的帮助，借鉴了许多其中的行文思路和代码思路，再次表示衷心的感谢。
https://www.cnblogs.com/inchbyinch/p/11630388.html
https://www.cnblogs.com/zhaoshuai1215/p/3448154.html
超详细的八大排序算法的各项比较以及各自的特点_柯南的博客-CSDN博客_排序算法比较
常用的排序算法及其适用场景_半夏。的博客-CSDN博客_排序算法应用场景
