【数据结构】与排序算法鏖战5天，我终于搞懂了排序的思路和实现--排序算法大全的保姆级攻略

目录一排序的概念及分类二排序算法的实现1插入排序intsert sort_1,核心思路_2,代码实现_3,总结2希尔排序Shell sort_1,核心思路_2,代码实现_3,总结3选择排序Select sort_1,核心思想_2,代码实现_3,总结4堆排序Heap sort第一步建小堆方法一向上调整建小堆方法二向下调整建小堆第二步排序5冒泡排序(Bubble sort)_1,核心思想:_2,代码实现_3,总结6快速排序Quick sort_1,核心思想_2,代码实现_3,时间和空间效率_4,优化方法三数取中法和小区间优化_5,先后指针法实现单趟排序_6,非递归实现快速排序7归并排序 Merge sort_1,核心思想_2,代码实现_3,时间和空间效率_4,非递归实现归并排序8,计数排序Counting sort_1,核心思想_2,代码实现_3,时间和空间效率三各种排序总结及稳定一排序的概念及分类排序就是将将给定的一串数据进行从小到大或者从大到小进行排列。二排序算法的实现1插入排序intsert sort_1,核心思路将数组分成两个两个部分一个为已排序部分一个为未排序的部分默认数组中的第一个数为已排序部分然后将未排序部分的第一个数字依次排入到已排序的部分直到排序到最后一个数未排序部分消失。图例展示将有序数组中的最后一个元素的下表记录为end将无序部分的第一个元素的下标记录为tmp,将tmp所指向的元素和end及end前面的元素从后往前依次进行比较如果前面的元素大就向后移动一位如果小于就停止比较。_2,代码实现//插入排序 void Insertsort(int* a, int n) { for (int i 0; i n - 1; i) { int end i; //end的范围为[0,n-2] int tmp a[end 1]; //进行后移 while (end 0 tmp a[end]) //注意防止越界访问 { a[end 1] a[end]; end--; } //后移完进行插入 a[end 1] tmp; } }_3,总结元素越接近有序直接插入排序的时间效率越高时间复杂度最坏的情况数组逆序每一个数都要遍历一遍前面的数1234……n-1 n*(n-1)/2 - 1时间复杂度为O(n^2)空间复杂度没有开辟任何新的空间O(1)2希尔排序Shell sort_1,核心思路希尔排序也称为缩小增量排序是对直接插入排序的优化先进行预排序使得序列基本有序再进行直接插入排序。预排序先将序列划分几个小序列再对这几个小序列分别进行直接插入排序。分析相比于直接插入进行预排序可以让大数更快跳转到后面去而不是一次一次往后移动。_2,代码实现//希尔排序2--每组并着排 void ShellSort2(int* a, int n) { int gap n; while (gap 1) { //1保证最后一个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 tmp a[end]) //注意防止越界访问 { a[end gap] a[end]; end - gap; } //后移完进行插入 a[end gap] tmp; } } }另一种写法//希尔排序2--每组并着排 void ShellSort2(int* a, int n) { int gap n; while (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 tmp a[end]) //注意防止越界访问 { a[end gap] a[end]; end - gap; } //后移完进行插入 a[end gap] tmp; } } }_3,总结当gap1时都是预排序让数组更接近有序。当gap1时数组已经非常接近有序此时进行插入排序就会非常快。希尔排序的时间复杂度为O(N^1.3)由于没有额外开辟数组空间所以空间复杂度为O(1)3选择排序Select sort_1,核心思想每次从待排序列中选出最大值和最小值放在序列的两端直到待排序列中的元素个数为零。遍历数组找到并存储最大值和最小值和选定序列的开头结尾元素进行交换。_2,代码实现//交换元素值 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) { //假设最大值和最小值均为begin int mini begin, maxi begin; //找出最大值和最小值--从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) { maxi mini; } Swap(a[maxi], a[end]); begin; end--; } }特殊情况分析_3,总结时间复杂度最坏情况n-1n-3n-5……1 n^2 / 4所以时间复杂度为:O(N^2)没有额外创建新空间空间复杂度为O(1)4堆排序Heap sort堆排序是基于数据结构堆的一种高效的排序方法。堆排序可以分为两步1建队 2排序下面给一个例子给定一个数组 a {8,9,7,2,5,4,1,6}要求将数组按照从小到大的顺序进行排序第一步建小堆方法一向上调整建小堆向上调整只需要上方的树都是小堆即可将数组中的元素从左到右进行向上调整也就是从树的根节点开始进行调整这样可以保证每要调整一个节点时该节点上面的节点都有序。分析时间复杂度方法二向下调整建小堆先找到倒数第一个分支节点进行向下调整再不断向前找元素进行调整直到遍历到根节点。分析时间复杂度第二步排序时间复杂度分析代码实现//堆排序 void heapsort(int* a,int n) { //升序建大堆 //降序建小堆 //降序-向上调整算法建小堆 //for (int i 1; i n; i) //{ // AdjustUp(a, i); //} //降序-向下调整算法建小堆 for (int i (n - 1 - 1) / 2; i 0; i--) { Adjustdown(a, n, i); } int end n - 1; while (end 0) { HPswap(a[0], a[end]); Adjustdown(a, end, 0); end--; } } void HPhead2() { int ar[] { 5,6,8,3,2,7,1,4,9 }; int sz sizeof(ar) / sizeof(ar[0]); heapsort(ar, sz); } int main() { //HPtest(); HPhead2(); return 0; }按照向下调整建小堆总体的时间复杂度为N^2*logN按照向上调整建小堆总体的时间复杂度为N^2*(logN)^2空间复杂度没有额外开辟空间故为O(1)5冒泡排序(Bubble sort)_1,核心思想:对相邻两个元素进行比较,然后进行排序。分析对一个数组内的元素进行排序例如数组内元素为 10 9 8 7 6 5 4 3 2 1按照升序的方式排列1 2 3 4 5 6 7 8 9 10我们需要先选取10和9两个元素进行比较在交换两个元素的位置依次往下进行当遍历完数组内所有元素后变为9 8 7 6 5 4 3 2 1 10。接着我们需要重复上述过程总共进行遍历9次得到升序数组。_2,代码实现_3,总结冒泡排序的时间复杂度为最坏情况倒序n-1n-2n-3……1 n*(n-1) / 2故最终为O(N^2)冒泡排序空间复杂度没有额外开辟空间故为O(1)6快速排序Quick sort_1,核心思想在数组中选取一个数作为基准值通过这个基准值将数组分成两个子数组让左子数组的值均小于基准值右子数组的值均大于基准值然后将左右数组的中间值和基准值进行交换 使得基准值左边的元素都比它小右边的都比他大然后再对左右数组进行递归快速排序。步骤通常选取数组最左边或者最右边的数当作基准值然后定义两个下标一个从左边开始向右走一个从最右边开始向左走。当检查到左数组中有比基准值还要大的值时停止当检查到右数组中有比基准值还要小的值时停止然后将两个值进行交换。相遇时停止停止位置的值一定小于key原因后面有解释并把key的值放到相遇的位置。递归部分然后以keyi为基准对数组进行分割分割为左数组部分和右数组部分。再对左右数组分别进行快速排序递归直到递归到左右数组中只有一个元素时终止此时进行返回最后得到的数组就是有序的。_2,代码实现//交换元素 void Swap(int* a, int* b) { int tmp *a; *a *b; *b tmp; } //快速排序 void QuickSort(int* a, int left,int right) { //当小区间只剩下一个数时跳出终止 if (left right) return; int begin left; int end right; int keyi left; //查找并交换元素 while (begin end) { //先从右找小 while (begin end a[end] a[keyi])//防止end--后不满足条件 { end--; } //再从左找大 while (begin end a[begin] a[keyi])//防止begin后不满足条件 { begin; } //进行交换 Swap(a[end],a[begin]); } //此时begin和end已经相遇要和keyi进行交换 Swap(a[keyi], a[begin]); keyi begin; //对数组进行分割然后进行对左右子数组递归 //[left,keyi-1] keyi [keyi1,right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi1, right); }_3,时间和空间效率快速排序的时间复杂度快速排序的高度类似二叉树的高度高度为logNN/2^h 1 N 2^h h logN每一层都相当于遍历了整个数组共N次所以最后快速排序的时间复杂度就为: O(N*logN)空间复杂度空间复杂度不仅包含手动管理的“显式数组”还包含程序运行所包含的“隐式内存”主要是函数调用栈开辟栈帧空间。由于同一个栈帧空间可以在上次调用完函数被销毁后再次作为下一个函数相同但参数不同的函数进行调用时再次创建这个栈帧空间其实际上进行排序时最多存在的栈帧空间为递归树的最大深度logN。所以说空间复杂度实际是同时存活的栈帧空间个数而不是总共开辟了多少次栈帧空间。综上空间复杂度为logN下面是时间和空间复杂度的最坏情况:最坏情况下时间复杂度可以退化为:O(N^2)空间复杂度可以退化为O(N)由于向下递归的次数较多递归深度较深而每次递归都会调用函数开辟栈帧空间所以可能会造成栈溢出。_4,优化方法三数取中法和小区间优化具体思路取数组中最左边的数和最右边的数以及最中间的数。进行比较选取值的大小排中间的数并把它放到数组的最左边。代码展示//取中间值 int GetMidi(int* a, int left, int right) { int mid (left right) / 2; if (a[left] a[mid]) { if (a[mid] a[right]) { return a[mid]; } else if (a[left] a[right]) { return a[right]; } else { return a[left]; } } else //a[left] a[mid] { if (a[right] a[mid]) { return a[mid]; } else if (a[left] a[right]) { return a[left]; } else { return a[right]; } } }优化2,小区间优化当数组被分为比较小的时候可以不使用快速排序的递归可以直接使用其他的排序算法对小数组进行排序。防止递归的次数太多影响效率。由于经过前面的几次快速排序数组接近有序可以直接使用插入排序。最终优化后代码//快速排序 void QuickSort(int* a, int left,int right) { //当小区间只剩下一个数时跳出终止 if (left right) return; //小区间优化 if ((right - left 1) 10) //right-left1 为数组中值的个数 { Insertsort(aleft, right-left1); } else { //三数取中 int midi GetMidi(a, left, right); Swap(a[midi], a[left]); int begin left; int end right; int keyi left; //查找并交换元素 while (begin end) { //先从右找小 while (begin end a[end] a[keyi])//防止end--后不满足条件 { end--; } //再从左找大 while (begin end a[begin] a[keyi])//防止begin后不满足条件 { begin; } //进行交换 Swap(a[end], a[begin]); } //此时begin和end已经相遇要和keyi进行交换 Swap(a[keyi], a[begin]); keyi begin; //对数组进行分割然后进行对左右子数组递归 //[left,keyi-1] keyi [keyi1,right] QuickSort(a, left, keyi - 1); QuickSort(a, keyi 1, right); } }补充解释为什么left和right相遇的位置的数一定比key小_5,先后指针法实现单趟排序核心思路代码实现//单趟排序--前后指针法 int PartSort2(int* a, int left, int right) { //三数取中 int midi GetMidi(a, left, right); Swap(a[midi], a[left]); //创建指针变量 int key left; int prev left; int cur prev 1; while (cur right) { //小于就进行交换如果相等就不交换提升效率 if (a[cur] a[key] prev ! cur) //先prev后交换 { Swap(a[cur], a[prev]); } cur; } //跳出循环--进行交换 Swap(a[prev], a[key]); return prev; }_6,非递归实现快速排序本质分析这里通过栈来实现主要通过栈后进先出的特点来实现对规定区间的排序排序还是在原来的区间上进行排序代码实现//快速排序--非递归实现--利用栈 void QuickSortNone(int* a, int left, int right) { //创建并初始化栈 ST st; STInit(st); STPush(st, right); STPush(st, left); //这次循环的结果要和下一次的循环对接 while (!STEmpty(st)) //当栈为空时就没有要排序的区间了 { //元素出栈--找到需要排序的区间 int begin STTop(st); STPop(st); int end STTop(st); STPop(st); //进行单次排序并找到key,进行分割 int key PartSort2(a, begin, end); //[begin,key-1] key [key1,end] //放入子序列为下次排序做准备--先放右边再放左边 if(key1 end) //区间中至少有两个元素 { STPush(st, end); STPush(st, key1); } if (begin key - 1) { STPush(st, key - 1); STPush(st, begin); } } }非递归实现快速排序的时间复杂度是O(N*logN)空间复杂度为O(logN)接下来我们考虑第一次调用到最深层次的节点时此时栈开辟的空间一定为最大值。计算这个最大值就是要计算的空间复杂度。由于整个过程相当于深度优先遍历当我们处理到这个区间时这个区间的兄弟区间还在栈中 其父亲区间一定已经出栈了其父亲区间的兄弟区间一定还在栈中再向上推导的父亲区间的兄弟区间还在栈中所以说除去第一层和最后一层每一层都有一个节点在栈中而第一层的一定不在栈中最后一层多一个在栈中所以总体来说就是高度logN7归并排序 Merge sort_1,核心思想归并排序的本质上是采用分治的思想先将原序列进行拆分 拆分为两个子数组在向下进行拆分直到拆分到数组中只有一个元素再把有序的子数组进行合并成一个新的有序数组直到合并成一个有序的数组。注意_2,代码实现//归并排序子函数--递归实现 void _MergeSort(int* a, int* tmp, int begin, int end) { //当区间只有一个数或区间不存在就返回 if (begin end) return; //先分割 int mid (begin end) / 2; //[begin,mid] [mid1,end] _MergeSort(a, tmp, begin, mid); _MergeSort(a, tmp, mid1, end); //进行合并 int begin1 begin, end1 mid; int begin2 mid1, end2 end; int i begin; //i的初始位置为begin //找小并尾插到新的数组当中 while (begin1 end1 begin2 end2) { if (a[begin1] a[begin2]) { tmp[i] a[begin1]; } else { tmp[i] a[begin2]; } } //将非空数组的其他数插入到tmp当中 while (begin1 end1) { tmp[i] a[begin1]; } while (begin2 end2) { tmp[i] 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); tmp NULL; }_3,时间和空间效率时间复杂度合并时每一层中的每一个数都要进行比较总共有高度 logN层所以时间复杂度为ON*logN空间复杂度额外开辟一个大小为n的数组所以 空间复杂度为O(N)_4,非递归实现归并排序补充修正代码实现//归并排序--非递归实现 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) { int begin1 i, end1 i gap - 1; int begin2 i gap, end2 i 2 * gap - 1; //第二组都越界由于第一组已经有序直接跳出停止归并 if (begin2 n - 1) { break; } //只有end2越界进行修正,继续归并 if (end2 n - 1) { 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]; } } //将非空数组的其他数插入到tmp当中 while (begin1 end1) { tmp[j] a[begin1]; } while (begin2 end2) { tmp[j] a[begin2]; } //每次拷贝回去方便下一次进行比较 memcpy(a i, tmp i, (end2 - i 1) * sizeof(int)); } gap * 2; } free(tmp); tmp NULL; }8,计数排序Counting sort_1,核心思想计数排序是一种非比较型的线性时间排序算法适用于在一定范围内的整数。通过统计元素的出现次数直接确定元素在排列后在数组空间中的位置不依赖元素的比较。_2,代码实现//计数排序 void CountSort(int* a, int n) { //找a数组的范围range int min a[0], max a[0]; int i 0; for(i0;in;i) { if (min a[i]) { min a[i]; } if (max a[i]) { max a[i]; } } int range (max - min 1); //创建数组count--使用calloc表示创建并初始化为0 int* count (int*)calloc(range,sizeof(int)); if (count NULL) { perror(calloc fail); return; } //将每个数据的出现次数记录到count数组当中 for (int i 0; i n; i) { count[a[i] - min]; } //进行排序 int j 0; for (i 0; i range; i) { while (count[i]--) { a[j] i min; } } free(count); }_3,时间和空间效率时间复杂度为前面循环N次后面循环range次所以最后为O(Nrange)空间复杂度:由于额外创建了一个大小为range的数组所以空间复杂度为O(range )该方法只适用于数组中的数据都是整数并且整数比较集中。三各种排序总结及稳定性各种排序的比较稳定性当待排序数组中有两个及以上相同的数据元素排序前后这几个相同元素的相对位置没有发生变化。简单来说排序后有相同元素的相对位置发生改变就表明该排序不稳定。排序后相同元素的相对位置没有发生改变就表明该排序稳定。直接插入排序由于插入元素前面的元素已经有序当要插入的元素和前面的某元素相等时插入的元素也只会插入到前面的那个元素的后面一个位置相对位置不会发生改变所以比较稳定。希尔排序由于在进行预排序时要进行分组当有两个相同元素在不同的组时在进行预排序时对每组元素的排序就有可能造成相对位置的改变所以不稳定。选择排序由于下面的情况所以不稳定。堆排序冒泡排序前面的元素和后面的元素进行比较如果相等不进行交换所以相对位置不会发生改变比较稳定。快速排序由于下面的情况所以不稳定归并排序是按照原来的位置进行拆分拆分不会导致相对位置的改变拆分后进行合并时每个元素都要和其他元素进行比较即使相同元素也是先排左区间的元素后排右区间的元素相对位置不会发生改变所以稳定。