蓝桥杯备考：六大排序算法

1 插入排序

算法过程

从第二个元素开始往前插入，比如第二个元素是7，我们把7存一下，然后和前面的元素比较，如果前面的元素大就把前面的元素往后移直到找到空位置插入

接下来我们把第三个元素插入到1和2的区间里面

第四个元素已经符合大小了，我们就不进行插入排序的步骤了，我们直接判断第五个元素

接着我们插入第六个元素

我们的插入排序就完成了

代码

#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N];void insert_sort(int n)
{for(int i = 2;i<=n;i++){int tmp = a[i];int j = i-1;while(j>0 && a[j]>tmp){a[j+1] = a[j];j--;}a[j+1] = tmp;}
}int main()
{int n;cin >> n;for(int i = 1;i<=n;i++){cin >> a[i];}insert_sort(n);for(int i = 1;i<=n;i++){cout << a[i] << " ";}
}

时间复杂度

最优的时间复杂度是O（n）也就是当我们的一组数是有序的时候，比如【1，2，3，4，5】我们只需要遍历一遍这组数，但是并没有进行插入操作

最差的时间复杂度是O（n²）也就是当我们的一组数是无序的时候，比如【5，4，3，2，1】，我们把4进行插入的时候需要比较1次，把3插入的时候需要比较两次，把2插入需要比较三次，把1插入需要比较四次，也就是说一组数有5个的话，程序执行1+2+3+4次操作，如果一组数有n个，我们就要执行1+2+3+...+n-1也就是(1+n-1)*n-1次，时间复杂度也就是n的平方次

2 冒泡排序

算法过程

冒泡排序的过程就是每次把最大的元素冒到最后，我们会执行n-1次，每次把最大的元素冒在最后

如果是逆序就交换

接下来我们冒第二大的数W

冒第三大的数

冒第四大的数

冒第五大的数

冒最后倒数第二大的数，结束！

代码

#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N];void bubble_sort(int n)
{int flag = 0;//依次枚举排序区间的最后一个元素 for(int i = n;i>=1;i--){for(int j = 1;j<i;j++){if(a[j]>a[j+1]){swap(a[j],a[j+1]);flag = 1;}}if(!flag) break;}
}int main()
{int n;cin >> n;for(int i = 1;i<=n;i++){cin >> a[i];}bubble_sort(n);for(int i = 1;i<=n;i++){cout << a[i] << " ";}
}

时间复杂度

比如我们的[1,2,3,4,5,6]我们优化后的冒泡排序会从1和2比较，2和3比较，3和4比较，。。。5和6比较，比较完之后没有发生交换直接结束了，所以我们的时间复杂度就是O（N）

但是我们的[6,5,4,3,2,1]就会先比较5次，变成5 4 3 2 1 6 再比较4次，变成 4 3 2 1 5 6 再比较 3次变成 3 2 1 4 5 6 再比较2次，变成 2 1 3 4 5 6，再比较1次变成 1 2 3 4 5 6 也就是说一共会比较1+2+3+4+5次，如果是n个元素就是1+。。。+n-1 也就是O（n²）的时间复杂度

3 选择排序

算法过程

每次从未排序序列中找出最小的那个数，放在有序的序列的后面，一直尾插

当前，整个数组都是待排序区间，我们遍历数组找到最小的元素，和第一个位置交换

接着，我们再从待排序区间里找出最小元素放在2的位置上

接着我们再从待排序元素里找到最小的放在3的位置上，因为25已经是最小的了，所以不需要变化

这样，待排序区间就只剩下5，6，7了，再找到这三个元素里最小的元素放在5的位置上

接下来我们找到6，7里最小的元素放在6的位置上，排序完成

代码

#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N];void select_sort(int n)
{for(int i = 1;i<n;i++){int pos = i;for(int j = i+1;j<=n;j++){if(a[j]<a[pos])pos = j;}swap(a[pos],a[i]);}
}int main()
{int n;cin >> n;for(int i = 1;i<=n;i++){cin >> a[i];}select_sort(n);for(int i = 1;i<=n;i++){cout << a[i] << " ";}
}

时间复杂度

无论是什么情况，选择排序的时间复杂度都是O（N²）级别的，就算我们这一组数是有序的，比如说是【1，2，3，4，5】我们先会执行5次遍历这五个元素找出最小的，然后放在第一个位置，也就是自己和自己交换了，然后待排序区间就是【2，3，4，5】，我们继续执行四次遍历这四个元素找出最小的放在2的位置上，待排序区间变成【3，4，5】接着我们执行三次找到最小元素放在3这个位置，待排序区间变成【4，5】我们执行两次找到最小元素放在4这个位置，排序完成，所以我们5个元素的执行次数就是2+3+4+5，n个元素就是2+....+n，也就是o（n²）级别的

4 堆排序

算法过程

我们的堆排序要比上面三个排序都强很多！

堆排序分为两步，第一步是建堆，第二步是排序

建堆就是从倒数第一个非叶子结点开始向下调整，一直到根结点，我们建堆就完成了

排序就是我们先把堆顶元素和最后一个元素交换，堆的大小减1，然后堆顶向下调整

很明显第一个非叶子结点是49，我们从49开始向下调整

再从50进行向下调整

再从25进行向下调整

接下来从16向下调整

我们的建堆操作完成，接下来就是排序

先把堆顶57和待排序区间最后的元素交换位置，然后堆的大小减1

这时候最后一个元素就排好了，我们继续从16向下调整，

接下来我们再把堆顶元素50和堆的最后元素的位置交换，堆的大小减1

接下来继续进行向下调整操作

我们继续把堆顶和堆尾交换，然后大小减1向下调整

继续进行操作

继续直到堆里只剩下一个元素，我们的排序就算是结束了

代码

#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N];
void down(int parent,int len)
{int child = parent*2;while(child <= len){if(child+1<=len && a[child+1] > a[child]) child++;if(a[parent] > a[child]) return;swap(a[child],a[parent]);parent = child;child = parent*2;}
}
void heap_sort(int a[],int n)
{//建堆for(int i = n/2;i>0;i--){down(i,n);} //排序(枚举最后一个元素）for(int i = n;i>1;i--){swap(a[1],a[i]);down(1,i-1);} 
}
int main()
{int n;cin >> n;for(int i = 1;i<=n;i++) cin >> a[i]; heap_sort(a,n);for(int i = 1;i<=n;i++){cout << a[i] << " ";}return 0;
}

时间复杂度

所以我们建堆时间复杂度的式子就是

我们排序时间复杂度

根据这段代码，我们依次枚举堆里最后一个元素，一共是n-1次，每次都进行向下调整log（n+1)

所以我们的时间复杂度就是O（N+N*logN）也就是O（N*logN）

5快速排序

算法过程

找一个基准元素，把待排序元素根据基准元素分成两部分.

继续递归左区间和右区间直到长度为1的时候根据33这个基准元素分左右区间

如图，我们的排序就完成了

当然我们的朴素排序是存在一些问题的，1.我们的基准元素选的不恰当的时候

我们的递归层数就变成N层了

还有一种情况就是2,重复元素太多也会导致

代码

我们在代码里修复这些问题，修复问题1.用C++标准里的随机函数来获取每个基准值

问题2.用三路划分，荷兰旗问题

#include <iostream>
#include <ctime>
#include <algorithm>
using namespace std;
const int N = 1e5+10;
int a[N];
int get_random(int left,int right)
{//比如区间是[2，4] 我们产生随机值也要在这之间，//rand%3,就是[0,2]再加上2就是【2，4】所以我们要得到随机值只要模长度再加左区间就行了 return a[rand()%(right-left+1) +left];
}
void quick_sort(int left,int right)
{if (left >= right) return;int p = get_random(left,right);int l = left-1,i=left,r = right+1;while(i < r){if(a[i] < p) swap(a[++l],a[i++]);else if(a[i] == p) i++;else swap(a[--r],a[i]);}quick_sort(left,l);quick_sort(r,right);}
int main()
{srand(time(0));int n;cin >> n;for(int i = 1;i<=n;i++) cin >> a[i];quick_sort(1,n);for(int i = 1;i<=n;i++) cout << a[i] << " ";
}

时间复杂度

一般情况下递归层数是logN，三路划分时间复杂度是N 总体时间复杂度是O（N*logN）

但是极端情况下（基准元素选择不恰当）就是O（N²）了

6.归并排序

算法过程

我们的归并排序分成两步，每次分成左右区间，对左右区间进行排序，然后合并左右区间向上返回

这会用到我们有序数组合并的知识，我们需要开辟一个临时数组

左区间递归

左区间合并完毕

右区间递归

右区间合并完毕

接下来把这左右两个区间合并，排序完成

代码

#include <iostream>
using namespace std;
const int N = 1e5+10;
int a[N];
int tmp[N];
void merge_sort(int left,int right)
{int mid = (left+right) >> 1;if(left>=right) return;merge_sort(left,mid);merge_sort(mid+1,right);int cur1 = left,cur2 = mid+1,i = left;while(cur1<=mid && cur2<=right){if(a[cur1] < a[cur2]) tmp[i++] = a[cur1++];else tmp[i++] = a[cur2++]; }while(cur1<=mid) tmp[i++] = a[cur1++];while(cur2<=right) tmp[i++] = a[cur2++];for(int j = left;j<=right;j++){a[j] = tmp[j];}}
int main()
{int n;cin >> n;for(int i = 1;i<=n;i++) cin >> a[i];merge_sort(1,n);for(int i = 1;i<=n;i++) cout << a[i] << " ";return 0;
}

时间复杂度

递归是一颗完全二叉树，分布很均匀，所以递归层数是logN，再因为数组合并的时间复杂度是N所以整体时间复杂度是O（N*logN）