网站建设课程设计要求,自己建立网站怎么搞,营销型网站制作步骤五个,装修技术培训去哪里学创作不易#xff0c;感谢三连支持#xff01;#xff01;
一、归并排序
1.1 思想 归并排序#xff08;MERGE-SORT#xff09;是建立在归并操作上的一种有效的排序算法,该算法是采用分治法#xff08;Divide andConquer#xff09;的一个非常典型的应用。将已有序的子… 创作不易感谢三连支持
一、归并排序
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, mid1, 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];elsetemp[i] a[begin2];}//这个时候其中一个区间先遍历完了这个时候另一个没有遍历的区间插入就可以了//以下两个while只会执行一个while (begin1 end1)temp[i] a[begin1];while (begin2end2)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);
}
要注意递归的返回条件是beginend因此归并排序每次拆分都是从中间拆分的所以不可能会出现区间不存在的情况 只有可能是区间只有一个元素的情况
1.3 非递归实现归并排序
怎么去思考非递归实现归并排序呢我们来画图理解 那我们其实可以通过指针来实现各个子区间的有序,直接在原数组上建立两个指针
我们设置一个gap来分割区间 这里的问题就是如何控制每次归并的子序列的范围以及什么时候结束归并 一、gap 控制几个为一组归并gap一开始从1开始则 第一个子序列的起始是begin1 i, end1 i gap -1; 第二个子序列的起始是begin2 igap, 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];elsetemp[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];elsetemp[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-i1));//一起拷贝回去}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){ //修正end2end2 n - 1;}while (begin1 end1 begin2 end2)//只要有一个先拷贝完就跳出循环{//谁小谁尾插if (a[begin1] a[begin2])temp[j] a[begin1];elsetemp[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(abegin, end - begin 1);//优化return;}int mid (begin end) / 2;//开始分解_MergeSort(a, begin, mid, temp);//左区间归并_MergeSort(a, mid1, 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];elsetemp[i] a[begin2];}//这个时候其中一个区间先遍历完了这个时候另一个没有遍历的区间插入就可以了//以下两个while只会执行一个while (begin1 end1)temp[i] a[begin1];while (begin2end2)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();
} 测试一下
N10000 N100000 我们发现
希尔排序、堆排序、快排、归并排、计数牌是一个量级的
N10000000 直接插入排、选择排序、冒泡排序是一个量级的
4.2 复杂度稳定性比较 六、八大排序全部代码
建议大家把博主的有关八大排序的代码都看一下
主要是前三个文件后面四个文件是为了快排的栈实现和队列实现准备的
6.1 sort.h
#pragma once
#includestdio.h
#includestdlib.h
#includestring.h
#includetime.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);//归并排序非递归版本2void CountSort(int* a, int n);//计数排序
6.2 sort.c
#includeSort.h
#includeStack.h
#includeQueue.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[i1];while (end 0){if (a[end] temp)//如果前面的数比后面的数大就前面元素插入到后面的位置a[end 1] a[end];elsebreak;--end;}a[end 1] temp;//不写在循环里面是避免end减成-1此时说明新加入的牌是最小的正好放在一开始的位置}
}void ShellSort(int* a, int n)
{//gap1 预排序//gap1 直接插入排序int gap n;while (gap 1){gap gap / 3 1;//这是为了保证gap最后一定为1for (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];elsebreak;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 left1; 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;elsereturn right;}else//a[left] a[mid]{if (a[mid] a[right])return mid;else if (a[right] a[left])return left;elsereturn 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;elsereturn right;}else//a[left] a[mid]{if (a[mid] a[right])return mid;else if (a[right] a[left])return left;elsereturn right;}
}int PartSort1(int* a, int left, int right)//hoare基准排序
{int midGetMidIndex(a, left, right);Swap(a[mid], a[left]);int keyi left;while (left right){//右先找比key大的while (left righta[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, keyi1,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] keypcur;}QuickSort2(a, left, phead - 1);QuickSort2(a, ptail1,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-1keyikeyi1right//如果对应的区间还能分割就继续压,要注意要先压后面在压前面if (keyi 1 right){StackPush(st, right);StackPush(st, keyi1);}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;}elsebreak;}
}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(abegin, end - begin 1);//优化return;}int mid (begin end) / 2;//开始分解_MergeSort(a, begin, mid, temp);//左区间归并_MergeSort(a, mid1, 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];elsetemp[i] a[begin2];}//这个时候其中一个区间先遍历完了这个时候另一个没有遍历的区间插入就可以了//以下两个while只会执行一个while (begin1 end1)//等于才能保证稳定性temp[i] a[begin1];while (begin2end2)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];elsetemp[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-i1));//一起拷贝回去}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){ //修正end2end2 n - 1;}while (begin1 end1 begin2 end2)//只要有一个先拷贝完就跳出循环{//谁小谁尾插if (a[begin1] a[begin2])temp[j] a[begin1];elsetemp[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
#includeSort.hvoid 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
#includestdio.h
#includestdbool.h
#includestdlib.h
#includeassert.htypedef 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
#includeStack.hvoid 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
#includestdio.h
#includestdlib.h
#includestdbool.h
#includeassert.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
#includeQueue.hvoid 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 (newnodeNULL)//如果新节点申请失败退出程序{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)//链表为空的情况可以根据容量也可以根据ptailNULLpheadNULL
{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;
}
