数据结构与算法⑰(第五章_八大排序)(完整代码+动图+详解+对比)（中）：https://developer.aliyun.com/article/1513587
4.归并排序
4.1 归并排序递归版
归并排序，从其思想上看就很适合使用递归来实现，并且用递归实现也比较简单。
其间我们需要申请一个与待排序列大小相同的数组用于合并过程两个有序的子序列，
合并完毕后再将数据拷贝回原数组。
void _MergeSort(int* arr, int left, int right, int* tmp)//归并排序递归版的子函数 { if (left >= right)//归并结束条件：当只有一个数据或是序列不存在时（认为有序） { return; } int mid = left + (right - left) / 2; //[left,mid] [mid+1,right] 分治递归，让子区间有序 _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid + 1, right, tmp); //将两段子区间进行归并，归并结果放在tmp中 int left1 = left, right1 = mid; int left2 = mid + 1, right2 = right; int i = left; while (left1 <= right1 && left2 <= right2) { //将较小的数据优先放入tmp，放入后++ if (arr[left1] < arr[left2]) { tmp[i++] = arr[left1++]; } else { tmp[i++] = arr[left2++]; } } //当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面 while (left1 <= right1)//有一个while循环条件肯定不满足，不用管 { tmp[i++] = arr[left1++]; } while (left2 <= right2) { tmp[i++] = arr[left2++]; } //归并完后，拷贝回原数组 //for (int j = left; j <= right; j++) //{ // arr[j] = tmp[j]; //} memcpy(arr + left, tmp + left, (right - left + 1) * sizeof(int)); } void MergeSort(int* arr, int sz) { int* tmp = (int*)malloc(sizeof(int) * sz);//申请一个与原数组大小相同的空间 if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } _MergeSort(arr, 0, sz - 1, tmp);//函数前加_用来表示其子函数，常用来递归 free(tmp); tmp = NULL; }
4.2 归并排序非递归版
前面快排的非递归里讲过递归的缺点， 归并排序递归改非递归的两种方法中不用数据结构的栈，
而是直接使用循环。我们只需要控制每次参与合并的元素个数即可，最终便能使序列变为有序：
由于我们操纵的是数组的下标，所以我们需要借助数组，来帮我们存储上面递归得到的数组下标，
和递归的区别就是，递归要将区间一直细分，要将左区间一直递归划分完了，再递归划分右区间，
而借助数组的非递归是一次性就将数据处理完毕，并且每次都将下标拷贝回原数组
归并排序的基本思路是将待排序序列a[0…n-1]看成是n个长度为1的有序序列，
相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，
得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列
当然，以上例子是一个待排序列长度比较特殊的例子，
（以上只适用于数组个数为2的次方，否则会越界）
我们若是想写出一个广泛适用的程序，必定需要考虑到某些极端情况：
情况一：当最后一个小组进行合并时，第二个小区间存在，但是该区间元素个数不够gap个，
这时我们需要在合并序列时，对第二个小区间的边界进行控制。
情况二：
当最后一个小组进行合并时，第二个小区间不存在，此时便不需要对该小组进行合并。
情况三：
当最后一个小组进行合并时，第二个小区间不存在，并且第一个小区间的元素个数不够gap个，此时也不需要对该小组进行合并。（可与情况二归为一类）
void MergeSortNonR(int* arr, int sz) { int* tmp = (int*)malloc(sizeof(int) * sz); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } int gap = 1; while (gap < sz) { for (int i = 0; i < sz; i += 2 * gap)//控制每次参与合并的元素个数 { // [i, i + gap - 1] [i + gap, i + 2 * gap - 1] int left1 = i, right1 = i + gap - 1; int left2 = i + gap, right2 = i + 2 * gap - 1; // 防止越界核心思想：right1、left2、right2都有可能越界 if (right1 >= sz || left2 >= sz)// right1越界 或者 left2 越界都不需要归并 { break; } else if (right2 >= sz)// right2 越界，需要归并，修正right2 { right2 = sz - 1; } int n = right2 - left1 + 1;//记录要拷贝的个数 int j = left1; while (left1 <= right1 && left2 <= right2) { if (arr[left1] < arr[left2]) { tmp[j++] = arr[left1++]; } else { tmp[j++] = arr[left2++]; } } while (left1 <= right1) { tmp[j++] = arr[left1++]; } while (left2 <= right2) { tmp[j++] = arr[left2++]; } // 把归并小区间拷贝回原数组 for (int k = i; k <= right2; k++) { arr[k] = tmp[k]; } //memcpy(arr + i, tmp + i, sizeof(int) * n); } gap *= 2; } free(tmp); tmp = NULL; }
5.计数排序
八大排序最后一个排序：计数排序，又叫非比较排序，非比较排序只适用于整数。
顾名思义，该算法不是通过比较数据的大小来进行排序的，
而是通过统计数组中相同元素出现的次数，然后通过统计的结果将序列回收到原来的序列中。
非比较排序还有桶排序和基数排序，但校招不考，用处也不大，只是计数排序的思想比较好，
所以这里只讲计数排序。
计数排序动图：
上列中的映射方法称为绝对映射，即arr数组中的元素是几就在count数组中下标为几的位置++，
但这样会造成空间浪费。例如，我们要将数组：1020,1021,1018，进行排序，
难道我们要开辟1022个整型空间吗？
若是使用计数排序，我们应该使用相对映射，简单来说，数组中的最小值就相对于count数组中的0下标，数组中的最大值就相对于count数组中的最后一个下标。这样，对于数组：1020,1021,1018，我们就只需要开辟用于储存4个整型的空间大小了，此时count数组中下标为i的位置记录的实际上是1018+i这个数出现的次数。
绝对映射：count数组中下标为i的位置记录的是arr数组中数字i出现的次数。
相对映射：count数组中下标为i的位置记录的是arr数组中数字min+i出现的次数。（负数也能排）
计数排序只适用于数据范围较集中的序列的排序，若待排序列的数据较分散，则会造成空间浪费。
5.1 计数排序代码：
oid CountSort(int* arr, int sz) { int min = arr[0]; int max = arr[0]; for (int i = 0; i < sz; i++)//找出数组中的最大值和最小值,为了后面开辟数组 { if (arr[i] < min) { min = arr[i]; } if (arr[i] > max) { max = arr[i]; } } int range = max - min + 1;//min和max之间的自然数个数（包括min和max本身） int* count = (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间，并将内存空间置0 if (count == NULL) { printf("calloc fail\n"); exit(-1); } for (int i = 0; i < sz; i++)//统计相同元素出现次数（相对映射） { count[arr[i] - min]++; } int i = 0; for (int j = 0; j < range; j++)//根据统计结果将序列回收到原来的数组中 { while (count[j]--) { arr[i++] = j + min; } } free(count); count = NULL; }
6.前七大排序复杂度和稳定性对比
由于计数排序是非比较排序，只适用于整数等各种原因，我们这里只讨论前七大排序。
6.1稳定性的概念：
假定在待排序的记录序列中，存在多个具有相同的关键字的记录，
若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，
而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
排序算法的稳定性通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序
与排序后它们两个先后位置顺序相同。
我们对冒泡排序很熟悉冒泡排序是把大的元素往后调，小的元素往前调。比较都发生在相邻的两个元素之间，如果两个元素相等，是不会发生交换的，所以相同元素的前后顺序没有改变，所以冒泡排序是稳定的排序。
再说选择排序，选择排序最重要的思想，就是假设某个数是最小的或最大的，
它是给某个位置选择无序区元素中最小的那个。可以先举个例子，比如5 2 5 4 1 这个序列，
选择排序会假设2是最小的，然后拿他和别的数去比，找到一个最小的，放到2所在的位置。
所以在这个排序中，第一趟的时候5会和1交换，两个5的相对位置就发生了改变，
有些资料说选择排序是稳定的，这是错的，选择排序是不稳定的排序。
学了这么久了，下面直接给出一张图，可以自己先试着写一遍，不要背，理解了才是最好的
6.2对比图
图中希尔排序最坏的情况也达不到O（N^2），所以只需记平均的就好，
快速排序加上三数取中的优化后出现时间最坏的概率几乎没有。
7.内排序和外排序（了解）
内部排序：数据元素全部放在内存中的排序。
外部排序：是因排序的数据很大，一次不能容纳全部的排序记录，
在排序过程中还需要访问外部存储器的排序。
我们通常所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。
我们前面比较的七大排序中都能用于内排序，归并排序在内排序和外排序都能用。
假设现在有10亿个整数（4GB）存放在文件A中，需要我们进行排序，
而内存一次只能提供512MB空间，归并排序解决该问题的基本思路如下：
1、每次从文件A中读取八分之一，即512MB到内存中进行排序（内排序），并将排序结果写入到一个文件中，然后再读取八分之一，重复这个过程。那么最终会生成8个各自有序的小文件（A1~A8）。
2、对生成的8个小文件进行11合并，最终8个文件被合成为4个，然后再11合并，就变成2个文件了，最后再进行一次11合并，就变成1个有序文件了。
注意：这里将两个文件进行11合并，并不是先将两个文件读入内存然后进行合并，因为内存装不下。这里的11合并是利用文件输入输出函数，从两个文件中各自读取一个数据，然后进行比较，将较小的数据写入到一个新文件中去，然后再读取，再比较，再写入，最终将两个文件中的数据全部写入到另一个文件中去，那么此时这个文件又是一个有序的文件了。
8.关于排序的选择题
有关一些概念的题尽量不放了，特别是对比图那一部分要自己能描述出来（时间，空间，复杂度）
8.1 排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。用冒泡排序对数列4 5 6 3 2 1进行升序排序，则第3趟之后的结果是（ ）
A.4 3 2 1 5 6
B.4 5 3 2 1 6
C.2 1 3 4 5 6
D.3 2 1 4 5 6
8.2 使用选择排序对长度为100的数组进行排序，则比较的次数为（ ）
A.5050
B.4950
C.4851
D.2475
8.3 有字符序列 FBJGEAIDCH，现在打算对它按字母的字典顺序用希尔排序进行排序，那么在第一趟后（步长为5）的序列为（ ）
A.CAEBFDIGJH
B.AIDCHFBJGE
C.ABDCEFIJGH
D.BFJGEAIDCH
8.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
8.5 对数字序列28 16 32 12 60 2 5 72进行升序的快速排序（以第一个关键码为基准的方法），一次划分后的结果为（ ）
A.2 5 12 16 28 60 32 72
B.2 16 5 12 28 60 32 72
C.2 16 12 5 28 60 32 72
D.5 16 2 12 28 32 60 72
8.6 下列选项中，不可能是快速排序第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
8.7 用某种排序方法对关键字序列 15 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.快速排序
8.8下面的排序算法中，初始数据集的排列顺序对算法的性能无影响的有
① 快速排序
② 希尔排序
③ 插入排序
④ 堆排序
⑤ 归并排序
⑥ 选择排序
A.①④⑤
B.④⑤⑥
C.②③⑥
D.②③⑤⑥
答案解析
8.1答案：D
冒泡排序，一趟排序会把未排序元素中的最值移动到未排序元素的最后一个位置，
第一趟：4 5 3 2 1 6
第二趟：4 3 2 1 5 6
第三趟：3 2 1 4 5 6
8.2答案：B
（注意这里没说应该是没有优化的选择排序）
选择排序，每次都要在未排序的所有元素中找到最值，
如果有n个元素，则
第一次比较次数： n - 1
第二次比较次数： n - 2
....
第n - 1次比较次数： 1
所有如果n = 100
则比较次数的总和：99 + 98 + ...... + 1（Sn=[n(a1+an)]/2，Sn=na1+[n(n-1)d]/2）
用第一个公式，99 * ( 1 + 99 ) / 2 = 99 * 50 = 4950，共4950次。
8.3答案：C
希尔排序按照步长把元素进行小组划分，每个小组元素进行插入排序。
所以如果步长为5，则整个数组被会划分成5组数据：
FA BI JD GC EH
所以一趟排序之后的结果为：
ABDCEFIJGH
8.4答案：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
8.5答案：B
快速排序以基准值为中心，对元素进行划分，这里以28为基准值，则小于28的和大于28的进行交换，完成一次划分
首先：32和5交换： 28 16 5 12 60 2 32 72
然后60和2交换： 28 16 5 12 2 60 32 72
最后28和最后一个小于28的元素进行交换：
2 16 5 12 28 60 32 72
8.6答案：C
这里说的是快排的第二趟，即在第一趟快排的结果的基础上进行的，如果已经经过了一趟排序，则会通过第一趟选择的基准值划分两个子区间，每个子区间也会以区间内选择的基准值划分成两部分。
A: 第一趟的基准值可以为2， 第二趟的基准值可以为3
B: 第一趟的基准值可以为2， 第二趟的基准值可以为9
C: 第一趟的基准值只能是9，但是第二趟的基准值就找不出来，没有符合要求的值作为基准值，所以不可能是一个中间结果。
D: 第一趟的基准值可以为9， 第二趟的基准值可以为5
8.7答案：D
此题中的排序是快排二分排序的思想，第一趟的基准值是25，第二趟的基准值分别是20，47，
第三趟的基准值分别是15，21，35，68
8.8答案：B
快排： 初始顺序影响较大，有序是，性能最差
插入: 接近有序，性能最好
希尔：希尔是对插入排序的优化，这种优化是在无序的序列中才有明显的效果，如果序列接近有序，反而是插入最优。
堆排，归并，选择对初始顺序不敏感
9.八大排序完整代码
（大练习就是手撕了）可以用每个排序都跑一下这道力扣题：（快排过不了据说是放了5万个2）
Sort.h
#pragma once #include<stdio.h> #include<assert.h> #include<stdlib.h> #include<string.h> #include<time.h> void printArr(int* arr, int sz); void Swap(int* p1, int* p2); void InsertSort(int* arr, int sz);//1.直接插入排序 void ShellSort(int* arr, int sz);//2.希尔排序 void SelectSort(int* arr, int sz);//3.选择排序 void HeapSort(int* arr, int sz);//4.堆排序 void BubbleSort(int* arr, int sz);//5.冒泡排序 void QuickSort(int* arr, int left, int right);//6.快速排序递归版 void QuickSortNonR(int* arr, int left, int right);//6.快速排序非递归版 void MergeSort(int* arr, int sz);//7.归并排序递归版 void MergeSortNonR(int* arr, int sz);;//7.归并排序非递归版 void CountSort(int* arr, int sz);//8.计数排序
Sort.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Sort.h" #include "Stack.h" void printArr(int* arr, int sz) { for (int i = 0;i <= sz - 1;i++) { printf("%d ", arr[i]); } printf("\n"); } void Swap(int* p1, int* p2) { int tmp = *p1; *p1 = *p2; *p2 = tmp; } void InsertSort(int* arr, int sz)//1.直接插入排序 { assert(arr != NULL); for (int i = 0;i <= sz - 2;i++) { int end = i;//把数组第一个元素当作有序，像打扑克牌摸牌排序一样 int x = arr[end + 1]; //x已经保存了a[end + 1] 所以后面再覆盖也可以 因此end只能落在sz-2 while (end >= 0) { if (arr[end] > x) { arr[end + 1] = arr[end]; end--; } else { break; } } arr[end + 1] = x; } } void ShellSort(int* arr, int sz)//2.希尔排序 { int gap = sz; //多次预排序(gap > 1)+直接插入排序(gap == 1) while (gap > 1)//gap进去以后才除所以大于1就行 { //两种取gap的方法： //gap = gap / 2;//一次跳一半 gap = gap / 3 + 1; //加一是为了保证最后一次gap小于3的时候 //能够有gap等于1来表示直接插入排序 //多组同时搞： for (int i = 0; i < sz - gap; i++) { int end = i; int x = arr[end + gap]; while (end >= 0) { if (arr[end] > x) { arr[end + gap] = arr[end]; end -= gap; } else { break; } } arr[end + gap] = x; } } } void SelectSort(int* arr, int sz)//3.选择排序 { int begin = 0; int end = sz - 1; while (begin < end) { int mini = begin; int maxi = end; int i = 0; for (i = begin;i <= end;i++) { //选出[begin,end]中最大和最小的 if (arr[i] < arr[mini]) { mini = i; } if (arr[i] > arr[maxi]) { maxi = i; } } //int arr[] = { 1,6,5,4,7,8,9,2,0,3 }; Swap(&arr[begin], &arr[mini]); //这里需要考虑第一个值放最大值的情况，如果第一个值为最大值,此时最大值位置被移动 if (begin == maxi) { maxi = mini;//最大的值被换到了mini的位置，更新最大值的位置 } Swap(&arr[end], & arr[maxi]); begin++; end--; } } void justDown(int* arr, int sz, int father_idx)//大堆下调 { int child_idx = father_idx * 2 + 1; // 计算出左孩子的值（默认认为左孩子大） while (child_idx < sz) // 最坏情況：调到叶子（child_idx >= 数组范围时必然已经调到叶子） { if ((child_idx + 1 < sz) && (arr[child_idx + 1] > arr[child_idx])) { // 如果右孩子存在且右孩子比左孩子大 child_idx = child_idx + 1;// 让其代表右孩子 } if (arr[child_idx] > arr[father_idx])//如果孩子的值大于父亲的值（不符合大堆的性质） { Swap(&arr[child_idx], &arr[father_idx]); father_idx = child_idx; // 更新下标往下走 child_idx = father_idx * 2 + 1; // 计算出该节点路线的新父亲 } else // 如果孩子的值小于父亲的值（符合大堆的性质） { break; } } } void HeapSort(int* arr, int sz)//4.堆排序 { //创建大堆，选出最大的数，时间：O(N) int father = ((sz - 1) - 1) / 2; // 计算出最后一个叶子节点的父亲 while (father >= 0) { justDown(arr, sz, father); father--; } //交换后调堆 时间：O(N * logN) int end = sz - 1; while (end > 0) { Swap(&arr[0], &arr[end]); justDown(arr, end, 0); end--; } } void BubbleSort(int* arr, int sz)//5.冒泡排序 { int i = 0; int j = 0; for (i = 0;i < sz - 1;i++) { int flag = 1; for (j = 0;j < sz - 1 - i;j++) { if (arr[j] > arr[j + 1]) { Swap(&arr[j], &arr[j + 1]); } flag = 0; } if (flag) { break; } } } int GetMidIndex(int* arr, int left, int right)//三数取中 { int mid = left + (right - left) / 2; if (arr[mid] > arr[left]) { if (arr[mid] < arr[right]) return mid; else if (arr[left] > arr[right]) return left; else return right; } else { if (arr[mid] > arr[right]) return mid; else if (arr[left] > arr[right]) return right; else return left; } } int PartSort1(int* arr, int left, int right)//Hoare法快速排序 { int midIndex = GetMidIndex(arr, left, right);//加上三数取中 Swap(&arr[left], &arr[midIndex]);//把中间元素和最左边元素换了就行 int keyi = left; while (left < right) { //右边先走 找小 控制不要错开不要越界 while (left < right && arr[right] >= arr[keyi]) { --right; } //左边再走 找大 控制不要错开不要越界 while (left < right && arr[left] <= arr[keyi]) { ++left; } Swap(&arr[left], &arr[right]); } Swap(&arr[left], &arr[keyi]);//交换相遇的地方和关键字的位置 return left;//返回关键字的位置 } int PartSort2(int* arr, int left, int right)//挖坑法快速排序 { int midIndex = GetMidIndex(arr, left, right);//加上三数取中 int pit = midIndex; int keyi = pit; while (left < right) { while (left < right && arr[right] >= arr[keyi]) { right--; } arr[pit] = arr[right]; pit = right; while (left < right && arr[left] <= arr[keyi]) { left++; } arr[pit] = arr[left]; pit = left; } arr[pit] = arr[keyi]; return pit; } int PartSort3(int* arr, int left, int right)//前后指针法快速排序 { int midIndex = GetMidIndex(arr, left, right);//加上三数取中 Swap(&arr[left], &arr[midIndex]);//把中间元素和最左边元素换了就行 int prev = left; int cur = left + 1; int keyi = left; while (cur <= right) { /*while (cur <= right && arr[cur] >= arr[keyi]) { cur++; } if (cur <= right) { prev++; Swap(&arr[cur], &arr[prev]); cur++; }*/ if (arr[cur] < arr[keyi] && ++prev != cur)//反正都要cur++，注意这里prev已经++了 { Swap(&arr[cur], &arr[prev]); } cur++;//前面注释的优化 } Swap(&arr[prev], &arr[keyi]); return prev; } void QuickSort(int* arr, int left, int right)//6.快速排序递归版 { if (left >= right) { return; } if (right - left + 1 < 19)//可以自己取，官方是十几 { InsertSort(arr + left, right - left + 1); } else { //int keyi = PartSort1(arr, left, right); //int keyi = PartSort2(arr, left, right); int keyi = PartSort3(arr, left, right); QuickSort(arr, left, keyi - 1); QuickSort(arr, keyi + 1, right); } } void QuickSortNonR(int* arr, int left, int right)//6.快速排序非递归版 { Stack st; StackInit(&st); StackPush(&st, right);//为了更类似上面的递归就先入右 StackPush(&st, left); while (!StackEmpty(&st)) { int begin = StackTop(&st); StackPop(&st); int end = StackTop(&st); StackPop(&st); int keyi = PartSort3(arr, begin, end); //区间被成两部分了 [begin,keyi-1] [keyi+1,end] if (keyi + 1 < end)//先处理右 { StackPush(&st, end); StackPush(&st, keyi + 1); } if(begin < keyi - 1) { StackPush(&st, keyi - 1); StackPush(&st, begin); } } StackDestroy(&st); } void _MergeSort(int* arr, int left, int right, int* tmp)//归并排序递归版的子函数 { if (left >= right)//归并结束条件：当只有一个数据或是序列不存在时（认为有序） { return; } int mid = left + (right - left) / 2; //[left,mid] [mid+1,right] 分治递归，让子区间有序 _MergeSort(arr, left, mid, tmp); _MergeSort(arr, mid + 1, right, tmp); //将两段子区间进行归并，归并结果放在tmp中 int left1 = left, right1 = mid; int left2 = mid + 1, right2 = right; int i = left; while (left1 <= right1 && left2 <= right2) { //将较小的数据优先放入tmp，放入后++ if (arr[left1] < arr[left2]) { tmp[i++] = arr[left1++]; } else { tmp[i++] = arr[left2++]; } } //当遍历完其中一个区间，将另一个区间剩余的数据直接放到tmp的后面 while (left1 <= right1)//有一个while循环条件肯定不满足，不用管 { tmp[i++] = arr[left1++]; } while (left2 <= right2) { tmp[i++] = arr[left2++]; } //归并完后，拷贝回原数组 //for (int j = left; j <= right; j++) //{ // arr[j] = tmp[j]; //} memcpy(arr + left, tmp + left, (right - left + 1) * sizeof(int)); } void MergeSort(int* arr, int sz)//7.归并排序递归版 { int* tmp = (int*)malloc(sizeof(int) * sz);//申请一个与原数组大小相同的空间 if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } _MergeSort(arr, 0, sz - 1, tmp);//函数前加_用来表示其子函数，常用来递归 free(tmp); tmp = NULL; } void MergeSortNonR(int* arr, int sz)//7.归并排序非递归版 { int* tmp = (int*)malloc(sizeof(int) * sz); if (tmp == NULL) { printf("malloc fail\n"); exit(-1); } memset(tmp, 0, sizeof(int) * sz); int gap = 1; while (gap < sz) { for (int i = 0; i < sz; i += 2 * gap)//控制每次参与合并的元素个数 { // [i, i + gap - 1] [i + gap, i + 2 * gap - 1] int left1 = i, right1 = i + gap - 1; int left2 = i + gap, right2 = i + 2 * gap - 1; // 防止越界核心思想：right1、left2、right2都有可能越界 if (right1 >= sz || left2 >= sz)// right1越界 或者 left2 越界都不需要归并 { break; } else if (right2 >= sz)// right2 越界，需要归并，修正right2 { right2 = sz - 1; } int n = right2 - left1 + 1;//记录要拷贝的个数 int j = left1; while (left1 <= right1 && left2 <= right2) { if (arr[left1] <= arr[left2])//加个等于就是稳定的（后面会讲稳定性） { tmp[j++] = arr[left1++]; } else { tmp[j++] = arr[left2++]; } } while (left1 <= right1) { tmp[j++] = arr[left1++]; } while (left2 <= right2) { tmp[j++] = arr[left2++]; } // 把归并小区间拷贝回原数组 //for (int k = i; k <= right2; k++) //{ // arr[k] = tmp[k]; //} memcpy(arr + i, tmp + i, sizeof(int) * n); } gap *= 2; } free(tmp); tmp = NULL; } void CountSort(int* arr, int sz)//8.计数排序 { int min = arr[0]; int max = arr[0]; for (int i = 0; i < sz; i++)//找出数组中的最大值和最小值,为了后面开辟数组 { if (arr[i] < min) { min = arr[i]; } if (arr[i] > max) { max = arr[i]; } } int range = max - min + 1;//min和max之间的自然数个数（包括min和max本身） int* count = (int*)calloc(range, sizeof(int));//开辟可储存range个整型的内存空间，并将内存空间置0 if (count == NULL) { printf("calloc fail\n"); exit(-1); } for (int i = 0; i < sz; i++)//统计相同元素出现次数（相对映射） { count[arr[i] - min]++; } int i = 0; for (int j = 0; j < range; j++)//根据统计结果将序列回收到原来的数组中 { while (count[j]--) { arr[i++] = j + min; } } free(count); count = NULL; }
Test.c
#define _CRT_SECURE_NO_WARNINGS 1 #include"Sort.h" // 测试排序的性能对比 void TestOP() { srand(time(0)); const int N = 10000;//可以改N和屏蔽效率低的排序来测试 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 = 0; i < N; ++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 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); int end6 = clock(); int begin7 = clock(); BubbleSort(a7, N); int end7 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); 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("BubbleSort:%d\n", end7 - begin7); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); } int main() { int arr[] = { 1,6,5,4,7,8,9,2,0,3 }; int sz = sizeof(arr) / sizeof(arr[0]); printArr(arr, sz); //InsertSort(arr, sz); //ShellSort(arr, sz); //SelectSort(arr, sz); //HeapSort(arr, sz); //BubbleSort(arr, sz); QuickSort(arr, 0, sz - 1); //QuickSortNonR(arr, 0, sz - 1); //MergeSort(arr, sz); //MergeSortNonR(arr,sz); //CountSort(arr,sz); printArr(arr, sz); TestOP(); return 0; }
Stack.h
#pragma once #include <stdio.h> #include <stdlib.h> #include <assert.h> #include <stdbool.h> typedef int StackDataType; typedef struct Stack { StackDataType* array; //数组 int top; //栈顶 int capacity; //容量 } Stack; void StackInit(Stack* ps); void StackDestroy(Stack* ps); void StackPush(Stack* ps, StackDataType x); bool StackEmpty(Stack* ps); void StackPop(Stack* ps); StackDataType StackTop(Stack* ps); int StackSize(Stack* ps);
Stack.c
#define _CRT_SECURE_NO_WARNINGS 1 #include "Stack.h" void StackInit(Stack* ps)//初始化 { assert(ps); ps->array = NULL; ps->top = 0; // ps->top = -1 ps->capacity = 0; } void StackDestroy(Stack* ps)//销毁 { assert(ps); free(ps->array); ps->array = NULL; ps->capacity = ps->top = 0; } void StackPush(Stack* ps, StackDataType x)//进栈 { assert(ps); if (ps->top == ps->capacity) { int new_capacity = ps->capacity == 0 ? 4 : ps->capacity * 2; StackDataType* tmp_arr =(StackDataType *) realloc(ps->array, sizeof(StackDataType) * new_capacity); if (tmp_arr == NULL) { printf("realloc failed!\n"); exit(-1); } // 更新 ps->array = tmp_arr; ps->capacity = new_capacity; } ps->array[ps->top] = x;// 填入数据 ps->top++; } bool StackEmpty(Stack* ps)//判断栈是否为空 { assert(ps); return ps->top == 0; //等于0就是空，就是真 } void StackPop(Stack* ps)// 出栈 { assert(ps); //assert(ps->top > 0); //防止top为空 assert(!StackEmpty(ps)); ps->top--; } StackDataType StackTop(Stack* ps)//返回栈顶数据 { assert(ps); //assert(ps->top > 0); //防止top为空 assert(!StackEmpty(ps)); return ps->array[ps->top - 1]; } int StackSize(Stack* ps) //计算栈的大小 { assert(ps); return ps->top;// 因为我们设定top是指向栈顶的下一个，所以top就是size }
