DS：八大排序之归并排序、计数排序

                                               创作不易，感谢三连支持！！ 

一、归并排序

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++];elsetemp[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++];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-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){	//修正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(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++];elsetemp[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);//归并排序非递归版本2void 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];elsebreak;--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最后一定为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 = 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;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 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] = keypcur++;}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;}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(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++];elsetemp[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++];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-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){	//修正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

#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;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：http://www.rhkb.cn/news/259615.html

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

Python学习（16）|列表_遍历_排序_max_min_sum

Python学习（16）|列表_遍历_排序_max_min_sum

列表的遍历&#xff1a; a [10,20,30,40] for obj in a: #obj 是临时变量名称&#xff0c;随意起名print(obj) 执行结果&#xff1a; 复制列表所有的元素到新列表对象&#xff1a; list1 [30,40,50] list2 list1 #只是将list2也指向了列表对象。也就是说list…
阅读更多...
Maven - Plugins报错的正确解决之道

Maven - Plugins报错的正确解决之道

背景&#xff1a; 正确解决之道&#xff1a; 在自己本地Maven的安装目录中找到自己的仓库地址目录&#xff1a;直接搜索自己报错的插件文件&#xff0c;把它们删除&#xff0c;如图&#xff1a; 接着回到IDEA点击Maven刷新按钮重新加载即可&#xff1a;已解决 反例&#xff1…
阅读更多...
SORA给数字孪生带来哪些启示

SORA给数字孪生带来哪些启示

最近两天的朋友圈又被一则科技新闻刷屏了&#xff0c;那就是&#xff1a;OpenAI发布文生视频模型“Sora”。它是继ChatGPT之后&#xff0c;OpenAI又推出的一款震惊科技圈的产品&#xff0c;使AIGC向前迈了一大步。 数字孪生技术与AIGC&#xff08;人工智能生成内容&#xff09…
阅读更多...
多元统计分析课程论文-聚类效果评价

多元统计分析课程论文-聚类效果评价

数据集来源&#xff1a;Unsupervised Learning on Country Data (kaggle.com) 代码参考&#xff1a;Clustering: PCA| K-Means - DBSCAN - Hierarchical | | Kaggle 基于特征合成降维和主成分分析法降维的国家数据集聚类效果评价 目录 1.特征合成降维 2.PCA降维 3.K-Mean…
阅读更多...
集结低代码/零代码行业大咖，2024年领域内首场重磅峰会火热开启！

集结低代码/零代码行业大咖，2024年领域内首场重磅峰会火热开启！

低代码/零代码技术是一种创新的软件开发方法&#xff0c;旨在简化程序开发过程&#xff0c;使得即便是非专业开发者也能快速构建和部署应用程序。通过图形化界面和拖拽式操作&#xff0c;用户可以无需编写复杂的代码&#xff0c;就能完成应用程序的设计、开发和部署&#xff0c…
阅读更多...
tsmc12：boundary cell/tap cell的align VIA0 grid

tsmc12：boundary cell/tap cell的align VIA0 grid

更多学习内容请关注「拾陆楼」知识星球 拾陆楼知识星球入口 往期文章链接: tsmc12：via0的spacing问题（Via0.S.1） tsmc12 OD.L.5 DRC tsmc12：boundary cell注意事项
阅读更多...
2024年【R1快开门式压力容器操作】考试及R1快开门式压力容器操作考试内容

2024年【R1快开门式压力容器操作】考试及R1快开门式压力容器操作考试内容

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 R1快开门式压力容器操作考试参考答案及R1快开门式压力容器操作考试试题解析是安全生产模拟考试一点通题库老师及R1快开门式压力容器操作操作证已考过的学员汇总&#xff0c;相对有效帮助R1快开门式压力容器操作考试内…
阅读更多...
鸿蒙（HarmonyOS）项目方舟框架（ArkUI）之Marquee组件

鸿蒙（HarmonyOS）项目方舟框架（ArkUI）之Marquee组件

鸿蒙&#xff08;HarmonyOS&#xff09;项目方舟框架&#xff08;ArkUI&#xff09;之Marquee组件 一、操作环境 操作系统: Windows 10 专业版、IDE:DevEco Studio 3.1、SDK:HarmonyOS 3.1 二、Marquee组件 跑马灯组件&#xff0c;用于滚动展示一段单行文本&#xff0c;仅当…
阅读更多...
在 Python 中，通过列表字典创建 DataFrame 时，若字典的 key 的顺序不一样以及部分字典缺失某些键，pandas 将如何处理？

在 Python 中，通过列表字典创建 DataFrame 时，若字典的 key 的顺序不一样以及部分字典缺失某些键，pandas 将如何处理？

&#x1f349; CSDN 叶庭云&#xff1a;https://yetingyun.blog.csdn.net/ pandas 是一个快速、强大、灵活且易于使用的开源数据分析和处理工具&#xff0c;它是建立在 Python 编程语言之上的。 pandas 官方文档地址&#xff1a;https://pandas.pydata.org/ 在 Python 中&…
阅读更多...
多模态基础--- word Embedding

多模态基础--- word Embedding

1 word Embedding 原始的单词编码方式&#xff1a; one-hot&#xff0c;维度太大&#xff0c;不同单词之间相互独立&#xff0c;没有远近关系区分。 wordclass&#xff0c;将同一类单词编码在一起&#xff0c;此时丢失了类别和类别间的相关信息&#xff0c;比如class1和class3…
阅读更多...
小游戏和GUI编程(7) | SimpleNN 界面源码解析

小游戏和GUI编程(7) | SimpleNN 界面源码解析

小游戏和GUI编程(7) | SimpleNN 界面源码解析 0. 简介 SimpleNN 是 AdamYuan 在高中一年级时用 1 天时间写出来的简易 CNN, 使用 SFML 做 UI, 用于交互式输入手写数字&#xff0c;这个数字被训练好的 CNN 网络执行推理得到识别结果, 它的运行效果如下&#xff1a; 这一篇我们…
阅读更多...
java客运管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

java客运管理系统Myeclipse开发mysql数据库web结构java编程计算机网页项目

一、源码特点 java客运管理系统是一套完善的java web信息管理系统&#xff0c;对理解JSP java编程开发语言有帮助&#xff0c;系统具有完整的源代码和数据库&#xff0c;系统主要采用B/S模式开发。开发环境为TOMCAT7.0,Myeclipse8.5开发&#xff0c;数据库为Mysql5.0&#…
阅读更多...
安装Joplin Server私有化部署(docker)

安装Joplin Server私有化部署(docker)

安装Joplin Server私有化部署(docker) 前言: 老规矩官方文档链接 1. 首先拥有一个自己的云服务器(如果没有外网访问需求的话就随意吧) 安装docker安装方式 这里Joplin是使用PostgreSQL数据库的形式, 如果没有PostgreSQL库的话, Joplin默认使用的是SQLLite数据库 我这里使用的是…
阅读更多...
Shiro-11-web 介绍

Shiro-11-web 介绍

配置 将Shiro集成到任何web应用程序的最简单方法是在web.xml中配置一个Servlet ContextListener和过滤器&#xff0c;该Servlet了解如何读取Shiro的INI配置。 INI配置格式本身的大部分是在配置页面的INI部分中定义的&#xff0c;但是我们将在这里介绍一些额外的特定于web的部…
阅读更多...
入门级10寸加固行业平板—EM-I10J

入门级10寸加固行业平板—EM-I10J

亿道信息以其坚固耐用的智能终端设备而闻名&#xff0c;近日发布了一款理想入门级 10 英寸加固平板电脑—I10J。 EM-I10J​​ 这是一款 10 英寸的平板电脑&#xff0c;主要运行 Windows 10操作系统&#xff0c;带有硬化塑料外壳&#xff0c;具有 IP65 防水防尘功能和 MIL-STD 8…
阅读更多...
【Java EE初阶十七】网络原理（二）

【Java EE初阶十七】网络原理（二）

2. 传输层 2.2 TCP协议 2.2.2 关于可靠传输 4.滑动窗口 前面的三个机制&#xff0c;都是在保证 tcp 的可靠性&#xff1b; TCP 的可靠传输,是会影响传输的效率的.(多出了一些等待 ack 的时间,单位时间内能传输的数据就少了)&#xff1b; 滑动窗口,就让可靠传输对性能的影响,更…
阅读更多...
【大模型 知识图谱】ChatKBQA：KBQA知识图谱问答 + 大模型

【大模型 知识图谱】ChatKBQA：KBQA知识图谱问答 + 大模型

ChatKBQA&#xff1a;KBQA知识图谱问答 大模型 提出背景传统方法处理流程ChatKBQA处理流程对比优势 总结ChatKBQA框架概览特征1&#xff1a;逻辑形式生成特征2&#xff1a;无监督实体和关系检索特征3&#xff1a;参数高效的微调特征4&#xff1a;GQoT 可解释的查询执行特征5&a…
阅读更多...
实心陶瓷电阻器的基本原理？

实心陶瓷电阻器的基本原理？

什么是陶瓷电阻器&#xff1f; 陶瓷组合电阻器由精细研磨的绝缘体和导体的混合物组成&#xff0c;被压缩成圆柱形。连接端子&#xff0c;并在电阻器的外壳上涂上绝缘涂层。电阻根据绝缘体与导体混合物的比例进行控制。 陶瓷是一种优良的电绝缘体&#xff0c;也是一种极好的导热…
阅读更多...
【Linux】---Linux下基本指令（2）

【Linux】---Linux下基本指令（2）

目录 一、指令详细介绍1.1 cat 指令1.2 echo 指令1.3 more 指令1.4 less 指令1.5 head 指令1.6 tail 指令1.7 date 指令1.8 cal 指令1.9 find 指令1.10 grep 指令1.11 zip/unzip 指令1.12 tar 指令1.13 uname –r 指令&#xff1a; 一、指令详细介绍 1.1 cat 指令 语法&#…
阅读更多...
学习Android的第十六天

学习Android的第十六天

目录 Android 自定义 Adapter Adapter 接口 SpinnerAdapter ListAdapter BaseAdapter 自定义 BaseAdapter 参考文档 Android ListView 列表控件 ListView 的属性和方法 表头表尾分割线的设置 列表从底部开始显示 android:stackFromBottom 设置点击颜色 cacheColorH…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023