做印刷品去哪个网站,建设部网站办事大厅,常见的推广方式,哪些网站国内打不开✨✨这些 排序算法都是指的 需要进行比较的排序算法 ✨✨下面都是略微讲解一下思路#xff0c;如果需要详细了解哪一个排序#xff0c;点击#x1f449;链接即可 ✨✨对于时间、空间复杂度、稳定性#xff0c;希望你#x1f9d1;#x1f393;能够理解记忆#x1f9d1;… ✨✨这些 排序算法都是指的 需要进行比较的排序算法 ✨✨下面都是略微讲解一下思路如果需要详细了解哪一个排序点击链接即可 ✨✨对于时间、空间复杂度、稳定性希望你能够理解记忆而不是背表格 目录 一、稳定性定义 二、各个排序 1、直接插入排序【排序算法】插入排序-CSDN博客
2、希尔排序【排序算法】希尔排序-CSDN博客
3、选择排序【排序算法】选择排序-CSDN博客
4、堆排序【排序算法】堆排序(Heapsort)-CSDN博客
5、冒泡排序【排序算法】冒泡排序-CSDN博客
6、快速排序【排序算法】快速排序-CSDN博客
7、归并排序【排序算法】归并排序-CSDN博客
三、性能比较
Sort.h
Sort.c test.c
四、总结编辑 一、稳定性定义 排序算法的稳定性指的是在排序过程中相等的元素在排序后保持它们原有的相对顺序。也就是说如果两个元素在原始未排序的序列中是相等的并且其中一个在另一个之前那么在排序后的序列中这个顺序依然保持不变。 当然使用可能对我们来说不够明显但是在实践中在对结构体进行排序非常有意义 ✨ 假设我们要按总分进行排名但是如果总分相同的情况按照数学成绩高的排前头这个时候我们先按照数学成绩排好序相当于第一名是张三那么按照总分拍好后张三还是排在李四的前面从这个表来看第一是张三第二是李四第三是小翔这就是稳定性总分相同的情况下张三还是在李四的前面 二、各个排序 1、直接插入排序【排序算法】插入排序-CSDN博客
✨直接插入排序的思想前一个数有序我拿这一个数和你比如果比你小前一个数往后移动。相当于插扑克牌那么前一个和我手上的牌相等的话不会取挪前一张牌。
所以》》 稳定性✨稳定 时间复杂度O(N^2) 空间复杂度O(1) 稳定性稳定 2、希尔排序【排序算法】希尔排序-CSDN博客
✨希尔的思想是分gap组对每个组都进行插入排序然后gap会不断变小当到1时进行直接插入排序那么想想场景相同的元素在预排序的时候如果被分到不同的组顺序也可能被打断那么就是不稳定因为预排序无法控制所以直接认为不稳定 时间复杂度O(N^1.3) 空间复杂度O(1) 稳定性不稳定 3、选择排序【排序算法】选择排序-CSDN博客
✨在数组里面选小的数选到小的就更新一下相同的不更新然后继续找直到遍历结束把最小的放到左边看着好像是稳定的真是一回事但是我们只是注意了小的耶忘记了我们在在第一个位置的数的情况如下我的5和原来的5相对顺序是不是就已经发生改变了记住这个例子它是不稳定的 时间复杂度O(N^2) 空间复杂度O(1) 稳定性不稳定 4、堆排序【排序算法】堆排序(Heapsort)-CSDN博客
✨思想向下调整建堆建好堆后将尾元素和栈顶元素交换交换以后重现堆n-1个元素的堆进行调整比如全是2的大堆将2取出来全乱了乱套了 时间复杂度O(N*logN) 空间复杂度O(1) 稳定性不稳定 5、冒泡排序【排序算法】冒泡排序-CSDN博客
✨思想前一个和后一个比较大于后一个就交换相等的s》》》稳定的 时间复杂度O(N^2) 空间复杂度O(1) 稳定性稳定 6、快速排序【排序算法】快速排序-CSDN博客
✨思想找比kyi小的和比kyi大的小的放前半部分大的放到后半部分最后kyi放到中间》》
kyi交换到后面顺序乱了所以✨不稳定 时间复杂度O(N*logN) 空间复杂度O(logN) 稳定性不稳定 7、归并排序【排序算法】归并排序-CSDN博客
✨思想2个有序的数组合并2个有序数组相等的情况取前一个尾插 ✨ 稳定的 时间复杂度O(NlogN) 空间复杂度O(N) 稳定性稳定 三、性能比较
✨拿上代码可以自己测试玩哦感兴趣的可以拿走;
Sort.h
#pragma once
#includestdio.h
#includestdlib.h
#includetime.h
#includeassert.h
#includeStack.h
#includestring.h
//插入排序有实践意义
void InsertSort(int* a, int n);
//希尔排序
void ShellSort(int* a, int n);//堆排序
void Swp(int* p1, int* p2);
void AdjustDwon(int* a, int n, int paret);
void HeapSort(int* a, int n);
//选择排序
void SelectSort(int* a, int n);//冒泡排序
void BubbleSort(int* a, int n);//快速排序left和right传的都是下标
void QuickSort1(int* a, int left, int right);
//挖坑法
void QuickSort2(int* a, int left, int right);
//前后指针法
void QuickSort3(int* a, int left, int right);
//非递归法
void QuickSortNonR(int* a, int left, int right);//归并排序
void MergeSort(int* a, int n);
//非递归
void MergeSortNonR(int* a, int n);//计数排序
void CountSort(int* a, int n);
Sort.c #define _CRT_SECURE_NO_WARNINGS 3
#includeSort.h//堆排序
//交换数据
void Swp(int* p1, int* p2)
{assert(p1 p2);int tmp *p2;*p2 *p1;*p1 tmp;
}
void AdjustDwon(int* a, int n, int parent)
{assert(a);//孩子int child parent * 2 1;while (childn){if (child 1 n a[child 1] a[child]){child child 1;}if (a[parent] a[child]){Swp(a[parent], a[child]);parent child;child parent * 2 1;}else{break;}}
}
void HeapSort(int* a, int n)
{//向下调整建堆int i;for (i (n - 1 - 1) / 2; i 0; i--){AdjustDwon(a, n, i);}for (i n - 1; i 0; i--){Swp(a[0], a[i]);AdjustDwon(a, i, 0);}
}
//选择排序
//void SelectSort(int* a, int n)
//{
// for (int i 0; i n; i)
// {
// int min i;
// for (int j i; j n; j)
// {
// if (a[j] a[min])
// {
// min j;
// }
// }
// Swp(a[min], a[i]);
// }
//
//}
选择排序
//void SelectSort(int* a, int n)
//{
// int begin 0, end n - 1;
// while (begin end)
// {
// int mini begin, maxi begin;
// for (int i begin 1; i end; i)
// {
// if (a[i] a[maxi])
// {
// maxi i;
// }
//
// if (a[i] a[mini])
// {
// mini i;
// }
// }
// if (mini end maxi begin)
// {
// Swp(a[maxi], a[mini]);
//
// }
// else if (maxi begin)
// {
// //谁先换掉
// Swp(a[end], a[maxi]);
// Swp(a[begin], a[mini]);
// }
// else
// {
// Swp(a[begin], a[mini]);
// Swp(a[end], a[maxi]);
// }
// begin;
// end--;
// }
//}
void SelectSort(int* a, int n)
{int begin 0;int end n - 1;while (begin end){int maxi begin;int mini begin;for (int i begin 1; i end; i){if (a[maxi] a[i]){maxi i;}if (a[mini] a[i]){mini i;}}Swp(a[mini], a[begin]);if (maxi begin){maxi mini;}Swp(a[maxi], a[end]);begin;end--;}
}//插入排序end1前面的是有序的不断拿end1去比较
void InsertSort(int* a, int n)
{int i;for (i 0; i n - 1; i){int end i;int tmp a[end 1];while (end 0){if (a[end] tmp){a[end 1] a[end];end--;}else{break;}}a[end 1] tmp;}
}//希尔排序:插入的优化1、预排序 2、插入排序
void ShellSort(int* a, int n)
{int gap n;//gap的组数越大数据可以更快的跳到后面小的更快跳到前面但是越不接近有序反之gap越接近有序while (gap 1){//巧妙的用的除法/2 /3 /4都行但是有人证明了/3更好还要加1因为gap小于3的话gap/30//最后一次gap一定是1,也就是插入排序数据变成有序的呢gap gap / 3 1;for (int i 0; i n - gap; i){int end i;int tmp a[end gap];while (end 0){if (a[end] tmp){a[end gap] a[end];end - gap;}else{break;}}a[end gap] tmp;}}}
//4层循环(方法二)
//void ShellSort(int* a, int n)
//{
//
// int gap n;
// while (gap 1)
// {
// gap gap / 3 1;
// for (int i 0; i gap; i)
// {
// for (int j i; j n - i-gap; j gap)
// {
// int end j;
// int tmp a[end gap];
// while (end 0)
// {
// if (a[end] tmp)
// {
// a[end gap] a[end];
// end - gap;
// }
// else
// {
// break;
// }
// }
// a[end gap] tmp; }
// }
//
// }
//
//
//}//冒泡排序
void BubbleSort(int* a, int n)
{int i;for (i 0; i n - 1; i){int flag 0;//从前往后冒泡第一趟最后一个为最大值只要n-1趟即可for (int j1; j n-i; j){if (a[j] a[j - 1]){int tmp a[j];a[j] a[j - 1];a[j - 1] tmp;flag 1;}}if (flag 0){break;}}}//快速排序
//递归实现
//优化先三个数找中间
int GetMin(int* a, int left, int right)
{int min ((right - left) 1) left;if (a[min] a[left]){if (a[min] a[right]){return min;}else if (a[right]a[left]){return right;}else{return left;}}else{if (a[min] a[right]){return min;}else if (a[right] a[left]){return right;}else{return left;}}}
//Hoare
void QuickSort1(int* a, int left, int right)
{//递归结束条件/*if (right left){return;}*///优化后递归结束条件变成了当剩下10个以内的元素需要排序时就使用插入排序if (right - left 1 10){InsertSort(a left, right - left 1);}else {//3个取中int mid GetMin(a, left, right);//将中的元素换到leftSwp(a[mid], a[left]);int keyi left;int begin left;int end right;while (begin end){//右边找小的左边找大的while (a[end] a[keyi] end begin){end--;}while (a[begin] a[keyi] end begin){begin;}//交换Swp(a[begin], a[end]);}Swp(a[keyi], a[begin]);QuickSort1(a, left, begin - 1);QuickSort1(a, end 1, right);}
}
//挖坑法(有一个人要蹲坑)效率差不多
void QuickSort2(int* a, int left, int right){if (right - left 1 10){InsertSort(a left, right - left 1);}else{int mid GetMin(a, left, right);Swp(a[left], a[mid]);int keyi a[left];int begin left;int end right;while (begin end){//仍然是左边找大右边找小while (begin end a[end] keyi){end--;}a[begin] a[end];while (begin end a[begin] keyi){begin;}a[end] a[begin];}a[end] keyi;QuickSort2(a, left, begin - 1);QuickSort2(a, end 1, right);}}
//前后指针法
void QuickSort3(int* a, int left, int right)
{/*if (left right){return;}*/if (right - left 1 10){//小于10个数据进行插入排序InsertSort(a left, right - left 1);}else{int mid GetMin(a, left, right);Swp(a[mid], a[left]);int keyi left;int prev left;int cur left 1;//cur先走找小的while (cur right){//若小于a[keyi]则prev后移一位 再交换if (a[cur] a[keyi]){prev;Swp(a[prev], a[cur]);}cur;}Swp(a[prev], a[keyi]);QuickSort3(a, left, prev - 1);QuickSort3(a, prev 1, right);}
}
//非递归将递归变成迭代最重要的是区间
void QuickSortNonR(int* a, int left, int right)
{SL pts;SLInit(pts);SLPush(pts,right);SLPush(pts, left);while (!SLEmpty(pts)){int begin SLPot(pts);SLPop(pts);int end SLPot(pts);SLPop(pts);int mid GetMin(a, begin,end);Swp(a[mid], a[begin]);int keyi begin;int prev begin;int cur begin 1;//cur先走找小的while (cur end){//若小于a[keyi]则prev后移一位 再交换if (a[cur] a[keyi]){prev;Swp(a[prev], a[cur]);}cur;}Swp(a[prev], a[keyi]);if (prev 1 end){SLPush(pts, end);SLPush(pts, prev 1);}if (prev - 1 begin){SLPush(pts, prev-1);SLPush(pts, 0);}}SLDestroy(pts);}//归并排序:
//子函数:实现递归
void _MergeSort(int* tmp, int* a, int left, int right)
{if (left right){return;}int mid ((right-left)1)left;_MergeSort(tmp, a, left, mid);_MergeSort(tmp, a, mid 1,right);int begin1 left;int end1 mid;int begin2 mid 1;int end2 right;int i 0;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[i] a[begin1];}else{tmp[i] a[begin2];}}while (begin1 end1){tmp[i] a[begin1];}while (begin2 end2){tmp[i] a[begin2];}memcpy(a left, tmp, (right - left 1)*sizeof(int));}
void MergeSort(int* a, int n)
{int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}_MergeSort(tmp, a, 0, n-1);free(tmp);tmp NULL;
}
//非递归归并
void MergeSortNonR(int* a, int n)
{//额外创造一个空间int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}int gap 1;while (gap n){for (int i 0; i n; i2*gap){int begin1 i;int end1 i gap - 1;int begin2 i gap;int end2 i 2 * gap-1;int j i;if (begin2n){break;} if (end2 n){end2 n - 1;}//printf([%d,%d][%d,%d], begin1, end1, begin2, end2);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, tmpi, sizeof(int)*(end2 - i 1));}putchar(\n);gap * 2;}free(tmp);tmp NULL;
}//计数排序
void CountSort(int* a, int n)
{//求最大和最小值int max a[0];int min a[0];for (int i 1; i n; i){if (a[i] min){min a[i];}if (a[i] max){max a[i];}}int ragem max - min 1;//计数的数组int* count (int*)calloc(ragem, sizeof(int));;if (count NULL){perror(calloc fail);return;}//计数for (int i 0; i n; i){count[a[i] - min];}int j 0;//排序for (int i 0; i ragem; i){while (count[i]--){a[j] i min;}}} test.c
#define _CRT_SECURE_NO_WARNINGS 3#includeSort.h//打印
void InPrin(int* a, int n)
{int i;for (i 0; i n; i){printf(%d , a[i]);}
}
//验证函数是否成功
void SortTest()
{int a[] { 10,9,7,1,3,9,4,2,12,3,5,7};int n sizeof(a) / sizeof(a[0]);//HeapSort(a, n);/*printf(InsertSort:);InsertSort(a, n);InPrin(a, n);putchar(\n);puts(对比);printf(ShellSort:);*///ShellSort(a, n);//InPrin(a, n);//BubbleSort(a, n);//SelectSort(a, n);//QuickSort1(a, 0, n - 1);//QuickSort3(a, 0, n - 1);//QuickSortNonR(a, 0, n - 1);//MergeSort(a, n);//MergeSortNonR(a, n);CountSort(a, n);InPrin(a, n);
}
//性能测试
void SortTest1()
{int n 10000000;srand((unsigned int)time(NULL));int* a1 (int*)malloc(sizeof(int) * n);if (a1 NULL){perror(malloc:a1);return;}int* a2 (int*)malloc(sizeof(int) * n);if (a2 NULL){perror(malloc:a2);return;}int* a3 (int*)malloc(sizeof(int) * n);if (a3 NULL){perror(malloc:a3);return;}int* a4 (int*)malloc(sizeof(int) * n);if (a4 NULL){perror(malloc:a4);return;}int* a5 (int*)malloc(sizeof(int) * n);if (a5 NULL){perror(malloc:a5);return;}int* a6 (int*)malloc(sizeof(int) * n);if (a6 NULL){perror(malloc:a6);return;}int* a7 (int*)malloc(sizeof(int) * n);if (a7 NULL){perror(malloc:a7);return;}int* a8 (int*)malloc(sizeof(int) * n);if (a8 NULL){perror(malloc:a8);return;}for (int i 0; i n; i){//尽可能保证多个随机数a1[i] rand()i;a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];a6[i] a1[i];a7[i] a1[i];a8[i] a1[i];}//冒泡int begin1 clock();//BubbleSort(a1, n);int end1 clock();//堆排序int begin2 clock();HeapSort(a2, n);int end2 clock();//希尔int begin3 clock();ShellSort(a3, n);int end3 clock();//插入数据太多也得下桌int begin4 clock();//InsertSort(a4, n);int end4 clock();//选择(下桌太慢了影响到其他数据计算)int begin5 clock();//SelectSort(a5,n);int end5 clock();//快排int begin6 clock();QuickSort3(a6, 0, n - 1);int end6 clock();int begin7 clock();MergeSort(a7, n);//MergeSortNonR(a7, n);int end7 clock();int begin8 clock();CountSort(a8, n);int end8 clock();printf(BubbleSort:%d\n, end1 - begin1);printf(HeadSort:%d\n, end2 - begin2);printf(ShellSort:%d\n, end3 - begin3);printf(InsertSort:%d\n, end4 - begin4);printf(SelectSort:%d\n, end5 - begin5);printf(QuickSort:%d\n, end6 - begin6);printf(MergeSort:%d\n, end7 - begin7);printf(CountSort:%d\n, end8 - begin8);free(a1);a1 NULL;free(a2);a2 NULL;free(a3);a3 NULL;free(a4);a4 NULL;free(a5);a5 NULL;free(a6);a6 NULL;free(a7);a7 NULL;free(a8);a8 NULL;
}int main()
{//SortTest();SortTest1();return 0;
}
四、总结排序算法 提醒一句希望你还是通过代码理解性的记忆明确这个值是怎么计算出来的而不是记住冰冷的表格❤️
