经典排序写法,必须会!不会就背下来!
注意:为了好理解数组类型统一为int
(一)插入排序
直接插入排序
//最容易忽略的细节就是所有插入排序的数组下标都是从1开始的
//因为下标为0的地方我们用来作为哨兵/临时变量(也就是一个临时存放点)
void InsertSort(int a[],int n)
{
int i,j; //提前定义好,下面不容易出错
//初始规定第一个元素已排好序,所以i从2开始
for(i = 2;i <= n;i ++)
if(a[i] < a[i - 1]) //拿当前元素跟前面排好序的元素对比,看是否符合要求
{
a[0] = a[i]; //把当下元素放入哨兵
for(j = i - 1;a[0] < a[j];j --) //从前一个元素从后往前依次找到当前元素该放的位置
a[j + 1] = a[j]; //先前插入的过程就是元素往后挪动的过程
a[j + 1] = a[0]; //到这已经找到要插入的那个位置了,直接哨兵归位即可
}
}
折半插入排序
//所谓的折半查找就是二分法,定义一个区间三个遍历玩一套猜数字的游戏罢了
//这里把二分法加入插入排序中,就是为了在找到当前元素应该插入的位置的时候能加速,仅此而已!
//而插入排序之所以能加入二分法,就是因为整个插入的过程前面已排好序的区间适合二分法的使用!
//因为二分法的前提条件必须是有序的区间,这里我们默认为递增区间(如果题目是递减,一定要该些细节!)
void InsertSort(int a[],int n)
{
int i,j,left,right,mid; //把二分法的三个指针先定义出来(分别为区间的左,右,中指针)
for(i = 2;i <= n;i ++) //每遍历一个当前元素就默认第一个元素到当前元素为一个区间,方便二分法
{
a[0] = a[i]; //当前元素放入哨兵
left = 1; //左指针初始为区间的左端点
right = i - 1; //右指针初始为区间的右端点
while(left <= right) //二分法(默认递增有序)
{
mid = (left + right) / 2; //取区间的中间位置做分割点
if(a[mid] > a[0]) //因为我们目的是找到哨兵该插入的位置,所以哨兵就是目标元素
right = mid - 1; //哨兵在左区间
else
left = mod + 1; //哨兵在右区间(注意:这行代码保证了排序的稳定性)
}
for(j = i - 1;j >= right + 1;j --) //二分法结束以后,右端点即为要插入的地方
a[j + 1] = a[j]; //老样子,往后挪元素
a[right + 1] = a[0]; //哨兵归位
}
}
希尔排序
//"跳大步排序"就是通过不同遍历步数来分出不同的数组集合,步数越大集合越小
//然后把这些集合从小到大逐个进行插入排序,当最后一个集合也排完序了就OK了
//因为最后一个集合的步数为1,也就是整个数组!
void ShellSort(int a[],int n)
{
int i,j,k;
for(k = n/2;k >= 1;k /= 2) //k表示遍历步数,并设置步长,每一次循环都是一个集合
for(i = k + 1;i <= n;i ++)
if(a[i] < a[i - k]) //判断该集合中当前元素的前一个排好序的元素
{
a[0] = a[i]; //暂存在a[0],只作暂存单元
for(j = i - k;j > 0&&a[0] < a[j];j -= k) //这里的循环条件要防止越界
a[j + k] = a[j];//集合元素后移,找到插入的位置
a[j + k] = a[0]; //插入集合中对应的位置
}
}
(二)交换排序
冒泡排序
//冒泡排序,太简单了,我都懒得讲,自己看吧
//这里增加了一个flag,多此一举,但很有逼格!
void BubbleSort(int a[],int n)
{
for(int i = 0;i < n - 1;i ++)
{
flag = false;//这里做个标记,就是判断冒泡过程中是否出现已经排好序的情况就直接退出即可(没啥用感觉)
for(int j = n - 1;j > i;j --)
if(a[j - 1] > a[j])
{
swap(a[j - 1],a[j]);//这里也可以写成两个变量交换
flag = true;//如果出现交换就说明还待继续冒泡
}
if(flag == false) return;//没有出现交换就说明已经排好序了,直接结束程序就行了
}
}
快速排序
//这里我特别说一下:我提供的是算法分析的模板写法,可以直接背诵的
//但是应试考试要以王道书上的快速排序逻辑为主
//这个代码主要是应对出一道让你默写快速排序的大题而准备的
void quick_sort(int l , int r) //快速排序
{
if(l >= r) return;
//划分讲策略,划分不好导致递归层数太多,
//适得其反,取左右端点数据卡你就不好过,一般取中间
int i = l - 1, j = r + 1, x = q[(l + r) / 2];
while (i < j)
{
do i ++; while(q[i] < x);
do j --; while(q[j] > x);
if(i < j) swap(q[i],q[j]);
}
quick_sort(l, j);
quick_sort(j + 1, r);
}
(三)选择排序
简单选择排序
//每次定位一个元素然后交换即可,看不懂就背下来会写就行
void SelectSort(int a[],int n)
{
for(int i = 0;i < n - 1;i ++)
{
int min = i;
for(int j = i + 1;j < n;j ++)
if(a[j] < a[min])
min = j;
if(min != i) swap(a[i],a[min]);
}
}
堆排序
//这里我特别说一下:我提供的是算法分析的模板写法,可以直接背诵的
//但是应试考试要以王道书上的快速排序逻辑为主
//这个代码主要是应对出一道让你默写快速排序的大题而准备的
//堆要维护一个sz,表示堆里面时刻有多少个元素,实时更新全局变量
int sz;
void down(int u)
{
int t = u;
if(u * 2 <= sz && q[u * 2] > q[t]) t = u * 2;
if(u * 2 + 1 <= sz && q[u * 2 + 1] > q[t]) t = u * 2 + 1;
if(u != t)
{
swap(q[u], q[t]);
down(t);
}
}
void heap_sort()
{
sz = n;
for(int i = n / 2; i ; i --) down(i);
for (int i = 0; i < n - 1;i ++)
{
swap(q[1], q[sz]); //把最后一个元素放到最后
sz --; //删掉最后一个元素
down(1);
}
}
(四)归并排序(二路归并排序)
//这里我特别说一下:我提供的是算法分析的模板写法,可以直接背诵的
//但是应试考试要以王道书上的快速排序逻辑为主
//这个代码主要是应对出一道让你默写快速排序的大题而准备的
//辅助数组
int w[N];
void merge_sort(int l, int r) // 归并排序
{
if(l >= r) return;
//先分割
int mid = l + r >> 1;
merge_sort(l, mid), merge_sort(mid + 1, r);
//再二路归并
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
if(q[i] <= q[j]) w[k ++] = q[i ++];
else w[k ++] = q[j ++];
while (i <= mid) w[k ++] = q[i ++];//把左区间残余的归入
while (j <= r) w[k ++] = q[j ++];//把右区间残余的归入,这波叫做捡漏
//辅助数组归并完事就要物归原主,更新原数组
for (i = l, j = 0;j < k;i ++, j ++) q[i] = w[j];
}
要是排序理论理解不到位,可以看看我总结过得:
初级排序讲解: https://www.acwing.com/blog/content/16334/
高级排序讲解: https://www.acwing.com/blog/content/16486/
发现有问题了,及时跟我反应
返回目录:
https://www.acwing.com/file_system/file/content/whole/index/content/5976074/