当前位置 博文首页 > Linux猿：【万字整理】??8大排序算法??【建议收藏】
🎈 作者：Linux猿
🎈 简介：CSDN博客专家🏆，C/C++、面试、刷题、算法尽管咨询我，关注我，有问题私聊！
🎈 关注专栏：C/C++面试通关集锦?（优质好文持续更新中……）🚀
目录
一、冒泡排序
1. 算法思想
2. 实例演示
3. 代码实现
4. 算法复杂度
二、选择排序
1. 算法思想
2. 实例演示
3. 代码实现
4. 算法复杂度
三、快速排序
1. 算法思想
2. 实例演示
3. 代码实现
4. 算法复杂度
四、归并排序
1. 算法思想
2. 实例演示
3. 代码演示
4. 算法复杂度
五、堆排序
1. 算法思想
2. 实例演示
3. 代码实现
4. 算法复杂度
六、直接插入排序
1. 算法思想
2. 实例演示
3. 代码实现
4. 算法复杂度
七、希尔排序
1. 算法思想
2. 实例演示
3. 代码实现
4. 算法复杂度
八、基数排序
1. 算法思想
2. 实例演示
3. 代码实现
4. 算法复杂度
本文来整理一下八大排序算法，下面将结合实例演示进行说明！
冒泡排序是一种比较简单的排序算法，它是一种基于比较的算法，是一种稳定的排序算法。从第一个元素开始，每次比较相邻元素，如果元素顺序不正确，则进行交换，否则，比较下一对相邻元素。重复上述过程，一直到所有元素都有序。
稳定性：
若经过排序后，各元素的相对位置不变（排序前 r[i] 在 r[j] 前，排序后 r[i] 依然在 r[j] 后，相对位置不变），即排序具有稳定性。
下面以数组 [7, 9, 5 , 3, 1] 为例进行从小到大排序的演示：
第一趟排序：
7 与 9 不交换? =》 9 与 5 交换? =》 9 与 3 交换? =》 9与1交换
第一趟排序结果为：
[7, 5, 3, 1, 9]
经过第一趟排序后，9已经在最终排序位置上。
第二趟排序：
7与5 交换? =》 7 与 3 交换? =》 7与1不交换（9 已经在最终位置上不必进行比较）
第二趟排序结果为：
[5, 3, 1, 7, 9]
经过第二趟排序后，7，9已经在最终排序位置上。
第三趟排序：
5 与 3 交换，5与1交换
第三趟排序结果为：
[3, 1, 5, 7, 9]
经过第三趟排序后，5,7,9 已经在最终位置上。
第四趟排序：
3 与 1 交换
第四趟排序结果为：
[1, 3, 5, 7, 9]
经过第四趟排序后，数组已经有序。
可以看到每一趟排序后至少有一个元素在最终的排序位置上，最多经过 n-1 趟排序，数组全部有序。
接下来看一下代码实现。
void bubbleSort(int g[], int n) {
bool flag = true; //检查数组是否有序
for(int i = 0;i < n-1; ++i){
flag = false;
for(int j = 0; j < n-i-1; ++j){//n-i-1 已经有序的元素不再比较
if(g[j] > g[j+1]){
swap(g[j], g[j+1]);
flag = true;
}
}
if(!flag) break; // flag = false 表示没有交换元素，数组已经有序
}
}空间复杂度：除了本身的数组不需要额外的存储空间，故空间复杂度为 O(1)。
时间复杂度：有两层 for 循环，排序次数的时间复杂度为 O(n)，交换次数的时间复杂度为O(n)，因为是嵌套的，故总的复杂度为O(n^2)。
选择排序是一个比较简单的排序，是一种基于选择的排序算法，但并不是一个稳定的排序算法。
基本思想（从小到大排序）：选择数组最小的元素，与数组第一个元素交换，然后选择剩余的数组元素中最小的元素，与数组第二个元素交换，一直重复上述操作，直到数组有序。
下面以数组 [7, 9, 5 , 3, 1] 为例进行从小到大排序的演示：
第一趟排序：
遍历一遍数组，最小的元素是1，与 第一个元素 7 交换。
第一趟排序的结果为：
[1, 9, 5, 3, 7]
第一趟排序后，元素 1 已经在最终排序位置上。
第二趟排序：
遍历一遍数组剩余元素，最小元素是3，3 与 9 交换。
第二趟排序的结果为：
[1, 3, 5, 9, 7]
经过第三趟排序后，将 3 放置到最终排序位置（其实 5 也已经在最终位置了）
第三趟排序：
遍历一遍数组剩余元素，最小元素是 5，已经在最终排序位置，不用交换。
第三趟排序的结果为：
[1, 3, 5, 9, 7]
第四趟排序：
遍历一遍数组剩余元素，最小元素是 7，将 7 与 9 交换。
第四趟排序结果为：
[1, 3, 5, 7, 9]
第四趟排序后，全部元素已经有序。
void selectSort(int a[], int n){
int Min;
for(int i = 0;i < n-1; ++i){//选择 n-1 次
Min = i;
for(int j = i+1; j < n; ++j){//从 i-n之间选择一个最小值放在i处。
if(a[j] < a[Min]){
Min = j;
}
}
if(Min != i){
swap(a[i], a[Min]);
}
}
}空间复杂度：除了本身的数组不需要额外的存储空间，故空间复杂度为 O(1)。
时间复杂度：两层嵌套的 for 循环，每个的时间复杂度为O(n)，故总的时间复杂度为O(n^2)
快速排序是一种更优的排序算法，是一种不稳定的排序算法。它采用分而治之的思想，每次排序选择待排序序列的一个值，该值作为枢纽值，以该值为基点，小于该值的交换到左边，大于该值的交换到右边。然后，重复上述操作，排序左右两边待排序的序列。一直分解到单个元素，每次分解都会确定一个元素的最终位置。
那么，交换的规则是什么呢？
以左边第一个是枢纽值为例，枢纽值首先从右向左找到一个小于枢纽值的元素，将这个元素与枢纽值交换位置，交换后再从左到右与枢纽值进行比较，找到一个比枢纽值大的元素，与枢纽值交换，然后重复上述过程，直到枢纽值左边元素不大于枢纽值，枢纽值右边不小于枢纽值为止。
下面以数组 [5, 7, 9 , 3, 1] 为例进行从小到大排序的演示：
枢纽值的选择以待排序序列的第一个为例。
首先，选取 5 为枢纽值，先从右向左找到一个小于枢纽值 5 的值，并与之交换位置，很明显，
5 与 1 交换，交换后数组变为：
[1, 7, 9, 3, 5]
然后，从左向右找到一个比枢纽值大的元素，并与之交换位置，这个元素是7，与5交换位置后，数组变为：
[1, 5, 9, 3, 7]
然后，从右向左找到一个比枢纽值小的元素，并与之交换位置，这个元素是3，与5交换位置后，数组变为：
[1, 3, 9, 5, 7]
然后，从左向右找到一个比枢纽值大的元素，并与之交换位置，这个元素是 9，与5交换位置后，数组变为：
[1, 3, 5, 9, 7]
然后重复上述操作，排序[1, 3] 和 [9, 7]两个序列。
序列[1, 3]， 1为枢纽值，从右向左找到一个比枢纽值1 小的元素，序列已经有序了，1 的右边值比1大，左边没有值。因为1右边序列[3] 只有一个元素，故不用排序。
序列[9, 7]，9 为枢纽值，从右向左找到一个比枢纽值9小的元素，这个元素是 7,7与9交换位置，交换后为：
[7, 9]，序列已经有序，枢纽值左边序列[7] 只有一个元素，故不用排序。
最后，得到有序序列 [1, 3, 5, 7, 9]。
递归版本：
/*快速排序算法
* l ----- 序列左边下标
* t ----- 序列右边下标
* a[] --- 排序数组
*/
int Partition(int a[], int l, int t){//使用枢纽值划分待排序序列
int idx = l + rand()%(t - l + 1);//枢纽值是随机选取的
swap(a[l], a[idx]);
int i = l;
int j = t;
int x = a[i];
while(i < j){
while(i < j && a[j] > x)
j--;
if(i < j)
a[i++] = a[j];
while(i < j && a[i] < x)
i++;
if(i < j)
a[j--] = a[i];
}
a[i] = x;
return i;
}
//递归进行划分
void Quick_Sort(int a[], int l, int t){
if(l < t){
int mid = Partition(a, l, t);//划分，返回基准值下标
Quick_Sort(a, l, mid-1);//枢纽值左边待排序序列
Quick_Sort(a, mid+1, t);//枢纽值右边待排序序列
}
}非递归版本：
//Pair存储待排序序列的第一个和最后一个坐标，
//这样就可以确定一个序列。
typedef pair<int, int> Pair;
int Partition(int a[], int lt, int rt){//以枢纽值划分待排序序列
int i = lt;
int j = rt;
int rm = i + rand()%(j - i + 1);//枢纽值随机选取
swap(a[i], a[rm]);
int x = a[i];
while(i < j){
while(i < j && a[j] > x)
j--;
if(i < j)
a[i++] = a[j];
while(i < j && a[i] < x)
i++;
if(i < j)
a[j--] = a[i];
}
a[i] = x;
return i;
}
//以栈的形式模拟递归
void Quick_Sort(int a[], int l, int t){
stack<Pair>S;
S.push(Pair(l, t));
while(!S.empty()){//使用栈模拟
int lt = S.top().first;
int rt = S.top().second;
S.pop();
int mid = Partition(a, lt, rt);
if(mid+1 < rt)
S.push(Pair(mid+1, rt));
if(lt < mid-1)
S.push(Pair(lt, mid-1));
}
}
空间复杂度：不管是递归版本，还是非递归版本，都会占用空间，复杂度为O(log2n) ~ O(n)，最好的情况是每次都是2分序列，复杂度为 O(log2n)，最差的情况是每次的枢纽值是最大值或最小值，复杂度为O(n)。
时间复杂度：平均情况下，有n个元素，栈的深度为 log2n，故总的时间复杂度为O(nlog2n)。
归并排序是一种比较快的排序算法，是一种稳定排序算法。它也是采用分而治之的思想，归并排序是先划分排序元素，每次都是二分，先不进行比较，直到划分为单个元素后。回溯的时候进行比较，作归并。
如果还不懂，没关系！接下来看一下实例演示就懂了。
下面以数组 [5, 7, 9 , 3, 1, 8，6,2] 为例进行从小到大排序的演示：
