阅前提示
- 本文数组下标均从1开始
- 本文数组排序默认为升序 特殊情况会有说明
- 算法稳定性:在一组待排序记录中,如果存在任意两个相等的记录 R 和 S,且在待排序记录中 R 在 S 前,如果在排序后 R 依然在 S 前,即它们的前后位置在排序前后不发生改变,则称为排序算法为稳定的。
参考文章
插入排序
1.直接插入排序
空间复杂度 $O(1)$
最优时间复杂度 $O(n)$ 初始为有序
最坏时间复杂度 $O(n^2)$ 初始为倒序
平均时间发制度 $O(n^2)$
稳定
void insert_sort(int a[],int n){
//视1~i-1有序 将i插入到1~i-1中合适的位置
//比a[i]大的整体向后移动一位
for (int i=2,j;i<=n;i++){//默认1~i-1有序
int x=a[i];
for (j=i-1;j>=0&&x<a[j];j--){//找不到<=a[i]的就一直向前
a[j+1]=a[j];//向后移动一位
}
a[j+1]=x;//找到了 赋值 放在<=a[i]的数后面
}
}
2.折半插入排序
空间复杂度 $O(1)$
最优时间复杂度 $O(n)$ 初始为有序
最坏时间复杂度 $O(n^2)$ 初始为倒序
平均时间复杂度 $O(n^2)$
虽然查找时间变为了$O(log_2n)$但移动仍然是$O(n)$
稳定
void insert_sort_by2(int a[],int n){
//只是在查找上优化成二分的直接插入排序
for (int i=2,j;i<=n;i++){//默认1~i-1有序
int x=a[i];
int l=0,r=i-1;
//注意边界哦 l=0避免出现a[i]是最小的 r=i-1有序序列的边界是[1,i-1]
while (l<r){//找到最后一个<=a[i]的数
int mid=l+r+1>>1;
if (a[mid]<=x) l=mid;
else r=mid-1;
}
//通通向后移动一位
for (int j=i-1;j>=l;j--) a[j+1]=a[j];
a[l+1]=x;
}
}
3.希尔排序
空间复杂度 $O(1)$
最优时间复杂度 $O(n^1.3)$
最坏时间复杂度 $O(n^2)$
希尔排序性能分析复杂 不需要掌握 只要知道是不稳定算法即可
不稳定 因为同样大小的元素可能不在一个组内,相对位置可能会变换
void shell_sort(int a[],int n){
//给定一个d 对L[i,i+d,d+2d+...,i+kd]进行直接插入排序
//d=1时 排序完成
//本函数d从n/2开始
//初始卷子上一般会给d 然后让模拟
for (int d=n/2;d>=1;d/=2){
for (int i=1+d,j;i<=n;i++){//和直接插入排序一样 默认1~i-d有序
int x=a[i];
for (j=i-d;j>=0&&x<a[j];j-=d){//往后少稍稍
a[j+d]=a[j];
}
a[j+d]=x;
}
}
}
交换排序
1.冒泡排序
空间复杂度 $O(1)$只使用了常数的辅助空间
最优时间复杂度 $O(n)$ 有序
最坏时间复杂度 $O(n^2)$ 倒序
平均复杂度 $O(n^2)$
稳定
void bulble_sort(int a[],int n){
//从n开始 像冒泡泡一样 把[i+1,n]中最小的数一位一位交换到i+1
bool flag;
for (int i=0;i<n-1;i++){//趟数
flag=0;
for (int j=n;j>i;j--){//当前趟
if (a[j-1]>a[j]){
swap(a[j-1],a[j]);
flag=1;
}
}
if (flag==0) return ;//说明未发生交换 意味着所有元素已经有序
}
}
2.快速排序
边界问题看这里
空间复杂度 $O(log_2n)$ 递归栈深度
最优时间复杂度 $O(nlog_2n)$ 选中的枢轴可将数分成两部分
最坏时间复杂度 $O(n^2)$ 选中的枢轴是最大或最小的 此时 空间复杂度还变成了$O(n)$
平均复杂度 $O(nlog_2n)$
不稳定
void quick_sort(int a[],int l,int r){
//快速排序 先排再分 本函数以中间位置的元素为枢纽
//将区间内元素分为大于x和小于x的
if (l>=r) return ;
int i=l-1,j=r+1,x=a[l+r>>1];
while (i<j){
do i++;while (x>a[i]);//遇到>=x的会停下
do j--;while (x<a[j]);//遇到<=x的会停下
if (i<j) swap(a[i],a[j]);
}
//这里出来时i>=j
quick_sort(a,l,j),quick_sort(a,j+1,r);
//结束时i在j的右边 j是左半段的终点,i是右半段的起点
//为什么是j可以看上面的链接 分析边界问题
}
选择排序
1.简单选择排序
空间复杂度 $O(1)$只使用了常数的辅助空间
最优时间复杂度 $O(n^2)$
最坏时间复杂度 $O(n^2)$
平均复杂度 $O(n^2)$
选择排序的移动次数很少 同时 比较次数与初始状态无关 所以最优最坏都是$O(n^2)$
不稳定 找到第i大的元素,和位置i交换位置 可能会发生位置变换
void select_sort(int a[],int n){
// 选一个最小的 插上
// 1~i为有序序列 i+1~n为无序序列
// 在[i+1,n]中找到最小的 交换到i+1的位置上
int j,min;
for (int i=1;i<n;i++){
min=j;//min j是下标
for (int j=i+1;j<=n;j++){//找到最小值下标
if (a[j]<a[min]) min=j;
}
if (min!=j){
swap(a[i],a[min]);
}
}
}
2.堆排序
空间复杂度 $O(1)$
最优时间复杂度 $O(nlog_2n)$
最坏时间复杂度 $O(nlog_2n)$
平均复杂度 $O(nlog_2n)$
不稳定
每次堆排序都要先建堆$O(n)$然后再调整n-1次每次调整时间复杂度都是$O(log_2n)$
所以时间复杂度为$O(n)+(n-1)*O(log_2n)=O(nlog_2n)$
$\color{red}{对序列进行升序排列用大根堆!}$
$\color{red}{对序列进行降序排列用小根堆!}$
下面是迭代实现down 操作 更适合笔试
y总的递归down更适合上机题
int a[100010],n,cnt;
void down(int a[],int k,int len){//k是节点下标 len是堆的元素个数
//默认除k结点外其他已经有序
//将以k为根结点的树调整为大根堆
int x=a[k];//存当前以k为根节点的子树堆顶
for (int i=k*2;i<=len;i*=2){//i*2 进入叶节点
if (i<len&&a[i]<a[i+1]) i++;
//i<len判断有无右兄弟
if (x>=a[i]) break;
//堆顶不用调整
else {//堆顶要调整
a[k]=a[i];//先给堆顶更新值
k=i;//再记录要交换的点
//这个过程其实是递归地 因为是从最后一个非叶子节点开始down
//使得默认除k结点外其他已经有序 的条件成立
}
}
a[k]=x;//赋堆顶
}
void build_heap(int a[],int n){
for (int i=n/2;i>=1;i--) down(a,i,n);
//从最后一个非叶子节点开始down
}
void heap_sort(int a[],int cnt){//l是堆顶下标 cnt是堆的元素个数
build_heap(a,cnt);
for (int i=cnt;i>1;i--){
//删除堆顶 down 循环往复
swap(a[1],a[i]);
//堆的删除就是 将堆顶与最后一个节点交换
down(a,1,i-1);//已经删除了 所以总节点数是i-1
}
}
归并排序
空间复杂度 $O(n)$
最优时间复杂度 $O(nlog_2n)$
最坏时间复杂度 $O(nlog_2n)$
平均复杂度 $O(nlog_2n)$
稳定
每趟所有元素都得遍历一遍 是$O(n)$ 要进行ceil($log_2n$)趟
故复杂度为$O(nlog_2n)$
void merge_sort(int a[],int l,int r){
if (l>=r) return ;
int mid=l+r>>1,i=l,j=mid+1,k=1;
merge_sort(a,l,j-1),merge_sort(a,j,r);
//注意边界
//先排好序 再合并
while (i<=mid&&j<=r){
//合并流程是 两个相邻的有序表双指针扫描
//哪个小哪个先进辅助数组
if (a[i]<a[j]) t[k++]=a[i++];
else t[k++]=a[j++];
}
//根据上面while循环的执行条件 下面只会执行一个while
//且因为俩部分都是有序的 一个表走完了意味着
//没走完的表剩下的数都比走完的表内的数大 顺序接上就行
while (i<=mid) t[k++]=a[i++];
while (j<=r) t[k++]=a[j++];
for (int i=l,j=1;i<=r;) a[i++]=t[j++];
//在从辅助数组取出 赋值赋回去
}
蓬蒿佬orz