建设网站只能是公司吗,正规企业展厅设计公司,秀山网站建设,建e网网址是多少目录 编辑
排序的概念
常见排序算法
编辑
1.冒泡排序
#x1f379;图解
#x1f973;代码实现
#x1f914;时间复杂度
2.插入排序
#x1f379;图解
#x1f334;深度剖析
#x1f34e;代码思路
#x1f973;代码实现
#x1f914;时间复杂度
3.希尔…目录 编辑
排序的概念
常见排序算法
编辑
1.冒泡排序
图解
代码实现
时间复杂度
2.插入排序
图解
深度剖析
代码思路
代码实现
时间复杂度
3.希尔排序
深度剖析
代码思路
思考关于gap的取值问题
代码实现
时间复杂度
4.堆排序
⛱️请看我的另一篇文章详解堆排序
5.选择排序
图解
深度剖析
代码实现
时间复杂度
6.快速排序
图解1霍尔法
深度剖析
代码思路
优化1改变选key策略采用三数选中法
优化2小区间优化采用其它排序方法减少递归次数
思考如何保证相遇位置比key小
代码实现
图解2前后指针法 深度剖析
代码思路
优化避免自己和自己交换
代码实现
非递归实现
代码思路
代码实现
7.归并排序
图解
深度剖析 递归版
代码思路
代码实现
非递归版
代码思路
思考上面的思路只能解决数组大小为的数组其余数组则会存在越界问题如何解决
代码实现
时间复杂度 排序的概念 排序 所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。 稳定性 假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次 序保持不变即在原序列中 r[i]r[j] 且 r[i] 在 r[j] 之前而在排序后的序列中 r[i] 仍在 r[j] 之前则称这种排 序算法是稳定的否则称为不稳定的。 内部排序 数据元素全部放在内存中的排序。 外部排序 数据元素太多不能同时放在内存中根据排序过程的要求不断地在内外存之间移动数据的排序。 常见排序算法 下文将会细细介绍上图中七种排序观看前可以点一个免费的赞与收藏支持作者~希望本篇博客能帮助到你
1.冒泡排序
相邻两个数进行比较大的数向后移每次循环都能冒出一个大的数到数组最后直至最后全部冒出。
图解 代码实现
#define _CRT_SECURE_NO_WARNINGS
#include stdio.hvoid bubble_sort(int arr[],int sz)
{int flag 1;//优化int i 0;for (i 0; i sz - 1; i) {int j 0;for (j 0; j sz - 1 - i; j) {if (arr[j] arr[j 1]) {flag 0;int tmp arr[j];arr[j] arr[j 1];arr[j 1] tmp;}}if (flag 1) {break;}}
}int main() {int n 0;int arr[] {2,6,9,3,6,9,1};int sz sizeof(arr) / sizeof(arr[0]);bubble_sort(arr, sz);for (n 0; n sz - 1; n) {printf(%d, arr[n]);}return 0;
}
时间复杂度
O(N^2)
2.插入排序
图解 深度剖析
代码思路
上图为基本的插入排序可对其进行优化依次遍历找出最大值和最小值索引。
代码思路1.设变量minimaxi分别为最小值和最大值索引 设beginend分别无序部分的首尾索引。 2.遍历无序部分找出最小值和最大值的索引minimaxi 3.将a[begin]和a[mini]进行交换将a[end]和a[maxi]进行交换 注意两次交换的中间需要进行依次判断判断maxi是否仍然等于begin因为经过第一个交换后原begin位置的值已经交换到mini位置去了如果判断成立maxi也应该跟随原begin的值的移动移动到mini位置。 4.此时begin、end处已经属于有序部分begin,end--更新无序部分的范围。 5.对剩余无序部分重复上述步骤直到beginend。
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
void swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}void selectsort(int* a, int n) {int begin 0;int end n - 1;while (begin end) {int mini begin;int maxi begin;//找最大值最小值的索引for (int i begin 1; i end; i) {if (a[i] a[mini]) {mini i;}if (a[i] a[maxi]) {maxi i;}}//进行交换swap(a[mini], a[begin]);if (maxi begin)//begin此时被mini换走了maxi mini;swap(a[maxi], a[end]);begin;end--;}}int main() {int a1[8] { 9,1,2,5,7,4,6,3};selectsort(a1,8);//int a2[5] { 3,2,5,6,7 };//selectsort(a2, 5);for (int i 0; i 8; i) {printf(%d , a1[i]);}return 0;
}
时间复杂度
ON^2)
3.希尔排序
深度剖析
代码思路
希尔排序是在插入排序的基础上进行优化的。
1.预排序将数组分为gap组进行预排序让数组接近有序
2.插入排序此时数组近乎有序使用插入排序效率极高 即蓝色的为一组红色的为一组绿色为一组对每组进行插入排序 以下是预排序的代码
//预排序过程假设gap3
//第一种写法依次对三组进行预排序
for(int j0;jgap;j){ //依次对三组进行预排序
for (int i gap; i n; igap) { //对一组进行预排序的过程由于一组内部元素之间相距gap所以应该是igapint end i;int tmp a[end];while (end gap) {if (tmp a[end - gap]) {a[end] a[end - gap];a[end - gap] tmp;end - gap;}else {break;}} }
//第二种写法同时进行三组的预排序但效率相较上一种写法其实没有改变
for (int i gap; i n; i) {//先对蓝组排1下再对红组排1下再对绿组排1下如此循环int end i;int tmp a[end];while (end gap) {if (tmp a[end - gap]) {a[end] a[end - gap];a[end - gap] tmp;end - gap;}else {break;}}
思考关于gap的取值问题
gap越大大的数字越快跳到后面小的数字越快跳到前面结果越不接近有序。
gap越小跳得越慢但结果越接近有序gap1时相当于插入排序) 解决方案走多组gapgap1时就是预排序 gap1时就是插入排序
gap我们通常设置为gapgap/31
这里1是为了保证gap1。 代码实现
//1.预排序分成gap组进行//2.插入排序void ShellSort(int* a, int n) {int gap n;while (gap1) {gap gap / 3 1;//保证gap1for (int i gap; i n; i) {int end i;int tmp a[end];while (end gap) {if (tmp a[end - gap]) {a[end] a[end - gap];a[end - gap] tmp;end - gap;}else {break;}}}}}
时间复杂度 4.堆排序
⛱️请看我的另一篇文章详解堆排序
5.选择排序
图解 深度剖析
基本思路遍历一遍选择最小的插到最左边
优化思路遍历一遍选出最小的最大的分别插到最左最右
一个小坑将最大值放到最后后可能破坏了原本的
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
void swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}void selectsort(int* a, int n) {int begin 0;int end n-1 ;while (begin end) {int mini a[begin];int maxi a[end];for (int i begin; i end; i) {if (a[i] mini) {mini a[i];swap(a[i], a[begin]);}if(a[i]maxi) {maxi a[i];swap(a[i], a[end]);}//验证if (a[i] mini) {mini a[i];swap(a[i], a[begin]);}}begin;end--;}}int main() {int a1[8] { 9,1,2,5,7,4,6,3};selectsort(a1,8);//int a2[5] { 3,2,5,6,7 };//selectsort(a2, 5);for (int i 0; i 8; i) {printf(%d , a1[i]);}return 0;
}
时间复杂度
ON^2)
6.快速排序
图解1霍尔法 深度剖析
代码思路
我们先考虑单趟 end,begin相遇前end向前走找比key小的值begin向后走找比key大的值都找到后两者进行交换 end,begin相遇时循环停止交换begin和key 单趟过后的结果
key所在位置一定是正确的位置[left,key-1]中的值一定小于key[key1,right]中的值一定大于key
//单趟一定先走end,再走begin
int begin left;int end right;int key left;while (begin end) {while (a[end] a[key] begin end) {end--;}while(a[begin] a[key]beginend) {begin;}Swap(a[begin], a[end]);}Swap(a[begin], a[key]);
key begin;
此时整个数组可以划分为三个部分[left,key-1]key, [key1,right]
递归接着就用递归思想对[left,key-1][key1,right]中的值进行排序 递归结束条件数组不存在或者只有1个元素 优化1改变选key策略采用三数选中法
当数组有序排列时且数据量较大时基础版快排可能出现栈溢出问题。 解决办法:改变选key的策略采用三数选中的方法使key不要老是为最小值而尽量趋于中值。
即确定出三个索引如leftright, (right-left)/2选出三个索引对应的值为中值的索引。
//优化1改变选key的策略采用三数选中法
int FindMid(int* a, int left, int right) {int mid (left right) / 2;if (a[left] a[right]) {if (a[left] a[mid]) {if (a[mid] a[right]) {//a[left]a[mid]a[right]return mid;}else {//a[left]a[right]a[mid]return right;}}else {//a[mid]a[left]a[right]return left;}}else {//a[left] a[right]if (a[mid] a[right]) {if (a[mid] a[left]) {//a[mid] a[left] a[right]return left;}else {return mid;}}else {//a[left] a[right]a[mid]return right;}}
}优化2小区间优化采用其它排序方法减少递归次数
冒泡排序、选择排序效率太一般希尔排序更适合处理数据量更大的数据此时的数据已经较为接近有序此处采用插入排序。 //优化小数区间采取选择排序if (left 5 right) {InsertSort(aleft, right - left 1);return;} 思考如何保证相遇位置比key小
左边做key右边先走可以保证相遇位置比key小。
相遇场景分析
begin遇endend先走停下来一定是因为遇到了比key小的值。 begin再走begin没有找到大的遇到end就停下了。
end遇beginend走end没有找到小的遇到begin就停下了。 而begin的位置此时还是上一轮交换的位置而上一轮交换把比key小的值换到了begin的位置。 代码实现
1.基础版递归
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
//递归版
void Swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}
void QuickSort(int* a, int left, int right) {//先考虑单趟//end找比key小begin找比key大都找到后交换//end,begin相遇时停止交换begin和key//单趟过后的结果key所在位置一定是正确的位置a[left,key-1]一定小于keya[key1,right]一定大于key//接着就用递归思想处理a[left,key-1]a[key1,right]//递归结束条件数组不存在或者只有1个元素if (left right) {return;}int begin left;int end right;int key left;while (begin end) {while (a[end] a[key] begin end) {end--;}while(a[begin] a[key]beginend) {begin;}Swap(a[begin], a[end]);}Swap(a[begin], a[key]);key begin;//此时key需要改变QuickSort(a, left, key-1);QuickSort(a, key 1, right);
}int main() {int a[10]{ 6, 1, 2, 7, 9, 3, 4, 5, 10,8 };QuickSort(a, 0, 9);for (int i 0; i 10; i) {printf(%d , a[i]);}return 0;
}
2.优化版递归
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
//递归版
void Swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}
//优化1改变选key的策略采用三数选中法
int FindMid(int* a, int left, int right) {int mid (left right) / 2;if (a[left] a[right]) {if (a[left] a[mid]) {if (a[mid] a[right]) {//a[left]a[mid]a[right]return mid;}else {//a[left]a[right]a[mid]return right;}}else {//a[mid]a[left]a[right]return left;}}else {//a[left] a[right]if (a[mid] a[right]) {if (a[mid] a[left]) {//a[mid] a[left] a[right]return left;}else {return mid;}}else {//a[left] a[right]a[mid]return right;}}
}void InsertSort(int* a, int n) {for (int i 1; i n ; i) {int end i;int tmp a[end];while (end 0) {if (tmp a[end - 1]) {a[end] a[end - 1];a[end - 1] tmp;end--;}else {break;}}}
}void QuickSort(int* a, int left, int right){//先考虑单趟//end找比key小begin找比key大都找到后交换//end,begin相遇时停止交换begin和key//单趟过后的结果key所在位置一定是正确的位置a[left,key-1]一定小于keya[key1,right]一定大于key//接着就用递归思想处理a[left,key-1]a[key1,right]//递归结束条件数组不存在或者只有1个元素/*if (left right) {return;}*///优化小数区间采取选择排序if (left 5 right) {InsertSort(aleft, right - left 1);return;}int begin left;int end right;//优化改变选key的策略采用三数选中法int key FindMid(aleft, left, right);Swap(a[begin], a[key]);key begin;//int key begin;while (begin end) {while (a[end] a[key] begin end) {end--;}while(a[begin] a[key]beginend) {begin;}Swap(a[begin], a[end]);}Swap(a[begin], a[key]);key begin;//此时key需要改变QuickSort(a, left, key-1);QuickSort(a, key 1, right);
}int main(){int a[10]{ 6, 1, 2, 7, 9, 3, 4, 5, 10,8 };QuickSort(a, 0, 9);for (int i 0; i 10; i) {printf(%d , a[i]);}return 0;
}
图解2前后指针法 深度剖析
代码思路
仍然从单趟开始分析
1. 2.判断cur指针指向的数据是否小于key 小于——prev后移一位交换cur和prev指向的内容cur指针后移一位
大于——cur后移一位效果使得prev和cur之间的值全是大于key的值 3.当cur越界将prev指向的内容与key进行呼唤
效果key左边的数据都比key小key右边的数据都比key大 由于快慢指针法单趟后的效果和霍尔法其实是一致的后续步骤就和霍尔法的步骤一模一样。
优化避免自己和自己交换
if (a[cur] a[key] prev ! cur) {//优化当prev与cur重叠时就不进行交换Swap(a[cur], a[prev]);}
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
void Swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}
//优化1改变选key的策略采用三数选中法
int FindMid(int* a, int left, int right) {int mid (left right) / 2;if (a[left] a[right]) {if (a[left] a[mid]) {if (a[mid] a[right]) {//a[left]a[mid]a[right]return mid;}else {//a[left]a[right]a[mid]return right;}}else {//a[mid]a[left]a[right]return left;}}else {//a[left] a[right]if (a[mid] a[right]) {if (a[mid] a[left]) {//a[mid] a[left] a[right]return left;}else {return mid;}}else {//a[left] a[right]a[mid]return right;}}
}void InsertSort(int* a, int n) {for (int i 1; i n; i) {int end i;int tmp a[end];while (end 0) {if (tmp a[end - 1]) {a[end] a[end - 1];a[end - 1] tmp;end--;}else {break;}}}
}void QuickSort2(int* a, int left, int right) {if (left 5 right) {InsertSort(a left, right - left 1);return;}//优化改变选key的策略采用三数选中法int key FindMid(a left, left, right);Swap(a[left], a[key]);key left;int prev left;int cur left 1;while (cur right) {if (a[cur] a[key] prev ! cur) {//优化当prev与cur重叠时就不进行交换Swap(a[cur], a[prev]);}cur;}Swap(a[key], a[prev]);key prev;//此时key需要改变QuickSort2(a, left, key - 1);QuickSort2(a, key 1, right);
}int main(){int a[10] { 6, 1, 2, 7, 9, 3, 4, 5, 10,8 };QuickSort2(a, 0, 9);for (int i 0; i 10; i) {printf(%d , a[i]);}return 0;
} 非递归实现
代码思路
利用栈来模拟递归的过程假设每次key值都刚好二分。
1.初始化一个栈将right和left压入栈中
1.对数组进行单趟快速排序得到[left,key-1],key,[key1,right]
2.设begin1leftend1key-1 设begin2key1end2right
3.若begin2end2,将end2begin2压入栈中
若begin1end1,将end1begin1压入栈中
4.取并删除栈顶元素两次得到begin1end1对[begin1,end1]数组进行单趟快速排序
5.重复步骤23,4,栈为空时循环结束
.
代码实现
#define _CRT_SECURE_NO_WARNINGS
#include stdio.h
#include stack.hvoid Swap(int* a, int* b) {int tmp *a;*a *b;*b tmp;
}void QuickSort(int* a, int left, int right) {Stack st;StackInit(st);StackPush(st, right);StackPush(st, left);while (!StackEmpty(st)) {left StackTop(st);StackPop(st);right StackTop(st);StackPop(st);int begin left;int end right;int key begin;while (begin end) {while (a[end] a[key] begin end) {end--;}while (a[begin] a[key] begin end) {begin;}Swap(a[begin], a[end]);}Swap(a[begin], a[key]);key begin;//此时key需要改变int begin1 left;int end1 key - 1;int begin2 key 1;int end2 right;if (begin2 end2) {StackPush(st, end2);StackPush(st, begin2);}if (begin1 end1) {StackPush(st, end1);StackPush(st, begin1);}}StackDestroy(st);return;
}int main() {int a[10] { 6, 1, 2, 7, 9, 3, 4, 5, 10,8 };QuickSort(a, 0, 9);for (int i 0; i 10; i) {printf(%d , a[i]);}return 0;
}
7.归并排序
图解 深度剖析 基本思想 归并排序 MERGE-SORT 是建立在归并操作上的一种有效的排序算法 , 该算法是采用分治法 。 将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 递归版
代码思路
假设数组可以被拆分成两个子数组
比较begin1和begin2位置的值
取小尾插到tmp
被取指针向前移动
未被取指针不动 但问题是数组往往不能直接被拆成两个有序数组
因此考虑继续细分数组直到有序比如只有1个数时必定有序 然后将有序子数组一层层的合并回去每次合并完将结果拷贝回原数组。 这个过程有点类似后序遍历。
代码实现
void MergeSort1(int* a, int n) {int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL) {perror(tmp malloc fail!);return;}if (n 1) {//当数组被拆分成单个数或无法继续拆分返回return;}int mid (n1)/ 2;//假设数组3个数mid2,MergeSort1(a, mid);//[0,mid-1]有序MergeSort1(amid, n-mid);//[mid,n-1]有序//合并两个有序数组int begin1 0;int end1 mid - 1;int begin2 mid;int end2 n - 1;int tmp1 0;while (begin1 end1 begin2 end2) {if (a[begin1] a[begin2]) {//begin1的数比begin2小尾插begin1tmp[tmp1] a[begin1];begin1;tmp1;}else {tmp[tmp1] a[begin2];begin2;tmp1;}}//循环结束说明有一方指针已经走完//将另一方未走完指针走完while (begin1 end1) {tmp[tmp1] a[begin1];begin1;tmp1;}while (begin2 end2) {tmp[tmp1] a[begin2];begin2;tmp1;}//此时的tmp数组为有序数组//拷贝回原数组memcpy(a, tmp, sizeof(int) * n);
}
非递归版
代码思路
1.首先设一个变量gap代表每组需要归并的个数。
2.划分两个大小为gap的子数组[begin1,end1],[begin2,end2]这两个数组应当是有序的对其进行归并归并完后继续向后划分两个大小为gap的子数组继续归并直到整个数组被遍历完。
3.遍历完一次数组意味着以gap*2为大小的子数组已经有序因此gap*2以新gap数继续完成新一轮对数组的归并遍历。直到gap2,结束。
思考上面的思路只能解决数组大小为的数组其余数组则会存在越界问题如何解决
这是一个数据个数为10的数组 打印每轮的合并情况可发现有些位置发生了越界 将图示越界的位置抽象出来即为 解决方案
判断begin2是否存在若不存在则结束归并若存在则修正end2使其不越界。
代码实现
void MergeSort2(int* a, int n) {int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL) {perror(tmp malloc fail!);return;}if (n 1) {//当数组被拆分成单个数或无法继续拆分返回return;}//后序遍历//合并两个有序数组int gap 1;//每组需要归并的个数while(gapn){//层序遍历for(int i0;in;i2*gap){int begin1 i;int end1 igap-1;int begin2 igap;int end2 i2*gap-1;int j i;if (begin2 n) {break;}if (end2 n) {end2 n - 1;}while (begin1 end1 begin2 end2) {if (a[begin1] a[begin2]) {//begin1的数比begin2小尾插begin1tmp[j] a[begin1];begin1;}else {tmp[j] a[begin2];begin2;}}//循环结束说明有一方指针已经走完//将另一方未走完指针走完while (begin1 end1) {tmp[j] a[begin1];begin1;}while (begin2 end2) {tmp[j] a[begin2];begin2;}//此时的tmp数组为有序数组//拷贝回原数组memcpy(ai, tmpi, sizeof(int) * (end2-i1));//易错点(end2-begin11)是错的因为begin1这个时候已经不再是子数组起点位置}gap * 2;}}int main() {int a1[8] { 10,6,7,1,3,9,4,2 };int a2[16] { 16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1 };int a3[12] { 12,11,10,9,8,7,6,5,4,3,2,1 };MergeSort2(a1, 8);for (int i 0; i 8; i) {printf(%d , a1[i]);}printf(\n);MergeSort2(a2, 16);for (int i 0; i 16; i) {printf(%d , a2[i]);}MergeSort2(a3, 12);printf(\n);for (int i 0; i 12; i) {printf(%d , a3[i]);}} 时间复杂度
ON*logN)
