关于美术馆网站建设的方案,庆元县住房和城乡建设局网站,石家庄网站建设网站建设,游戏设计网站 作者简介#xff1a;დ旧言~#xff0c;目前大一#xff0c;现在学习Java#xff0c;c#xff0c;c#xff0c;Python等 座右铭#xff1a;松树千年终是朽#xff0c;槿花一日自为荣。 目标#xff1a;掌握每种排序的方法#xff0c;理解每种排序利弊… 作者简介დ旧言~目前大一现在学习JavaccPython等 座右铭松树千年终是朽槿花一日自为荣。 目标掌握每种排序的方法理解每种排序利弊和复杂度。 毒鸡汤船停在码头是最安全的但那不是造船的目的人呆在家里是最舒服的但那不是人生的意义。最美好的生活方式莫过于和一群志同道合的人奔跑在理想的路上 望小伙伴们点赞收藏✨加关注哟 前言 谈起排序这个事情大家都是耳熟能详的事了从我们认识的斗地主每一复牌都是按照从小到大的顺序排序的如图 排序的目的是为了让我们很好的管理使无序的事情变成有序当然排序的方法有很多如由大到小由大到小.....。而面对大量数据就需要排序。在数据结构中我们发明了多种排序如我们最早认识的冒泡排序本篇博客让大家对多种排序有一个很好的认知闲话少谈。
⭐主体
咱们就掌握八种就行啦 冒泡排序
这里博主在C语言刷题训练专栏中讲到过冒泡排序咱们再回顾回顾 这里我们以接口的形式写代码那咱们上代码咯 //冒泡排序测试
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){int exchange 0;for (int j 1; j n - i; j){if (a[i - 1] a[i]){//这里是一个交换函数Swap(a[i - 1], a[i]);exchange 1;}}//这里进行一趟有序时直接跳出循环if (exchange 0){break;}}
} 注意事项 1.我们知道当给的数据有序时就不再需要进行循环了直接跳出循环exchange作用。 2. 第二个循环中 j n - i 不能搞错。 时间复杂度O(N²)
空间复杂度O(1)
稳定性稳定
复杂性简单
直接插入排序
直接插入排序是一种简单的插入排序法其基本思想是 把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列 就好像我们斗地主拿牌插入相似。 咱们看看一个动态的插入动作。 这里我们以接口的形式写代码那咱们上代码咯 //插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];//一个元素进行插入while (end 0){if (tmp a[end]){a[end 1] a[end];}else{break;}--end;}//最后把插入的元素赋值回去a[end 1] tmp;}
} 注意事项 1.我们先进行第end个元素移动再进行n个元素进行移动。 2. 最后需要a[end 1] tmp赋值 时间复杂度O(N²) 空间复杂度O(1) 稳定性稳定 复杂性简单 希尔排序 希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序。咱们看看下面的图解 在看看一个动态的图解 这里我们以接口的形式写代码那咱们上代码咯 //希尔排序测试
void ShellSort(int* a, int n)
{int gap n;while (gap 1){//间隔gap的元素进行排序gap gap / 3 1;//本质上是插入排序for (int 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 end - gap;}else{break;}}//最后把插入的元素赋值回去a[end gap] tmp;}}
} 注意事项 1.首先先嵌套一个插入排序再把分组的元素进行交换。 2. gap gap / 3 1这个不要忘记。 时间复杂度O(N¹·²³) 空间复杂度O(1) 稳定性不稳定 复杂性复杂 选择排序 基本思想每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完 。咱们看看图解 这里我们看一个动态的图解 上代码 //选择排序测试
void SelectSort(int* a, int n)
{//初始化第一个元素 和 最后一个元素int begin 0;int 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;}}//最小值和最初的元素交换Swap(a[begin], a[mini]);//如果max被换走就需要重新赋值if (maxi begin){maxi mini;}//最大值和最末的元素交换Swap(a[end], a[maxi]);begin;--end;}
} 注意事项 1.这里先找到最小值和最大值然后交换到最前面和最后面一次进行。 2. 如果最大值被交换后需要从新赋值。 时间复杂度O(N²) 空间复杂度O(1) 稳定性不稳定 复杂性简单 堆排序 堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆排降序建小堆。咱们看看图解 再看看动态的图解 上代码 //堆排序测试
//实现向下调整建大堆
void AdjustDown(int* a, int n, int parent)
{//孩子和父亲的关系 int child parent * 2 1;while (child n){//找出小的那个孩子if (child 1 n a[child 1] a[child]){child;}//实现向下调整元素if (a[child] a[parent]){//元素交换Swap(a[child], a[parent]);// 继续往下调整parent child;child parent * 2 1;}else{break;}}
}//堆排序测试
void HeapSort(int* a, int n)
{//向下调整建堆for (int i (n - 1 - 1) / 2; i 0; i--){//实现向下调整建大堆AdjustDown(a, n, i);}int end n - 1;while (end 0){//元素交换Swap(a[0], a[end]);//实现向下调整建大堆AdjustDown(a, end, 0);--end;}
} 注意事项 1.首先我们需要建大堆以在二叉树讲解咯交换再建大堆 2. 每交换一个元素都需要再建一次大堆。 时间复杂度O(NlogN) 空间复杂度O(1) 稳定性不稳定 复杂性复杂 快排 在快排这个板块中我将讲述四个方法希小伙伴都能掌握。 快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。 Hoare方法 在动态图中key称为基准值默认把基准值定义在数组的首元素上其次为了加快遍历的速度需要用到两个变量分别去对应数组的首尾部分L处在数列的首部它需要从左往右寻找比Keyi位置的值大的遇到后就停下来没遇到就一直走R处在数列的尾部它需要从右往左去寻找比keyi位置的值小的也是遇到后就停下来没遇到就一直走。 当L与R都遇到停下来后开始互换位置然后继续遍历直到LR时双方都不会再走了因为它们走到了同一个位置这个位置被称为它俩的相遇点之后便需要将keyi位置的值与相遇点的值互换位置这样keyi位置的值就放到了中间成为了数组的中心——基准值它意味着将数组分为两个子序列左序列全是小于Keyi的值右序列全是大于Keyi的值这样便可以利用递归一层一层再对左右两个子序列进行相同的步骤——将一个大的无序序列转化为多个小的序列从而进行排序最终排列为完全有序的序列。 上代码 //三数取中 找出中间值
int GetMidi(int* a, int left, int right)
{//中间值int mid (left right) / 2;//三个数比较找出中间值if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}else{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}// 右边找小左边找大交换把左边的值跟a[keyi]交换
int PartSort1(int* a, int left, int right)
{//找中间值相对int midi GetMidi(a, left, right);//把最左边相对跟中间值相对换Swap(a[left], a[midi]);//定位最左边相对int keyi left;while (left right){//找小while (left right a[right] a[keyi]){--right;}//找大while (left right a[left] a[keyi]){left;}//左右交换Swap(a[left], a[right]);}//此时左边走到中间了开始交换Swap(a[keyi], a[left]);//返回return left;
}; 注意事项 1.首先先找到中间值。 2.再和最左边元素互换 3.左边找比中间值大的数右边找中间值小的数然后左右值交换。 4.此时左边走到中间了开始交换 5.上述进行循环知道排序完成 挖坑法 大家就看一下下面图解 //三数取中 找出中间值
int GetMidi(int* a, int left, int right)
{//中间值int mid (left right) / 2;//三个数比较找出中间值if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}else{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}//挖坑法
int PartSort2(int* a, int left, int right)
{//找中间值相对int midi GetMidi(a, left, right);//把最左边相对跟中间值相对换Swap(a[left], a[midi]);//定位最左边相对int key a[left];//保存key值以后左边形成第一个坑int hole left;while (left right){//右边先走找小填到左边的坑右边形成新的坑位while (left right a[right] key){--right;}a[hole] a[right];hole right;//左边再走找大填到右边的坑左边形成新的坑位while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
} 前后指针 通过创建两个指针prev指针指向数组序列首元素位置cur指向prev的下一个位置cur通过遍历去寻找比key基准值小的若找到了还得看prev的下一个位置是否为cur所处的位置若prev的下一个位置确实为cur所处位置则将cur指向的值与prev指向的值进行互换若prev的下一个位置不是cur所处位置则cur继续往后遍历直到cur遍历结束最后要将key基准值与prev指向的值进行互换最终确认基准值处于数组序列的中间位置。 //三数取中 找出中间值
int GetMidi(int* a, int left, int right)
{//中间值int mid (left right) / 2;//三个数比较找出中间值if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}else{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}//前后指针
int PartSort3(int* a, int left, int right)
{//找中间值相对int midi GetMidi(a, left, right);//把最左边相对跟中间值相对换Swap(a[left], a[midi]);//定义指针开头int prev left;//定义指针开头后一个int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}//交换Swap(a[prev], a[keyi]);return prev;
} 快排非递归 1.初始化我们的栈。 2.入栈把我们的开始的left0 rightn-1 3.进入我们的循环体循环体进入的条件是判断栈中是否还有数值如果有数值的化什么其中的数值对应的范围还是没有序的就需要出栈这个时候就需要进行出栈注意栈的数值的左右范围的对应进行我们的挖坑排序对于挖坑我们应该把key返回出来通过key的数值进行我们再一次的入栈操作同时我们的范围。 3.1[left key-1] 和[key1 right] 这样的范围满足条件才能继续push 之后pop进行我们的排序 4如果说我们的循环体结束了的话我们的数组就一定有序 前面已经讲述了栈这里就不再实现栈了 //快排非递归采用栈的形式先进后出
void QuickSortNonR(int* a, int begin, int end)
{//定义ST st;//初始化STInit(st);//添加元素STPush(st, end);STPush(st, begin);while (!STEmpty(st)){//剥离元素 让left取先入但是后出的元素区间的左边int left STTop(st);STPop(st);//让right取栈顶元素是我们后入的区间的右边int right STTop(st);STPop(st);// 右边找小左边找大交换把左边的值跟a[keyi]交换int keyi PartSort1(a, left, right);//分割成段 // [lefy,keyi-1] keyi [keyi1, right]if (keyi 1 right){//添加元素STPush(st, right);STPush(st, keyi 1);}if (left keyi - 1){//添加元素STPush(st, keyi - 1);STPush(st, left);}}//销毁STDestroy(st);
} 归并排序 这里讲述两种方法一种是递归型另一种则是非递归 归并排序递归型 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。 归并排序核心步骤 void _MergeSort(int* a, int* tmp, int begin, int end)
{//尾小于头时if (end begin)return;//开始分割int mid (end begin) / 2;// [begin, mid][mid1, end]_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid 1, end);//归并到tmp数据组再拷贝回去//a-[begin, mid][mid1, end]-tmpint begin1 begin, end1 mid;int begin2 mid 1, end2 end;int index begin;//开始拷贝while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}//当第一段元素没有完全拷贝完就把剩下的拷贝进去while (begin1 end1){tmp[index] a[begin1];}//当第二段元素没有完全拷贝完就把剩下的拷贝进去while (begin2 end2){tmp[index] a[begin2];}//拷贝回原数组memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int));
}//归并排序分路并归
void MergeSort(int* a, int n)
{//开辟空间int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}//调用_MergeSort(a, tmp, 0, n - 1);//释放内存free(tmp);
} 归并排序非递归型 第一次当 gap 为 1 的时候我们将距离为 1 的两个数组其实就是两个元素为 1 的数进行归并得到了拥有两个元素的一个有序数组然后通过循环将后面的元素全部用同样的方式归并。然后就得到了如上图所示蓝色表示的元素排布。同时我们在将这一步骤之后的数组拷贝回到原数组。在进行接下来的操作这里的意思和上递归的是一样的。接着每次将 gap 的值增加 2 倍直到 gap 的值不小于 n 结束归并。这个过程我们将其称为小区间优化。 //归并排序非递归
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; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;// [begin1,end1] [begin2,end2] 归并// 如果第二组不存在这一组不用归并了if (begin2 n){break;}// 如果第二组的右边界越界修正一下if (end2 n){end2 n - 1;}//printf([%d,%d][%d,%d] , begin1, end1, begin2, end2);int index i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}// 拷贝回原数组memcpy(a i, tmp i, (end2 - i 1) * sizeof(int));}printf(\n);gap * 2;}free(tmp);
} 计数排序 计数排序的朴素方法步骤 1、从无序数组中取出最大值max新建一个长度为max1的数组。 2、遍历无序数组取其中元素作为新建数组的索引存在一个则新数组该索引所在的值自增。 3、遍历新数组当存在不为0的元素取该元素的索引放入最终数组并且该元素自减直到为0返回最终数组。 上代码 //计数排序测试
void CountSort(int* a, int n)
{//找最大值和最小值int min a[0], max a[0];for (size_t i 0; i n; i){if (a[i] min)min a[i];if (a[i] max)max a[i];}//找出区间int range max - min 1;//开辟区间int* count (int*)malloc(sizeof(int) * range);printf(range:%d\n, range);//判断if (count NULL){perror(malloc fail);return;}//计入数字的个数memset(count, 0, sizeof(int) * range);// 统计数据出现次数for (int i 0; i n; i){count[a[i] - min];}//排序int j 0;for (int i 0; i range; i){while (count[i]--){a[j] i min;}}
}⭐总结
咱看看每种排序的复杂度和稳定性。 Sort.h代码 #includestdio.h//打印数据
void PrintArray(int* a, int n);//冒泡排序测试
void BubbleSort(int* a, int n);
//插入排序测试
void InsertSort(int* a, int n);
//希尔排序测试
void ShellSort(int* a, int n);
//选择排序测试
void SelectSort(int* a, int n);
//堆排序测试
void HeapSort(int* a, int n);//快排测试
void QuickSort1(int* a, int begin, int end);
void QuickSort2(int* a, int begin, int end);
//快排非递归测试
void QuickSortNonR(int* a, int begin, int end);//归并排序测试
void MergeSort(int* a, int n);
//归并排序非递归测试
void MergeSortNonR(int* a, int n);
//计数排序测试
void CountSort(int* a, int n);
Test.c代码
#define _CRT_SECURE_NO_WARNINGS 1#includetime.h
#includestdlib.h
#includeSort.h
#includeStack.h//希尔排序测试
void TestShellSort()
{int a[] { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };ShellSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}//冒泡排序测试
void TestBubbleSort()
{int a[] { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };BubbleSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}//堆排序测试
void TestHeapSort()
{int a[] { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };HeapSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}//选择排序测试
void TestSelectSort()
{int a[] { 9,1,2,5,7,4,8,6,3,5,1,2,3,5,1,8,3 };SelectSort(a, sizeof(a) / sizeof(int));PrintArray(a, sizeof(a) / sizeof(int));
}//测试代码
void TestOP()
{srand(time(0));const int N 100000;int* a1 (int*)malloc(sizeof(int) * N);int* a2 (int*)malloc(sizeof(int) * N);int* a3 (int*)malloc(sizeof(int) * N);int* a4 (int*)malloc(sizeof(int) * N);int* a5 (int*)malloc(sizeof(int) * N);int* a6 (int*)malloc(sizeof(int) * N);int* a7 (int*)malloc(sizeof(int) * N);for (int i N - 1; i 0; --i){a1[i] rand();a2[i] a1[i];a3[i] a1[i];a4[i] a1[i];a5[i] a1[i];a6[i] a1[i];a7[i] a1[i];}int begin1 clock();//插入排序InsertSort(a1, N);int end1 clock();int begin2 clock();//希尔排序测试ShellSort(a2, N);int end2 clock();int begin7 clock();//冒泡排序测试BubbleSort(a7, N);int end7 clock();int begin3 clock();//选择排序测试SelectSort(a3, N);int end3 clock();int begin4 clock();//堆排序测试HeapSort(a4, N);int end4 clock();int begin5 clock();//快排测试//QuickSort(a5, 0, N - 1);int end5 clock();int begin6 clock();//MergeSort(a6, N);//计数排序测试//CountSort(a6, N);int end6 clock();printf(InsertSort:%d\n, end1 - begin1);printf(ShellSort:%d\n, end2 - begin2);printf(BubbleSort:%d\n, end7 - begin7);printf(SelectSort:%d\n, end3 - begin3);printf(HeapSort:%d\n, end4 - begin4);printf(QuickSort:%d\n, end5 - begin5);printf(MergeSort:%d\n, end6 - begin6);printf(CountSort:%d\n, end6 - begin6);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);
}int main()
{TestOP();//TestBubbleSort();//TestHeapSort();//TestSelectSort();//TestQuickSort();//TestMergeSort();//TestCountSort();//printf(%d\n, Func(100000));return 0;
} Sort.c代码
#define _CRT_SECURE_NO_WARNINGS 1#includeSort.h
#includeStack.h//交换函数
void Swap(int* x, int* y)
{int tmp *x;*x *y;*y tmp;
}//打印数据
void PrintArray(int* a, int n)
{//循环for (int i 0; i n; i){printf(%d , a[i]);}printf(\n);
}//冒泡排序测试
void BubbleSort(int* a, int n)
{for (int i 0; i n - 1; i){int exchange 0;for (int j 1; j n - i; j){if (a[i - 1] a[i]){//这里是一个交换函数Swap(a[i - 1], a[i]);exchange 1;}}//这里进行一趟有序时直接跳出循环if (exchange 0){break;}}
}//插入排序
void InsertSort(int* a, int n)
{for (int i 0; i n - 1; i){int end i;int tmp a[end 1];//一个元素进行插入while (end 0){if (tmp a[end]){a[end 1] a[end];}else{break;}--end;}//最后把插入的元素赋值回去a[end 1] tmp;}
}//希尔排序测试
void ShellSort(int* a, int n)
{int gap n;while (gap 1){//间隔gap的元素进行排序gap gap / 3 1;//本质上是插入排序for (int 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 end - gap;}else{break;}}//最后把插入的元素赋值回去a[end gap] tmp;}}
}//void ShellSort(int* a, int n)
//{/*int gap 3;for (int j 0; j gap; j){for (int i j; i n - gap; i gap){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;}} *///选择排序测试
void SelectSort(int* a, int n)
{//初始化第一个元素 和 最后一个元素int begin 0;int 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;}}//最小值和最初的元素交换Swap(a[begin], a[mini]);//如果max被换走就需要重新赋值if (maxi begin){maxi mini;}//最大值和最末的元素交换Swap(a[end], a[maxi]);begin;--end;}
}//堆排序测试
//实现向下调整建大堆
void AdjustDown(int* a, int n, int parent)
{//孩子和父亲的关系 int child parent * 2 1;while (child n){//找出小的那个孩子if (child 1 n a[child 1] a[child]){child;}//实现向下调整元素if (a[child] a[parent]){//元素交换Swap(a[child], a[parent]);// 继续往下调整parent child;child parent * 2 1;}else{break;}}
}//堆排序测试
void HeapSort(int* a, int n)
{//向下调整建堆for (int i (n - 1 - 1) / 2; i 0; i--){//实现向下调整建大堆AdjustDown(a, n, i);}int end n - 1;while (end 0){//元素交换Swap(a[0], a[end]);//实现向下调整建大堆AdjustDown(a, end, 0);--end;}
}//三数取中 找出中间值
int GetMidi(int* a, int left, int right)
{//中间值int mid (left right) / 2;//三个数比较找出中间值if (a[left] a[mid]){if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}else{if (a[mid] a[right]){return mid;}else if (a[left] a[right]){return left;}else{return right;}}
}// 右边找小左边找大交换把左边的值跟a[keyi]交换
int PartSort1(int* a, int left, int right)
{//找中间值相对int midi GetMidi(a, left, right);//把最左边相对跟中间值相对换Swap(a[left], a[midi]);//定位最左边相对int keyi left;while (left right){//找小while (left right a[right] a[keyi]){--right;}//找大while (left right a[left] a[keyi]){left;}//左右交换Swap(a[left], a[right]);}//此时左边走到中间了开始交换Swap(a[keyi], a[left]);//返回return left;
};//挖坑法
int PartSort2(int* a, int left, int right)
{//找中间值相对int midi GetMidi(a, left, right);//把最左边相对跟中间值相对换Swap(a[left], a[midi]);//定位最左边相对int key a[left];//保存key值以后左边形成第一个坑int hole left;while (left right){//右边先走找小填到左边的坑右边形成新的坑位while (left right a[right] key){--right;}a[hole] a[right];hole right;//左边再走找大填到右边的坑左边形成新的坑位while (left right a[left] key){left;}a[hole] a[left];hole left;}a[hole] key;return hole;
}//前后指针
int PartSort3(int* a, int left, int right)
{//找中间值相对int midi GetMidi(a, left, right);//把最左边相对跟中间值相对换Swap(a[left], a[midi]);//定义指针开头int prev left;//定义指针开头后一个int cur prev 1;int keyi left;while (cur right){if (a[cur] a[keyi] prev ! cur){Swap(a[prev], a[cur]);}cur;}//交换Swap(a[prev], a[keyi]);return prev;
}//快排测试一
void QuickSort1(int* a, int begin, int end)
{if (begin end)return;//小区间优化小区间不再递归分割排序降低递归次数//当元素小于10时采用插入排序if ((end - begin 1) 10){//找值int keyi PartSort3(a, begin, end);// [begin, keyi-1] keyi [keyi1, end]QuickSort1(a, begin, keyi - 1);QuickSort1(a, keyi 1, end);}else{//插入排序InsertSort(a begin, end - begin 1);}
}//快排测试二
void QuickSort2(int* a, int begin, int end)
{if (begin end)return;//调用int keyi PartSort3(a, begin, end);//[begin, keyi-1] keyi [keyi1, end]QuickSort2(a, begin, keyi - 1);QuickSort2(a, keyi 1, end);
}//快排非递归采用栈的形式先进后出
void QuickSortNonR(int* a, int begin, int end)
{//定义ST st;//初始化STInit(st);//添加元素STPush(st, end);STPush(st, begin);while (!STEmpty(st)){//剥离元素 让left取先入但是后出的元素区间的左边int left STTop(st);STPop(st);//让right取栈顶元素是我们后入的区间的右边int right STTop(st);STPop(st);// 右边找小左边找大交换把左边的值跟a[keyi]交换int keyi PartSort1(a, left, right);//分割成段 // [lefy,keyi-1] keyi [keyi1, right]if (keyi 1 right){//添加元素STPush(st, right);STPush(st, keyi 1);}if (left keyi - 1){//添加元素STPush(st, keyi - 1);STPush(st, left);}}//销毁STDestroy(st);
}void _MergeSort(int* a, int* tmp, int begin, int end)
{//尾小于头时if (end begin)return;//开始分割int mid (end begin) / 2;// [begin, mid][mid1, end]_MergeSort(a, tmp, begin, mid);_MergeSort(a, tmp, mid 1, end);//归并到tmp数据组再拷贝回去//a-[begin, mid][mid1, end]-tmpint begin1 begin, end1 mid;int begin2 mid 1, end2 end;int index begin;//开始拷贝while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}//当第一段元素没有完全拷贝完就把剩下的拷贝进去while (begin1 end1){tmp[index] a[begin1];}//当第二段元素没有完全拷贝完就把剩下的拷贝进去while (begin2 end2){tmp[index] a[begin2];}//拷贝回原数组memcpy(a begin, tmp begin, (end - begin 1) * sizeof(int));
}//归并排序分路并归
void MergeSort(int* a, int n)
{//开辟空间int* tmp (int*)malloc(sizeof(int) * n);if (tmp NULL){perror(malloc fail);return;}//调用_MergeSort(a, tmp, 0, n - 1);//释放内存free(tmp);
}//归并排序非递归
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; i 2 * gap){int begin1 i, end1 i gap - 1;int begin2 i gap, end2 i 2 * gap - 1;// [begin1,end1] [begin2,end2] 归并// 如果第二组不存在这一组不用归并了if (begin2 n){break;}// 如果第二组的右边界越界修正一下if (end2 n){end2 n - 1;}//printf([%d,%d][%d,%d] , begin1, end1, begin2, end2);int index i;while (begin1 end1 begin2 end2){if (a[begin1] a[begin2]){tmp[index] a[begin1];}else{tmp[index] a[begin2];}}while (begin1 end1){tmp[index] a[begin1];}while (begin2 end2){tmp[index] a[begin2];}// 拷贝回原数组memcpy(a i, tmp i, (end2 - i 1) * sizeof(int));}printf(\n);gap * 2;}free(tmp);
}//计数排序测试
void CountSort(int* a, int n)
{//找最大值和最小值int min a[0], max a[0];for (size_t i 0; i n; i){if (a[i] min)min a[i];if (a[i] max)max a[i];}//找出区间int range max - min 1;//开辟区间int* count (int*)malloc(sizeof(int) * range);printf(range:%d\n, range);//判断if (count NULL){perror(malloc fail);return;}//计入数字的个数memset(count, 0, sizeof(int) * range);// 统计数据出现次数for (int i 0; i n; i){count[a[i] - min];}//排序int j 0;for (int i 0; i range; i){while (count[i]--){a[j] i min;}}
}
结束语 今天内容就到这里啦时间过得很快大家沉下心来好好学习会有一定的收获的大家多多坚持嘻嘻成功路上注定孤独因为坚持的人不多。那请大家举起自己的小说手给博主一键三连有你们的支持是我最大的动力回见。
