创作不易，感谢三连支持！！
一、归并排序
1.1 思想
归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide andConquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
还有一个关键点就是：归并一定要先拷贝到一个新数组里面，再拷贝到原数组！！
1.2 递归实现归并排序
根据上面的思路，我们来实现代码：
void _MergeSort(int* a, int begin, int end, int* temp) { if (begin == end) return;//设置递归返回条件 int mid = (begin + end) / 2; //开始分解 _MergeSort(a, begin, mid, temp);//左区间归并 _MergeSort(a, mid+1, end, temp);//右区间归并 //开始进行总归并 int begin1 = begin, end1 = mid;//设置指针指向左区间 int begin2 = mid + 1, end2 = end;//设置指针指向右区间 int i = begin;//用来遍历拷贝数组 while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环 { //谁小谁尾插 if (a[begin1] < a[begin2]) temp[i++] = a[begin1++]; else temp[i++] = a[begin2++]; } //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了 //以下两个while只会执行一个 while (begin1 <= end1) temp[i++] = a[begin1++]; while (begin2<=end2) temp[i++] = a[begin2++]; //归并完成，将temp的数据拷贝回去 memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));//因为递归，拷贝的不一定就是从头开始的,左闭右闭个数要+1; } void MergeSort(int* a, int n) { int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { perror("malloc fail"); exit(1); } //开辟成功，开始进行递归 _MergeSort(a, 0, n - 1, temp); }
要注意：递归的返回条件是begin==end！！因此归并排序每次拆分都是从中间拆分的，所以不可能会出现区间不存在的情况！！ 只有可能是区间只有一个元素的情况
1.3 非递归实现归并排序
怎么去思考非递归实现归并排序呢？？我们来画图理解：
那我们其实可以通过指针来实现各个子区间的有序,直接在原数组上建立两个指针
我们设置一个gap来分割区间
这里的问题就是，如何控制每次归并的子序列的范围？以及什么时候结束归并？
一、gap 控制几个为一组归并（gap一开始从1开始），则：
第一个子序列的起始是begin1 = i, end1 = i + gap -1;
第二个子序列的起始是begin2 = i+gap, end2 = i + 2 *gap - 1;
其中i是遍历一遍待排序的数组的下标，i从0开始。i每次应该跳2*gap步。
二、gap控制的是每次几个为一组我们 一开始是1个，2个、4个、8个，显然是2的倍数，所以gap每次乘等2即可！也不能一直让gap*=2下去，gap不可能大于等于数组的长度，所以当超过数组的长度是结束！
代码实现：
void MergeSortNonR(int* a, int n) { int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { perror("malloc fail"); exit(1); } //开辟成功 int gap = 1; while (gap < n) { int j = 0;//用来遍历拷贝数组 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; while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环 { //谁小谁尾插 if (a[begin1] < a[begin2]) temp[j++] = a[begin1++]; else temp[j++] = a[begin2++]; } //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了 //以下两个while只会执行一个 while (begin1 <= end1) temp[j++] = a[begin1++]; while (begin2 <= end2) temp[j++] = a[begin2++]; //归并完成，将temp的数据拷贝回去 } memcpy(a, temp, sizeof(int) * n);//一起拷贝回去 gap *= 2;//设置条件 } }
这样对吗？测试一下
如果我们将数加到10个呢？？
越界了！！因为我们之前那个情况是8个元素恰好是2的次方，所以无论怎么分割再归并，都不会越界，所以这个时候我们要考虑边界情况！！
修正版本1：
void MergeSortNonR(int* a, int n) { int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { perror("malloc fail"); exit(1); } //开辟成功 int gap = 1; while (gap < n) { int j = 0;//用来遍历拷贝数组 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 (end1 >= n || begin2 >= n) break; if (end2 >= n)//修正 end2 = n - 1; while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环 { //谁小谁尾插 if (a[begin1] <= a[begin2]) temp[j++] = a[begin1++]; else temp[j++] = a[begin2++]; } //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了 //以下两个while只会执行一个 while (begin1 <= end1) temp[j++] = a[begin1++]; while (begin2 <= end2) temp[j++] = a[begin2++]; //归并一次，拷贝一次 memcpy(a + i, temp + i, sizeof(int) * (end2-i+1));//一起拷贝回去 } gap *= 2;//设置条件 } }
修改版本2：
void MergeSortNonR2(int* a, int n) { int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { perror("malloc fail"); exit(1); } //开辟成功 int gap = 1; while (gap < n) { int j = 0;//用来遍历拷贝数组 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 (end1 >= n) { end1 = n - 1;//修正end1 //然后为了让begin2和end2不走循环，直接让他们区间不存在 begin2 = n; end2 = n - 1; } else if (begin2 >= n) { //不存在区间 begin2 = n; end2 = n - 1; } else if (end2 >= n) { //修正end2 end2 = n - 1; } while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环 { //谁小谁尾插 if (a[begin1] <= a[begin2]) temp[j++] = a[begin1++]; else temp[j++] = a[begin2++]; } //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了 //以下两个while只会执行一个 while (begin1 <= end1) temp[j++] = a[begin1++]; while (begin2 <= end2) temp[j++] = a[begin2++]; } gap *= 2;//设置条件 memcpy(a, temp, sizeof(int) * n); } }
1.4 归并排序的优化
假设我们的数据非常大，比如100万个数据，一开始的拆分效率是很高的，但是当数据变得很少的时候比如8个，这个时候再继续拆，效率其实很低的
我们当递归只剩大概10个元素的时候，停止递归，使用直接插入排序
void _MergeSort(int* a, int begin, int end, int* temp) { if (begin == end) return;//设置递归返回条件 if (end - begin + 1 < 10) { InsertSort(a+begin, end - begin + 1);//优化 return; } int mid = (begin + end) / 2; //开始分解 _MergeSort(a, begin, mid, temp);//左区间归并 _MergeSort(a, mid+1, end, temp);//右区间归并 //开始进行总归并 int begin1 = begin, end1 = mid;//设置指针指向左区间 int begin2 = mid + 1, end2 = end;//设置指针指向右区间 int i = begin;//用来遍历拷贝数组 while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环 { //谁小谁尾插 if (a[begin1] < a[begin2]) temp[i++] = a[begin1++]; else temp[i++] = a[begin2++]; } //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了 //以下两个while只会执行一个 while (begin1 <= end1) temp[i++] = a[begin1++]; while (begin2<=end2) temp[i++] = a[begin2++]; //归并完成，将temp的数据拷贝回去 memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));//因为递归，拷贝的不一定就是从头开始的,左闭右闭个数要+1; } void MergeSort(int* a, int n) { int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { perror("malloc fail"); exit(1); } //开辟成功，开始进行递归 _MergeSort(a, 0, n - 1, temp); }
1.5 复杂度分析
时间复杂度：O(N*logN)
他像二叉树的后序遍历，高度是logN，每一层合计归并时O(N)遍历一遍数组
空间复杂度：O(N)
N为辅助数组的长度，和原数组的长度一样！
二、计数排序
2.1 思想
思想：计数排序又称为鸽巢原理，是对哈希直接定址法的变形应用，是一种非比较排序！
步骤：
1、统计相同元素的出现次数
2、根据统计的结果将序列回收到原来的序列中
2.2 计数排序的实现
代码实现：
void CountSort(int* a, int n) { int min = a[0], max = a[0];//根据最值来确定范围 //遍历原数组找范围 for (int 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* temp = (int*)calloc(range, sizeof(int));//因为要初始化0，所以用calloc //也可以先用malloc，然后用memset(temp,0,sizeof(int)*range) if (temp == NULL) { perror("calloc fail"); exit(1); } //开辟成功后，开始遍历原数组计数 for (int i = 0; i < n; i++) temp[a[i] - min]++; //遍历完后，计数也完成了，开始遍历计数数组，恢复原数组 int k = 0;//用来恢复原数组 for (int j = 0; j < range; j++) while (temp[j]--)//一直减到0，就会跳下一层循环，直到遍历完！！ a[k++] = j + min; }
2.3 复杂度分析
时间复杂度：O(MAX(N,范围))
空间复杂度：O(范围)
2.4 计数排序的缺陷
1，只适合范围相对集中的数据
2、只适用与整型，因为只有整型才能和下标建立联系
三、内排序和外排序
四、稳定性
五、八大排序对比
4.1 代码实现测速度
void TestOP()//测试速度 { srand((unsigned int)time(NULL)); const int N = 10000; 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); int* a8 = (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]; a8[i] = a1[i]; } //clock计入程序走到当前位置的时间 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(); BubbleSort(a4, N); int end4 = clock(); int begin5 = clock(); HeapSort(a5, N); int end5 = clock(); int begin6 = clock(); QuickSort(a6, 0, N - 1); int end6 = clock(); int begin7 = clock(); MergeSort(a7, N); int end7 = clock(); int begin8 = clock(); CountSort(a8, N); int end8 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("BubbleSort:%d\n", end4 - begin4); printf("HeapSort:%d\n", end5 - begin5); printf("QuickSort:%d\n", end6 - begin6); printf("MergeSort:%d\n", end7 - begin7); printf("CountSort:%d\n", end8 - begin8); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); free(a8); } int main() { TestOP(); }
测试一下：
N=10000
N=100000
我们发现：
希尔排序、堆排序、快排、归并排、计数牌是一个量级的
N=10000000
直接插入排、选择排序、冒泡排序是一个量级的
4.2 复杂度稳定性比较
六、八大排序全部代码
建议大家把博主的有关八大排序的代码都看一下
主要是前三个文件，后面四个文件是为了快排的栈实现和队列实现准备的！！
6.1 sort.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<string.h> #include<time.h> void ArrPrint(int* a, int n);//用来打印结果 void Swap(int* p1, int* p2);//进行交换 void InsertSort(int* a, int n);//直接插入排序 void ShellSort(int* a, int n);//希尔排序 void SelectSort(int* a, int n);//选择排序 void AdjustDown(int* a, int n, int parent);//向下调整算法 void HeapSort(int* a, int n);//堆排序 void BubbleSort(int* a, int n);//冒泡排序 int GetMidIndex(int* a, int left, int right);//快排优化——三数取中 int GetMidIndex2(int* a, int left, int right);//三数取中再优化 int PartSort1(int* a, int left, int right);//hoare基准排序 int PartSort2(int* a, int left, int right);//挖坑基准排序 int PartSort3(int* a, int left, int right);//前后指针基准排序 void QuickSort(int* a, int left, int right);//递归快排 void QuickSort2(int* a, int left, int right);//三路归并快排 void QuickSortNonR1(int* a, int left, int right);//栈实现非递归快排 void QuickSortNonR2(int* a, int left, int right);//队列实现非递归快排 void HeapSort(int* a, int n);//堆排序 void BubbleSort(int* a, int n);//冒泡排序 void _MergeSort(int* a, int begin, int end,int *temp);//归并排序的子函数（用来递归） void MergeSort(int* a, int n);//归并排序 void MergeSortNonR(int* a, int n);//归并排序非递归 void MergeSortNonR2(int* a, int n);//归并排序非递归版本2 void CountSort(int* a, int n);//计数排序
6.2 sort.c
#include"Sort.h" #include"Stack.h" #include"Queue.h" void ArrPrint(int* a, int n) { for (int i = 0; i < n; i++) printf("%d ", a[i]); } void Swap(int* p1, int* p2) { int temp = *p1; *p1 = *p2; *p2 = temp; } void InsertSort(int* a, int n) { for (int i = 0; i < n - 1; i++) { int end = i; int temp = a[i+1]; while (end >= 0) { if (a[end] > temp)//如果前面的数比后面的数大，就前面元素插入到后面的位置 a[end + 1] = a[end]; else break; --end; } a[end + 1] = temp;//不写在循环里面，是避免end减成-1，此时说明新加入的牌是最小的，正好放在一开始的位置 } } void ShellSort(int* a, int n) { //gap>1 预排序 //gap=1 直接插入排序 int gap = n; while (gap > 1) { gap = gap / 3 + 1;//这是为了保证gap最后一定为1 for (int i = 0; i < n - gap; i++) { int end = i; int temp = a[i + gap]; while (end >= 0) { if (a[end] > temp)//如果前面的数比后面的数大，就前面元素插入到后面的位置 a[end + gap] = a[end]; else break; end -= gap; } a[end + gap] = temp; } } } // void SelectSort(int* a, int n) { int left = 0; int right = n - 1; while (left < right) { int min = left; int max = left; for (int i = left+1; i <= right; i++) { if (a[min] > a[i]) min = i; if (a[max] < a[i]) max = i; } //这里要考虑一种情况，就是如果最大的数恰好就在最左端，那么就会导致第二次swap换到后面的就不是最大的数而是最小的数了 Swap(&a[min], &a[left]); //如果max和begin重叠，修正一下 if (max == left) max = min; Swap(&a[max], &a[right]); left++; right--; } } int GetMidIndex(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[right] < a[left]) return left; else return right; } else//a[left] >a[mid] { if (a[mid] > a[right]) return mid; else if (a[right] > a[left]) return left; else return right; } } int GetMidIndex2(int* a, int left, int right) { int mid = left + (rand() % (right - left)); if (a[left] < a[mid]) { if (a[mid] < a[right]) return mid; else if (a[right] < a[left]) return left; else return right; } else//a[left] >a[mid] { if (a[mid] > a[right]) return mid; else if (a[right] > a[left]) return left; else return right; } } int PartSort1(int* a, int left, int right)//hoare基准排序 { int mid=GetMidIndex(a, left, right); Swap(&a[mid], &a[left]); int keyi = left; while (left < right) { //右先找比key大的 while (left < right&&a[right] >= a[keyi]) right--; //左找比key小的 while (left < right && a[left] <= a[keyi]) left++; //找到后，就交换 Swap(&a[left], &a[right]); } //此时相遇了，把相遇的位置和keyi的位置交换 Swap(&a[left], &a[keyi]); return left; } int PartSort2(int* a, int left, int right)//挖坑基准排序 { int mid = GetMidIndex(a, left, right); Swap(&a[mid], &a[left]); int key = a[left];//记住key的值 int hole = left;//开始挖坑 while (left < right) { //右先找比key大的 while (left < right && a[right] >= key) right--; //找到后，填坑，然后挖新坑 a[hole] = a[right]; hole = right; //左找比key小的 while (left < right && a[left] <= key) left++; //找到后，填坑，然后挖新坑 a[hole] = a[left]; hole = left; } //此时相遇了，把key值放在坑里 a[hole] = key; return hole; } int PartSort3(int* a, int left, int right) //前后指针基准排序 { int mid = GetMidIndex(a, left, right); Swap(&a[mid], &a[left]); int prev = left; int cur = left + 1; int keyi = left; while (cur <= right)//cur走出数组循环停止 { //cur一直在走，如果遇到比keyi小的，就停下来等perv走一步后交换，再接着走 if (a[cur] < a[keyi]&&++prev!=cur) Swap(&a[prev], &a[cur]); cur++; } //cur出去后，prev的值和keyi交换 Swap(&a[keyi], &a[prev]); return prev; } void QuickSort(int* a, int left, int right) { if (left >= right) return; int keyi = PartSort1(a, left, right); //根据基准值去分割区间，继续进行基准排序 QuickSort(a, left, keyi - 1); QuickSort(a, keyi+1,right); } void QuickSort2(int* a, int left, int right) { if (left >= right) return; int mid = GetMidIndex2(a, left, right); Swap(&a[mid], &a[left]); int phead = left; int pcur = left + 1; int ptail = right; int key = a[left]; while (pcur <= ptail) { if (a[pcur] < key) { Swap(&a[pcur], &a[phead]); pcur++; phead++; } else if (a[pcur] > key) { Swap(&a[pcur], &a[ptail]); ptail--; } else//a[pcur] = key pcur++; } QuickSort2(a, left, phead - 1); QuickSort2(a, ptail+1,right); } void QuickSortNonR1(int* a, int left, int right) { Stack st; StackInit(&st); //把区间压进去,一定要先压右区间！！ StackPush(&st, right); StackPush(&st, left); while (!StackEmpty(&st)) { //将数据弹出来进行进准计算 int left = StackTop(&st); StackPop(&st); int right= StackTop(&st); StackPop(&st); //进行基准计算 int keyi = PartSort3(a, left, right); //分割区间（left keyi-1）keyi（keyi+1，right） //如果对应的区间还能分割，就继续压,要注意要先压后面在压前面 if (keyi + 1 < right) { StackPush(&st, right); StackPush(&st, keyi+1); } if (keyi - 1 > left) { StackPush(&st, keyi-1); StackPush(&st,left); } } //会一直到栈为空，此时就拍好序了！！ StackDestory(&st); } void QuickSortNonR2(int* a, int left, int right) { Queue q; QueueInit(&q); QueuePush(&q, left); QueuePush(&q, right); while (!QueueEmpty(&q)) { int left = QueueFront(&q); QueuePop(&q); int right = QueueFront(&q); QueuePop(&q); int keyi = PartSort3(a, left, right); if (keyi - 1 > left) { QueuePush(&q, left); QueuePush(&q, keyi-1); } if (keyi + 1 <right) { QueuePush(&q, keyi +1); QueuePush(&q, right); } } QueueDestory(&q); } //向下调整算法 void AdjustDown(int* a, int n, int parent)//升序要建大堆 { int child = parent * 2 + 1;//假设左孩子比右孩子大 while (child < n) { //如果假设错误，就认错 if (child + 1 < n && a[child] < a[child + 1]) 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--; } } void BubbleSort(int* a, int n) { for (int i = 0; i < n - 1; i++) //每一趟拍好一个，最后排完n-1个，最后一个数就没必要比了 { int flag = 1;//假设有序 for (int j = 0; j < n - i - 1; j++)//第一趟需要比较的n-1次，第二次需要比较n-2次…… //所以结束条件跟着i变化 { if (a[j] > a[j + 1]) { Swap(&a[j], &a[j + 1]); flag = 0;//如果没有发生交换，说明不符合有序 } } if (flag == 1) break; } } void _MergeSort(int* a, int begin, int end, int* temp) { if (begin == end) return;//设置递归返回条件 if (end - begin + 1 < 10) { InsertSort(a+begin, end - begin + 1);//优化 return; } int mid = (begin + end) / 2; //开始分解 _MergeSort(a, begin, mid, temp);//左区间归并 _MergeSort(a, mid+1, end, temp);//右区间归并 //开始进行总归并 int begin1 = begin, end1 = mid;//设置指针指向左区间 int begin2 = mid + 1, end2 = end;//设置指针指向右区间 int i = begin;//用来遍历拷贝数组 while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环 { //谁小谁尾插 if (a[begin1] < a[begin2]) temp[i++] = a[begin1++]; else temp[i++] = a[begin2++]; } //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了 //以下两个while只会执行一个 while (begin1 <= end1)//等于才能保证稳定性！！ temp[i++] = a[begin1++]; while (begin2<=end2) temp[i++] = a[begin2++]; //归并完成，将temp的数据拷贝回去 memcpy(a + begin, temp + begin, sizeof(int) * (end - begin + 1));//因为递归，拷贝的不一定就是从头开始的,左闭右闭个数要+1; } void MergeSort(int* a, int n) { int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { perror("malloc fail"); exit(1); } //开辟成功，开始进行递归 _MergeSort(a, 0, n - 1, temp); } void MergeSortNonR(int* a, int n) { int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { perror("malloc fail"); exit(1); } //开辟成功 int gap = 1; while (gap < n) { int j = 0;//用来遍历拷贝数组 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 (end1 >= n || begin2 >= n) break; if (end2 >= n)//修正 end2 = n - 1; while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环 { //谁小谁尾插 if (a[begin1] <= a[begin2]) temp[j++] = a[begin1++]; else temp[j++] = a[begin2++]; } //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了 //以下两个while只会执行一个 while (begin1 <= end1) temp[j++] = a[begin1++]; while (begin2 <= end2) temp[j++] = a[begin2++]; //归并一次，拷贝一次 memcpy(a + i, temp + i, sizeof(int) * (end2-i+1));//一起拷贝回去 } gap *= 2;//设置条件 } } void MergeSortNonR2(int* a, int n) { int* temp = (int*)malloc(sizeof(int) * n); if (temp == NULL) { perror("malloc fail"); exit(1); } //开辟成功 int gap = 1; while (gap < n) { int j = 0;//用来遍历拷贝数组 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 (end1 >= n) { end1 = n - 1;//修正end1 //然后为了让begin2和end2不走循环，直接让他们区间不存在 begin2 = n; end2 = n - 1; } else if (begin2 >= n) { //不存在区间 begin2 = n; end2 = n - 1; } else if (end2 >= n) { //修正end2 end2 = n - 1; } while (begin1 <= end1 && begin2 <= end2)//只要有一个先拷贝完，就跳出循环 { //谁小谁尾插 if (a[begin1] <= a[begin2]) temp[j++] = a[begin1++]; else temp[j++] = a[begin2++]; } //这个时候其中一个区间先遍历完了，这个时候另一个没有遍历的区间插入就可以了 //以下两个while只会执行一个 while (begin1 <= end1) temp[j++] = a[begin1++]; while (begin2 <= end2) temp[j++] = a[begin2++]; } gap *= 2;//设置条件 memcpy(a, temp, sizeof(int) * n); } } void CountSort(int* a, int n) { int min = a[0], max = a[0];//根据最值来确定范围 //遍历原数组找范围 for (int 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* temp = (int*)calloc(range, sizeof(int));//因为要初始化0，所以用calloc //也可以先用malloc，然后用memset(temp,0,sizeof(int)*range) if (temp == NULL) { perror("calloc fail"); exit(1); } //开辟成功后，开始遍历原数组计数 for (int i = 0; i < n; i++) temp[a[i] - min]++; //遍历完后，计数也完成了，开始遍历计数数组，恢复原数组 int k = 0;//用来恢复原数组 for (int j = 0; j < range; j++) while (temp[j]--)//一直减到0，就会跳下一层循环，直到遍历完！！ a[k++] = j + min; }
6.3 test.c
#include"Sort.h" void TestOP()//测试速度 { srand((unsigned int)time(NULL)); const int N = 1000000; 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); int* a8 = (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]; a8[i] = a1[i]; } //clock计入程序走到当前位置的时间 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(); //BubbleSort(a4, N); int end4 = clock(); int begin5 = clock(); HeapSort(a5, N); int end5 = clock(); int begin6 = clock(); QuickSort(a6, 0, N - 1); int end6 = clock(); int begin7 = clock(); MergeSort(a7, N); int end7 = clock(); int begin8 = clock(); CountSort(a8, N); int end8 = clock(); printf("InsertSort:%d\n", end1 - begin1); printf("ShellSort:%d\n", end2 - begin2); printf("SelectSort:%d\n", end3 - begin3); printf("BubbleSort:%d\n", end4 - begin4); printf("HeapSort:%d\n", end5 - begin5); printf("QuickSort:%d\n", end6 - begin6); printf("MergeSort:%d\n", end7 - begin7); printf("CountSort:%d\n", end8 - begin8); free(a1); free(a2); free(a3); free(a4); free(a5); free(a6); free(a7); free(a8); } int main() { TestOP(); }
6.4 stack.h
#pragma once #include<stdio.h> #include<stdbool.h> #include<stdlib.h> #include<assert.h> typedef int STDataType; //支持动态增长的栈 typedef struct Stack { STDataType* a; int top;//栈顶 int capacity;//栈容量 }Stack; void StackInit(Stack* ps);//初始化栈 void StackPush(Stack* ps, STDataType x);//入栈 void StackPop(Stack* ps);//出栈 STDataType StackTop(Stack* ps);//获取栈顶元素 int StackSize(Stack* ps);//获取栈中有效元素个数 bool StackEmpty(Stack* ps);//检测栈是否为空，为空返回true void StackDestory(Stack* ps);//销毁栈
6.5 stack.c
#include"Stack.h" void StackInit(Stack* ps) { ps->a = NULL; ps->top = ps->capacity = 0; } void StackPush(Stack* ps, STDataType x) { assert(ps); //判断是否需要扩容 if (ps->top == ps->capacity) { int newcapacity = ps->capacity == 0 ? 4 : 2 * ps->capacity; STDataType* temp = (STDataType*)realloc(ps->a,sizeof(STDataType) * newcapacity); if (temp == NULL) { perror("realloc fail"); exit(1); } ps->a = temp; ps->capacity = newcapacity; } //压栈 ps->a[ps->top++] = x; } void StackPop(Stack* ps) { assert(ps); //如果栈为空，则没有删除的必要 assert(!StackEmpty(ps)); ps->top--; } STDataType StackTop(Stack* ps) { assert(ps); //如果栈为空，不可能有栈顶元素 assert(!StackEmpty(ps)); return ps->a[ps->top - 1]; } int StackSize(Stack* ps) { assert(ps); return ps->top; } bool StackEmpty(Stack* ps) { assert(ps); return ps->top == 0; } void StackDestory(Stack* ps) { free(ps->a); ps->a = NULL; ps->top = ps->capacity = 0; }
6.6 queue.h
#pragma once #include<stdio.h> #include<stdlib.h> #include<stdbool.h> #include<assert.h> typedef int QDatatype;//方便后面修改存储数据的数据类型 typedef struct QueueNode//队列结点的数据结构 { QDatatype data;//存储数据 struct QueueNode* next; }QNode; typedef struct Queue { QNode* phead;//指向队头，用于出队（头删） QNode* ptail;//指向队尾，用于入队（尾插） int size;//记录有效元素个数 }Queue;//创建一个队列相关结构体 void QueueInit(Queue* pq);//队列的初始化 void QueuePush(Queue* pq, QDatatype x);//队列的入队（尾插） void QueuePop(Queue* pq);//队列的出队(头删) QDatatype QueueFront(Queue* pq);//获取队列头部元素 QDatatype QueueBack(Queue* pq);//获取队列尾部元素 int QueueSize(Queue* pq);//获取队列中有效元素个数 bool QueueEmpty(Queue* pq);//判断队列是否为空 void QueueDestory(Queue* pq);//队列的销毁
6.7 queue.c
#include"Queue.h" void QueueInit(Queue* pq) { assert(pq);//判断传的是不是空指针 pq->phead = pq->ptail = NULL; pq->size = 0;//因为队列不像栈一样，有一个top表示栈顶元素的下标 //所以如果我们想知道这个队列的有效数据个数，就必须遍历队列 //由于其先进先出的特性，我们默认只能访问到头元素和尾元素 //所以必须访问一个头元素，就出队列一次，这样才能实现遍历 //但是这样的代价太大了，为了方便，我们直接用size } void QueuePush(Queue* pq, QDatatype x) { assert(pq); //入队必须从队尾入！ QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新节点 if (newnode==NULL)//如果新节点申请失败，退出程序 { perror("malloc fail"); } //新节点创建成功，给新节点初始化一下 newnode->data = x; newnode->next = NULL; //开始入队 //如果直接尾插的话，由于会用到ptail->next,所以得考虑队列为空的情况 if (pq->ptail== NULL)//如果为空，直接把让新节点成为phead和ptail { //按道理来说，如果ptail为空，phead也应该为空 // 但是有可能会因为我们的误操作使得phead不为空，这个时候一般是我们写错的问题 //所以使用assert来判断一下，有问题的话会及时返回错误信息 assert(pq->phead == NULL); pq->phead = pq->ptail = newnode; } else { pq->ptail->next = newnode; pq->ptail = newnode; } pq->size++; } void QueuePop(Queue* pq) { assert(pq); //如果队列为空，没有删除的必要 assert(!QueueEmpty(pq)); //队列中的出队列相当于链表的头删 //如果直接头删，那么如果队列只有一个有效数据的话，那么我们将phead的空间释放掉，但是没有将ptail给置空 //这样会导致ptail成为一个野指针，所以我们需要考虑只有一个节点多个节点的情况 if (pq->phead->next == NULL)//一个节点的情况,直接将这个节点释放并置空即可 { free(pq->phead); pq->phead = pq->ptail = NULL;//置空，防止野指针 } else//多个节点的情况，直接头删 { QNode* next = pq->phead->next;//临时指针记住下一个节点 free(pq->phead); pq->phead = next;//让下一个节点成为新的头 } pq->size--; } QDatatype QueueFront(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//队列如果为空，则不可能找得到队列头元素 //队列不为空的时候，直接返回phead指向的数据 return pq->phead->data; } QDatatype QueueBack(Queue* pq) { assert(pq); assert(!QueueEmpty(pq));//队列如果为空，则不可能找得到队尾元素 //队列不为空的时候，直接返回ptail指向的数据 return pq->ptail->data; } int QueueSize(Queue* pq) { assert(pq); return pq->size; } bool QueueEmpty(Queue* pq)//链表为空的情况，可以根据容量，也可以根据ptail==NULL&&phead==NULL { assert(pq); return pq->ptail == NULL && pq->phead == NULL; } void QueueDestory(Queue* pq) { assert(pq);//判断传的是不是空指针 //要逐个节点释放 QNode* pcur = pq->phead; while (pcur) { QNode* next = pcur->next; free(pcur); pcur = next; } pq->phead = pq->ptail = NULL; pq->size = 0; }
