上海青浦做网站公司,深圳入户申请网站官网,不懂外贸做外贸网站好做吗,网站开发还找到工作吗目录
基本排序
一.冒泡排序
二.选择排序
三.插入排序 进阶排序#xff08;递归实现#xff09;
一.快排hoare排序
1.单趟排序
快排步凑
快排的优化
#xff08;1#xff09;三数取中
#xff08;2#xff09;小区间优化
二.前后指针法(递归实现)
三.快排的非…目录
基本排序
一.冒泡排序
二.选择排序
三.插入排序 进阶排序递归实现
一.快排hoare排序
1.单趟排序
快排步凑
快排的优化
1三数取中
2小区间优化
二.前后指针法(递归实现)
三.快排的非递归实现(前后指针法的非递归)
快排的挖坑法的实现
二.堆排序
1.建堆的选择
2.堆排序的实现
二希尔排序
三.归并排序(递归实现与非递归的实现)
归并排序非递归实现
四.非比较排序(计数排序)
计数排序的缺陷
五.排序总结
稳定性的概念
六,排序的选择题练习与巩固 欢迎各位大佬的关顾能给个赞就好了QWQ由于篇幅很大可以根据目录跳转你想看的排序哦 基本排序
一.冒泡排序
冒泡排序即每次相邻比较排序每次将最小或最大固定在数组最后
void BubbleSort(int* arr, int len)
{for (int i 0; i len; i){int flag 1;for (int j 0; j len - i-1; j){if (arr[j] arr[j1]){flag 0;Swap(arr[j 1],arr[j]);}}if (flag)break;}
} 二.选择排序 很明显选择排序就是去找最小或者最大的下标然后赋值给原始位置,代码实现如下
void SelectSort(int* arr, int len)
{for (int i 0; i len-1; i){int min i;for (int j i 1; j len; j){if (arr[j] arr[min])min j;}Swap(arr[min], arr[i]);}
}
但是这种选择排序也太low了让我们来实现一个Plus版本一次循环找到最大与最小
int SelectSortPlus(int* arr, int len)
{int begin 0;int end len - 1;for (int i begin; i end-1; i){int min begin;int max begin;for (int j i1; j end; j){if (arr[j] arr[min])min j;if (arr[j] arr[max])max j;}Swap(arr[begin], arr[min]);if (begin max)//注意这里当begin与max的下标一样的时候会被先换导致bugmax min;Swap(arr[end], arr[max]);begin;end--;}
}
三.插入排序 看动图可以很容易的理解插入排序就是将已排好的序的后一个与前面的进行比较比它大或小的往后移动
void InsertSort(int* a, int len)
{for (int i 0; i len - 1; i){int end i;int temp a[end 1];while (end 0){if (temp a[end]){a[end 1] a[end];end--;}else{break;}a[end 1] temp;}}
} 进阶排序递归实现
一.快排hoare排序
快排有着多种实现方式我们下面这个是hoare创始人的排序方式
快速排序是一种高效的排序现在来让我们来实现一下
1.单趟排序
想要写出一个排序首先我们要去理解这个排序的单趟 单趟如图所示 如图我们可以发现它的步骤如下
快排步凑
(1)选出基准值key 为 left
2右边r先走找到比key小的停止
(3)右边r找到的情况下,左边L再开始找比key大的值
3左边L找到的情况下停止将这两个值进行交换
循环上面的操作
直到他们相遇将相遇的位置的值与key值交换
这就是快排的单趟排序接下来让我们来实现一下
void QuickSort2(int* arr, int left, int right)
{int key left;int begin left;int end right;while (begin end){//先从右边开始找小 //注意结束条件 begin一定endwhile (begin end arr[end] arr[key]){--end;}//再从左边找大while (begin end arr[begin] arr[key]){begin;}//两边都找到了之后进行交换Swap(arr[begin], arr[end]);}//最后相遇再与key交换Swap(arr[begin], arr[key]);}
}
想必这里大家会有一些疑问为什么
1.为什么要右边先走左边先走可以吗
2.为什么最后交换key的位置就固定了
3.要怎么样才能实现排序的效果 循环的实现既然单趟可以固定住key值在整个数里面的想要排序的位置那我们可不可以将这个数组进行分割[left~key-1]key[key1~right] 运用递归来实现呢
答案是肯定的
只需要每次递归进行分割固定n的值的位置如下图所示 如图所示很明显当我们进行递归的时候每次的位置都将被固定,从而实现了排序
代码如下
void QuickSort2(int* arr, int left, int right)
{//返回条件if (left right)return;int key left;int begin left;int end right;while (begin end){//先从右边开始找小 //注意结束条件 begin一定endwhile (begin end arr[end] arr[key]){--end;}//再从左边找大while (begin end arr[begin] arr[key]){begin;}//两边都找到了之后进行交换Swap(arr[begin], arr[end]);}//最后相遇再与key交换Swap(arr[begin], arr[key]);//递归排序分割成两份//[left~key-1] key [key1~right]最后相遇的指针也是一样的QuickSort2(arr, left, end - 1);QuickSort2(arr, end 1, right);
}
到这里我们也就完成了阉割版的快排但是距离真正的快排还是有些距离
现在的这个排序有着致命的缺陷如果说在数组已经是有些的情况下快排的将会退化就像是二叉树退化为单叉树一样如果我们这时还去递归那就会有爆栈栈溢出的风险原因很简单
如下图所示 如果是有序的情况下那么递归的深度将会变成n如果数据量太大将会爆栈 所以接下来要去实现一下三数取中小区间优化来对递归快排进行优化
快排的优化
1三数取中
选择key值进行,key值的选择就是为了避免这种有序情况的出现因为选key固定key的位值我们只需要找到中间的那个数进行固定区间递归的高度将会变为解决了爆栈的风险
int GetMid2(int* arr, int left, int right)
{//三个数进行比较 分类讨论int mid (left right) / 2;if (arr[left] arr[mid]){if (arr[mid] arr[right]){return mid;}//arr[mid]arr[right]else if (arr[right] arr[left]){return left;}else{return right;}}else//arr[left] arr[mid]{if (arr[mid] arr[right]){return mid;}//arr[righ]arr[mid]else if (arr[right]arr[left]){return left;}else{return right;}}
}
2小区间优化
什么是小区间优化在我们进行快排的时候如果每次的区间都能二分的化这个递归的过程是可以看出一颗二叉树而在满二叉树的叶子节点个数为整棵树的一半对于快排来说它的最后一层和倒数第二层是不用去排和只排一个数的但是却还要开辟栈帧所以我们这里使用小区间优化带代码如下直接使用当区间小于10时进行插入排序 //小区间优化 提升效率节省空间
if ((right - left 1) 10)//减少递归次数
{//加上偏移量leftInsertSort(arrleft, right - left 1);
}
else
{//进行递归
} 注意事项 二.前后指针法(递归实现)
由于hoare版本的有些复杂要去考虑什么右边先走之类的所以又有人想出了更加简单跟容易理解的办法前后指针法过程如图所示 可以发现与hoare版本大体一致都是去选择key与key比较,不同点在于,只有是cur去找比key小的值当找到比key小的值的时候prev然后与cur位置的值进行交换最后当cur走到最后prev的值再与key位置的值进行交换比起hoare版本简单了许多接下来我们来尝试实现一下
void QuickSortByPointer(int* arr, int left, int right)
{if (left right)return;//三数取中int mid GitMid(arr,left,right);Swap(arr[mid], arr[left]);int key left;int prev left;int cur prev1;//三数取中if ((right - left 1) 10){InsertSort(arrleft, right - left 1);//加上left}else{while (cur right){if (arr[key] arr[cur]prev ! cur)//为什么要写成这样Swap(arr[prev], arr[cur]);cur;}Swap(arr[prev], arr[key]);//区间变为[0,prev-1]prev[prev1,right]QuickSortByPointer(arr, left, prev - 1);//值给错了应该是leftQuickSortByPointer(arr, prev 1, right);}
}
你以为到这里快排就结束了嘛其实还是马达马达得是(远远没有结束),虽然我们加上三数取中与小区间的优化但是如果数据量过大还是会有爆栈的风险栈的空间比较小所以我们可以使用数据结构的栈来模拟实现程序中的压栈与出栈由于是在堆中建立内存巨大,8G的内存不可能溢出把
三.快排的非递归实现(前后指针法的非递归)
可以看见我们先是将每次的单次排序进行封装的
我们可以想象一下在程序中栈帧的建立与销毁的过程然后我们也可以自己使用数据结构的栈来实现 快排其实是可以看作二叉树的前序遍历的但是栈又是后进先出想要先得到左边界的值就需要先进右边想要得到右边界的值就需要先进左边
void QuickSortNoR(int* arr, int begin, int end)
{Stack st;CreatStack(st);StackPush(st, end);StackPush(st, begin);while (StackGetSize(st)!0){int left StackPop(st);//我的Pop是即出又返回栈顶元素的因为后进先出想要先得到left进右int right StackPop(st);//小区间优化if ((right - left 1) / 2 10)InsertSort(arr left, right - left 1);else{//开始模拟递归int key PartPointer(arr, left, right);//这个函数是每一次的单趟排序if (key 1 right)//进行递归由于后进先出 先进右区间{StackPush(st, right);//后进先出由于我们的右区间是后出 所以先进StackPush(st, key 1);}if (left key - 1)//注意错误之处区间不要写错了{StackPush(st, key - 1);StackPush(st, left);}}}
}
int PartPointer(int* arr, int left, int right)
{//三数取中int mid GitMid(arr, left, right);Swap(arr[mid], arr[left]);int key left;int prev left;int cur prev 1;while (cur right){if (arr[key] arr[cur])Swap(arr[prev], arr[cur]);cur;}Swap(arr[prev], arr[key]);return prev;//返回key的位置 prev就是key中间值 然后进行区间的分割同上
}
快排的挖坑法的实现
由于篇幅有限这里不在过多讲解 int PartSort2(int* a, int begin, int end)
{//begin是坑int key a[begin];while (begin end){while (begin end a[end] key)--end;// end给begin这个坑end就变成了新的坑。a[begin] a[end];while (begin end a[begin] key)begin;// end给begin这个坑begin就变成了新的坑。a[end] a[begin];}a[begin] key;return begin;
}
二.堆排序
学习完了快排接下来学习堆首先我们要知道堆的概念 堆在逻辑结构上是一个完全二叉树在物理结构上是一个数组 想要找到儿子节点就是(parent-1)/2 想要找到父亲节点就是child*21 如果想要深入理解堆可以看我的这一篇博客堆的实现与堆排序纯C语言版-CSDN博客
1.建堆的选择 当我们想要进行排序的时候首先要模拟堆的插入过程进行建堆这里有个问题如果想要降序排列那么应该建小堆还是大堆呢在我刚开学学习的时候想的是肯定是建大堆啊因为这样根节点就是最大的然后再出堆,其实这样想就错了这样只是出堆降序不是数组本身进行了降序排列所以降序是其实是建小堆升序其实是建大堆.那又是怎么实现的呢
2.堆排序的实现
在进行建堆之后小堆降序来举例我们就只需要模拟出堆这时每次最小的数就被放在了最后的位置,最后完成排序后整个数据就有序,如图当我们想要升序排列的时候建大堆 下面是完整的代码 void HeapSort(int* a, int max)//max为最大个数
{//建队for (int i 0; i max; i){AdjustUp(a, i);//模拟插入建小堆}//排序int end max - 1;//找到最后一个元素的下标进行交换while (end0){Swap(a[0], a[end]);AdjustDown(a, 0, end);--end;//最后的有序不在排序}
}
其实第一步建堆算法还没有做到极致,还可以倒着向下调整,这样的时间复杂度更低
//建堆法2
for (int i (max - 1 - 1) / 2; i 0; i--)//找到第一个非叶子结点 倒着进行想下调整
{AdjustDown(a, i, max-1);
} 二希尔排序
希尔排序是一个时间复杂度大约为的排序算法
它其实就是运用的插入排序
它的排序可以分为2步
1.预排序分为gap组进行
2.当gap1时即为选择排序
希尔排序的实质就是如果在排一个升序的数组如果大的在很前面每次就是一步一步的移动而当有了gap之后移动的步长将会变大大的数将会以更快的速度移到后面 我们将插入排序来进行一下比较
void InsertSort(int* a, int len)
{for (int i 0; i len - 1; i){int end i;int temp a[end 1];while (end 0){if (temp a[end]){a[end 1] a[end];end--;}else{break;}a[end 1] temp;}}
}
可以看见在进行插入排序的时候此时的步长gap为1每次只会往后面进行一步所以我们这里只需去改变想要排序的步长即可
下面是代码的实现
void ShellSort(int* a, int n)
{int gap n;while (gap 1){// 1保证最后一个gap一定是1// gap 1时是预排序// gap 1时是插入排序gap gap / 3 1;for (size_t i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (tmp a[end]){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}
}
我们可以发现我们上面是一组一组来排序
也可以多组并走都是一样的
三.归并排序(递归实现与非递归的实现)
归并排序的思想就是分治法(分而治之),如图所示 首先我们要创建一个临时的数组
运用了二叉树的后序遍历的思维先将数组拆分拆分后的数组又来进行合并在进行合并的两个数组分别有序只需要比较一次将小的放入到临时的数组当中放完成后再拷贝回去完成排序
重点就是在进行合并的时候两个数组是有序的 让我们来实现一下 l
000lkklkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkkklkkkkkkkkkkkkkkkkkkkkkkkk 222
代码如下
void MergeSort(int* arr, int len)
{int* temp (int*)malloc(sizeof(int) * len);_MergeSort(arr,temp,0,len-1);free(temp);temp NULL;
}
void _MergeSort(int* arr, int* temp, int left, int right)
{//返回条件if (left right)return;//进行递归//分成[left mid][mid1,right]不能写成[left mid-1][mid,right]分区间的时候将会出现问题//单趟排序 将左右区间看作有序数组 进行比较放入temp数组中int mid (left right) / 2;//[left mid][mid1,right]int begin1 left;int begin2 mid 1;int end1 mid;int end2 right;_MergeSort(arr, temp, begin1, end1);//左区间_MergeSort(arr, temp, begin2, end2);//右区间int i 0;while (begin1 end1 begin2 end2){if (arr[begin1] arr[begin2]){temp[i] arr[begin1];}else//直接else{temp[i] arr[begin2];}}//循环结束后还有元素全部放后面while (begin1 end1){temp[i] arr[begin1];}//循环结束后还有元素全部放后面while (begin2 end2){temp[i] arr[begin2];}//进行拷贝回去memcpy(arrleft, temp, i*sizeof(int));
}
归并排序非递归实现
想要实现归并的非递归我们是否还需要像快排一样去模拟栈呢当我们取模拟栈的时候由于归并的递归是一个后序遍历而栈无法去记录值所以使用栈就要用两个较为麻烦使用我们直接用下面这种思想 由上面递归实现的归并排序很容易想其中的gap为每个小组的个数
但是好像还有一个问题数组越界的问题 当我们使用了上面的数据进行分组的时候所以我们要进行区间的判断
加入
if (begin2 len - 1)//begin2已经越界,说明只有一组了没必要再排
{break;
}
if (end2 len - 1)//end2越界了进行修正即可
{end2 len - 1;
} 完整的代码如下
void MergeSortNonR(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}// gap每组归并数据的数据个数int gap 1;while (gap n){for (int i 0; i n; i 2 * gap){// [begin1, end1][begin2, end2]int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;//printf([%d,%d][%d,%d] , begin1, end1, begin2, end2);// 第二组都越界不存在这一组就不需要归并if (begin2 n)break;// 第二的组begin2没越界end2越界了需要修正一下继续归并if (end2 n)end2 n - 1;int j i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2])//注意等号这样才会稳定{tmp[j] a[begin1];}else{tmp[j] a[begin2];} }while (begin1 end1){tmp[j] a[begin1];}while (begin2 end2){tmp[j] a[begin2];}memcpy(a i, tmp i, sizeof(int) * (end2 - i 1));}//memcpy(a , tmp , sizeof(int) *n );//printf(\n);gap * 2;}free(tmp);tmp NULL;
}
四.非比较排序(计数排序)
接下来让我们来学习最后一个排序这个排序的特点是非比较的排序通过建立一个数组来存放数组中每个数出现的次数来实现排序 首先来思考我们想要开辟的数组的大小那是否就是原数组的长度大小呢因为要存储每个元素出现的次数那么我们开辟数组必须是连续的在开辟数组长度大小的时候有个细节如果每次都从0开始建立计数数组那如果遇到一个最小值为99最大值为110的数组那我们还是需要从0开始建立数组前面明明一个数都没有出现但是我们却还是去开辟的数组浪费了很多的空间所以我们只需要去找到最大与最小的那个值计算出rang最大值-最小值1注意要加一所以计数数数组的大小为rang那我们在进行计数的时候就只需要进行-min就可以了
然后是进行排序当计数数组里不为0说明当前位置有映射值进行自减1.加上min赋值给原数组实现排序效果 代码如下
void CountSort2(int* arr, int len)
{//找到原数组的最大与最小值int min arr[0];int max arr[len - 1];for (int i 0; i len; i){if (arr[i] min){min arr[i];}if (arr[i] max){max arr[i];}}int rang max - min 1;//开辟计数数组 注意这里要初始化开辟的计数数组 这样奇计数数组才全是0int* count (int*)calloc(rang,sizeof(int) * rang);//进行计数for (int i 0; i len; i){count[arr[i] - min];}//进行排序int j 0;for (int i 0; i rang; i){while (count[i]--)//当count[i]的元素不为0的时候说明当前映射有值{arr[j] i min;}}}
计数排序的缺陷
既然计数排序是一种映射的方法所以是只能对整数进行排列的
五.排序总结
学习完了上面的排序现在我们来进行一下总结 排序 平局时间复杂度 最坏时间复杂度 最好时间复杂度 稳定性 冒泡排序 O() O() O() 稳定 选择排序 O() O() O() 不稳定 插入排序 O() O() O() 稳定 希尔排序 O() O() O() 不稳定 堆排序 O() O()O() 不稳定 快速排序 O() O() O() 不稳定 归并排序 O() O() O() 稳定 稳定性的概念
上表的稳定性是什么意思其实就是相同数据的前后位置是否发生改变如下面红色5与蓝色5当排序完成后红色5还在蓝色5前面就是稳定的 六,排序的选择题练习与巩固
学完上面的知识不来两道题检测一下是不知道自己真正掌握了没有的下面让我们来做几道题加深一下印象。 1.用某种排序方法对关键字序列 25 84 21 47 15 27 68 35 20 进行排序序列的变化情况采样如下 20 15 21 25 47 27 68 35 84 15 20 21 25 35 27 47 68 84 15 20 21 25 27 35 47 68 84 请问采用的是以下哪种排序算法 A.选择排序 B.希尔排序 C.归并排序 D.快速排序 答案D 解析 此题中的排序是快排二分排序的思想第一趟的基准值是25第二趟的基准值分别是2047第三趟的基准值分别是15213568 2.下面的排序算法中初始数据集的排列顺序对算法的性能无影响的有 ① 快速排序 ② 希尔排序 ③ 插入排序 ④ 堆排序 ⑤ 归并排序 ⑥ 选择排序 A.①④⑤ B.④⑤⑥ C.②③⑥ D.②③⑤⑥ 答案B 解析 快排 初始顺序影响较大有序是性能最差 插入: 接近有序性能最好 希尔希尔是对插入排序的优化这种优化是在无序的序列中才有明显的效果如果序列接近有序反而是插入最优。 堆排归并选择对初始顺序不敏感 3.下列排序方法中每一趟排序结束时都至少能够确定一个元素最终位置的方法是 ① 选择排序 ② 归并排序 ③ 快速排序 ④ 堆排序 A.①④ B.①②④ C.①③④ D.①②③④ 答案C 解析 选择排序每次选一个最值放在最终的位置 快速排序每次基准值的位置也可以确定 堆排序每次堆顶元素的位置也可以确定 所以这三种方法都可以每次至少确定一个元素的位置 而归并排序每次都需要对n个元素重新确定位置所以不能保证每次都能确定一个元素位置有可能每次排序所有元素的位置都为发生变化。 4.现有数字序列 5 11 7 2 3 17目前要通过堆排序进行降序排序那么由该序列建立的初始堆应为 A.2 3 7 11 5 17 B.17 11 7 2 3 5 C.17 11 7 5 3 2 D.2 3 5 7 11 17 答案A 解析 要降序排列所以要建小堆每次把堆顶元素放在当前堆的最后一个位置 建堆要进行向下调整算法从最后一个非叶子节点开始进行向下调整算法直到根元素 5 11 7 2 3 17 5 2 7 11 3 17 2 3 7 11 5 17 所以初始堆序列为 2 3 7 11 5 17 5.下列选项中不可能是快速排序第2趟排序后的结果的是 A.2 3 5 4 6 7 9 B.2 7 5 6 4 3 9 C.3 2 5 4 7 6 9 D.4 2 3 5 7 6 9 答案C 解析 这里说的是快排的第二趟即在第一趟快排的结果的基础上进行的如果已经经过了一趟排序则会通过第一趟选择的基准值划分两个子区间每个子区间也会以区间内选择的基准值划分成两部分。 A: 第一趟的基准值可以为2 第二趟的基准值可以为3 B: 第一趟的基准值可以为2 第二趟的基准值可以为9 C: 第一趟的基准值只能是9但是第二趟的基准值就找不出来没有符合要求的值作为基准值所以不可能是一个中间结果。 D: 第一趟的基准值可以为9 第二趟的基准值可以为5 由于个人精力有限如有错误欢迎指出
小bit
