C学习（数据结构）--＞排序

目录

一、直接插入排序

 二、希尔排序

三、直接选择排序

四、快速排序

 1、取基准值

1）hoare找基准值​编辑

 2） 挖坑法找基准值​编辑

 3）快慢指针找基准值​编辑

 2、递归快速排序

3、非递归快速排序

​编辑

五、归并排序

​编辑

六、计数排序

七、堆排序

八、冒泡排序​编辑

九、总代码 

栈

Sort.h

Sort.cpp

main.cpp

---

一、直接插入排序

将需要排序的序列分成两部分，一部分序列已经排好序的为有序序列而还未排序的为无序序列，没每一次排序都是从无序序列中拿取数据直接插入到有序序列当中

//数据互换
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//直接插入排序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;//有序数组长度int tmp = arr[end + 1];//从无序数组从拿取数据//直接插入while (end >= 0){//arr[end] > arr[end + 1]if (arr[end] > tmp)//找比tmp小的数据{arr[end + 1] = arr[end];//比tmp大的数据往后移动一步end--;}else{break;}}//跳出while循环前end自减过，所以是 end + 1 arr[end + 1] = tmp;}
}

 二、希尔排序

直接插入排序的优化，通过将数组划分为数个小组，每个小组各自使用直接插入排序，然后再次细分小组，继续使用直接插入排序，直到每个小组的数据量为 1 时，排序结束

//希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){//划分小组//有可能出现 gap == 0 的情况,所以要保证最后一次gap == 1gap = gap / 3 + 1;//每个小组的直接插入排序for (int i = 0; i < n - gap; i++)//每两个数间隔gap，所以 n - gap{int end = i;//n - gap - 1;int tmp = arr[end + gap];while (end >= 0){//arr[end] > arr[end + 1]if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}arr[end + gap] = tmp;}}}
}

三、直接选择排序

每次通过直接在无序数组内寻找最大最小值，进行排序

//直接选择排序
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int min = begin, max = begin;//找最大最小值for (int i = begin + 1; i <= end; i++){//最小值if (arr[i] < arr[min]){min = i;}//最大值if (arr[i] > arr[max]){max = i;}}//避免max和begin在同一个位置if (max == begin){max = min;}Swap(&arr[min], &arr[begin++]);Swap(&arr[max], &arr[end--]);}
}

四、快速排序

在数组内取一个基准值，将比基准值小和大的值各自放在基准值的两边， 然后再在分好的两边各取一个基准值，重复操作，直到分的每个部分都只剩一个数据，排序结束

 1、取基准值

1）hoare找基准值

//hoare版本找基准值
int _HoareQuickSort(int* arr, int left, int right)
{int key = left;left++;while (left <= right){//找比基准值小的值while (left <= right && arr[right] > arr[key]){right--;}//找比基准值大的值while (left <= right && arr[left] < arr[key]){left++;}//防止最后一次 left > rightif (left <= right){Swap(&arr[left++], &arr[right--]);}}

 2） 挖坑法找基准值

//挖坑法找基准值
int _PitQuickSort(int* arr, int left, int right)
{int hole = left;//坑int key = arr[hole];//基准值while (left < right){//找比基准值小的值while (left < right && arr[right] >= key){right--;}arr[hole] = arr[right];//将找到的值放入坑内hole = right;//记录坑的位置//找比基准值大的值while (left < right && arr[left] < key){left++;}arr[hole] = arr[left];//将找到的值放入坑内hole = left;//记录坑的位置}arr[hole] = key;return hole;
}

 3）快慢指针找基准值

//lomuto前后指针找基准值
int _LomutoQuickSort(int* arr, int left, int right)
{int prev = left, pcur = left + 1;int key = left;while (pcur <= right){//寻找比基准值小的值if (arr[pcur] < arr[key] && ++prev != pcur) {Swap(&arr[pcur], &arr[prev]);}pcur++;}Swap(&arr[key], &arr[prev]);return prev;
}

 2、递归快速排序

//快速排序
void QuickSort(int* arr, int left,int right)
{if (left >= right){return;}//找基准值int key = _PitQuickSort(arr, left, right);//左子序列QuickSort(arr, left, key - 1);//右子序列QuickSort(arr, key + 1, right);
}

3、非递归快速排序

需要使用栈，通过栈来模拟递归，栈详见C学习（数据结构）--＞栈-CSDN博客

//非递归快速排序
//借用数据结构-栈
void StackQuickSort(int* arr, int left, int right)
{ST st;STInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){//取左右栈顶int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int prev = begin;int pcur = begin + 1;int key = begin;//双指针法找基准值while (pcur <= end){if (arr[pcur] < arr[key] && ++prev != pcur){Swap(&arr[prev], &arr[pcur]);}pcur++;}Swap(&arr[prev], &arr[key]);key = prev;//基准值划分左右区间：[begin,key-1],[key+1,end]if (key + 1 < end){StackPush(&st, end);StackPush(&st, key + 1);}if (key - 1 > begin){StackPush(&st, key - 1);StackPush(&st, begin);}}STDestroy(&st);
}

五、归并排序

通过递归，将一个无序数组分为两个长度相同或者相近的数组，然后在分好的数组再次各自分两个数组，反复操作，直到数组不能再分为止，此时递归开始返回，在返回前，将数组按数据从小到大两两合并，当递归结束时，排序完成。

//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right){return;}int mid = (left + right) / 2;_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);//合并两个数组 [left,mid] [mid+1,right]int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}//上面的循环结束，是因为 begin1 || begin2  越界，将剩下未排序的数据继续排序while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//排序完成，拷贝tmp到arrfor (int i = left; i <= right; i++){arr[i] = tmp[i];}
}void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);//归并排序_MergeSort(arr, 0, n - 1, tmp);free(tmp);tmp = NULL;
}

六、计数排序

通过统建立新数组统计数据内的数据出现的次数来排序 

这样的统计有缺点，第一，如果原数组中最小值为1000，那么就会新申请的数组中，就会至少申请1000个以上的空间，又由于最小值为1000，那么下标前1000个空间就会用不上，会很大程度上浪费空间 。第二，如果遇到负整数等情况，数组也无法做统计，无法进行排序。

将排序优化， 不是以最大值作为最大下标，而是以 最大值和最小值的差值作为最大下标，

例：max = 1022，min = 1000，那么最大下标就为 max - min = 22

在统计中，不是原数组中的数据（ arr[i] ）作为下标，而是原数组中的数据减去最小值 ( arr[i]-min )

作为下标，那么最后将统计好的数组拷贝回去原数组时，是将下标加上原数组中数据的最小值

（ i+min ）拷贝进原数组中。

这样可以大程度地节省空间，且可以统计负整数等。

//计数排序
void ConunSort(int* arr, int n)
{int max = arr[0], min = arr[0];//找最大值和最小值的差值for (int i = 1; i < n; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail!!!");exit(1);}//初始化数组memset(count, 0, range * sizeof(int));//统计数组每个数据出现的次数for (int i = 0; i < n; i++){count[arr[i] - min]++;}//取count数据放入arr中int index = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min;}}
}

七、堆排序

具体看C学习（数据结构）--＞ 实现顺序结构二叉树-CSDN博客

//堆排序
//数据的向上调整(小堆)
void AdjustUpSmall(int* arr, int child)
{assert(arr);int parent = (child - 1) / 2;while (child > 0){if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//数据的向下调整(小堆)
void AdjustDownSmall(int* arr, int parent, int n)//n表示有效数据个数
{int child = parent * 2 + 1;//左孩子while (child < n)//如果左孩子在数组内{//比较左右孩子大小if (child + 1 < n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//数据的向上调整(大堆)
void AdjustUpBig(int* arr, int child)
{assert(arr);int parent = (child - 1) / 2;while (child > 0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//数据的向下调整(大堆)
void AdjustDownBig(int* arr, int parent, int n)//n表示有效数据个数
{int child = parent * 2 + 1;//左孩子while (child < n)//如果左孩子在数组内{//比较左右孩子大小if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序
//排升序，建大堆
//排降序，建小堆void HeapSortSmall(int* arr, int n)
{建小堆，向上排序法建堆//for (int i = 0; i < n; i++)//{//	AdjustUpSmall(arr, i);//}//建小堆，向下排序法建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDownSmall(arr, i, n);}//排降序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDownSmall(arr, 0, end);end--;}
}void HeapSortBig(int* arr, int n)
{//建大堆，向下排序法建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDownBig(arr, i, n);}//排升序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDownBig(arr, 0, end);end--;}
}

八、冒泡排序

//冒泡排序
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){if (arr[j] < arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange == 0){break;}}
}

 九、其他

测试各个排序的运行效率

void test01()
{srand(time(0));int numsize = 50000;int begin = 0;int end = 0;int* a1 = (int*)malloc(sizeof(int) * numsize);int* a2 = (int*)malloc(sizeof(int) * numsize);int* a3 = (int*)malloc(sizeof(int) * numsize);int* a4 = (int*)malloc(sizeof(int) * numsize);int* a5 = (int*)malloc(sizeof(int) * numsize);int* a6 = (int*)malloc(sizeof(int) * numsize);int* a7 = (int*)malloc(sizeof(int) * numsize);int* a8 = (int*)malloc(sizeof(int) * numsize);int* a9 = (int*)malloc(sizeof(int) * numsize);for (int i = 0; i < numsize; 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];a9[i] = a1[i];}//冒泡排序begin = clock();BubbleSort(a1, numsize);end = clock();printf("冒泡排序：%d\n",end-begin);//堆排序begin = clock();HeapSortSmall(a2, numsize);end = clock();printf("堆排序：%d\n", end - begin);//直接插入排序begin = clock();InsertSort(a3, numsize);end = clock();printf("直接插入排序：%d\n", end - begin);//希尔排序begin = clock();ShellSort(a4, numsize);end = clock();printf("希尔排序：%d\n", end - begin);//直接选择排序begin = clock();SelectSort(a5, numsize);end = clock();printf("直接选择排序：%d\n", end - begin);//快速排序begin = clock();QuickSort(a6, 0, numsize - 1);end = clock();printf("快速排序：%d\n", end - begin);//非递归快速排序begin = clock();StackQuickSort(a7, 0, numsize - 1);end = clock();printf("非递归快速排序：%d\n", end - begin);//归并排序begin = clock();MergeSort(a8, numsize);end = clock();printf("归并排序：%d\n", end - begin);//计数排序begin = clock();ConunSort(a9, numsize);end = clock();printf("计数排序：%d\n", end - begin);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);free(a8);free(a9);a1 = NULL;a2 = NULL;a3 = NULL;a4 = NULL;a5 = NULL;a6 = NULL;a7 = NULL;a8 = NULL;a9 = NULL;
}int main()
{//测试test01();return 0;
}

运行结果

九、总代码 

栈

Stack.h 和 Stack.cpp 详见C学习（数据结构）--＞栈-CSDN博客

Sort.h

#pragma once
#define _CRT_SECURE_NO_WARNINGS 1#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<time.h>
#include<memory.h>//数据互换
void Swap(int* x, int* y);//冒泡排序
void BubbleSort(int* arr, int n);//数据的向上调整(小堆)
void AdjustUpSmall(int* arr, int child);//数据的向下调整(小堆)
void AdjustDownSmall(int* arr, int parent, int n);//数据的向上调整(大堆)
void AdjustUpBig(int* arr, int child);//数据的向下调整(大堆)
void AdjustDownBig(int* arr, int parent, int n);//堆排序
//排升序，建大堆
//排降序，建小堆
void HeapSortSmall(int* arr, int n);
void HeapSortBig(int* arr, int n);//直接插入排序
void InsertSort(int* arr, int n);//希尔排序
void ShellSort(int* arr, int n);//直接选择排序
void SelectSort(int* arr, int n);//快速排序
//hoare版本找基准值
int _HoareQuickSort(int* arr, int left, int right);
//挖坑法找基准值
int _PitQuickSort(int* arr, int left, int right);
//lomuto前后指针找基准值
int _LomutoQuickSort(int* arr, int left, int right);
//快速排序
void QuickSort(int* arr, int left, int right);
//非递归快速排序
//借用数据结构-栈
void StackQuickSort(int* arr, int left, int right);//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp);
void MergeSort(int* arr, int n);//计数排序
void ConunSort(int* arr, int n);

Sort.cpp

#include"Sort.h"
#include"Stack.h"//数据互换
void Swap(int* x, int* y)
{int tmp = *x;*x = *y;*y = tmp;
}//冒泡排序
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; i++){int exchange = 0;for (int j = 0; j < n - i - 1; j++){if (arr[j] < arr[j + 1]){exchange = 1;Swap(&arr[j], &arr[j + 1]);}}if (exchange == 0){break;}}
}//堆排序
//数据的向上调整(小堆)
void AdjustUpSmall(int* arr, int child)
{assert(arr);int parent = (child - 1) / 2;while (child > 0){if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//数据的向下调整(小堆)
void AdjustDownSmall(int* arr, int parent, int n)//n表示有效数据个数
{int child = parent * 2 + 1;//左孩子while (child < n)//如果左孩子在数组内{//比较左右孩子大小if (child + 1 < n && arr[child] > arr[child + 1]){child++;}if (arr[child] < arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//数据的向上调整(大堆)
void AdjustUpBig(int* arr, int child)
{assert(arr);int parent = (child - 1) / 2;while (child > 0){if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);child = parent;parent = (child - 1) / 2;}else{break;}}
}//数据的向下调整(大堆)
void AdjustDownBig(int* arr, int parent, int n)//n表示有效数据个数
{int child = parent * 2 + 1;//左孩子while (child < n)//如果左孩子在数组内{//比较左右孩子大小if (child + 1 < n && arr[child] < arr[child + 1]){child++;}if (arr[child] > arr[parent]){Swap(&arr[child], &arr[parent]);parent = child;child = parent * 2 + 1;}else{break;}}
}//堆排序
//排升序，建大堆
//排降序，建小堆void HeapSortSmall(int* arr, int n)
{建小堆，向上排序法建堆//for (int i = 0; i < n; i++)//{//	AdjustUpSmall(arr, i);//}//建小堆，向下排序法建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDownSmall(arr, i, n);}//排降序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDownSmall(arr, 0, end);end--;}
}void HeapSortBig(int* arr, int n)
{//建大堆，向下排序法建堆for (int i = (n - 1 - 1) / 2; i >= 0; i--){AdjustDownBig(arr, i, n);}//排升序int end = n - 1;while (end > 0){Swap(&arr[0], &arr[end]);AdjustDownBig(arr, 0, end);end--;}
}//直接插入排序
void InsertSort(int* arr, int n)
{for (int i = 0; i < n - 1; i++){int end = i;int tmp = arr[end + 1];while (end >= 0){//arr[end] > arr[end + 1]if (arr[end] > tmp){arr[end + 1] = arr[end];end--;}else{break;}}//while循环中end自减，所以是 end + 1 arr[end + 1] = tmp;}
}//希尔排序
void ShellSort(int* arr, int n)
{int gap = n;while (gap > 1){//有可能出现 gap == 0 的情况//要保证最后一次gap == 1;gap = gap / 3 + 1;//每个小组的直接选择插入for (int i = 0; i < n - gap; i++)//每两个数间隔gap，所以 n - gap{int end = i;//n - gap - 1;int tmp = arr[end + gap];while (end >= 0){//arr[end] > arr[end + 1]if (arr[end] > tmp){arr[end + gap] = arr[end];end -= gap;}else{break;}arr[end + gap] = tmp;}}}
}//直接选择排序
void SelectSort(int* arr, int n)
{int begin = 0;int end = n - 1;while (begin < end){int min = begin, max = begin;//找最大最小值for (int i = begin + 1; i <= end; i++){//最小值if (arr[i] < arr[min]){min = i;}//最大值if (arr[i] > arr[max]){max = i;}}//避免max和begin在同一个位置if (max == begin){max = min;}Swap(&arr[min], &arr[begin++]);Swap(&arr[max], &arr[end--]);}
}//快速排序//hoare版本找基准值
int _HoareQuickSort(int* arr, int left, int right)
{int key = left;left++;while (left <= right){//找比基准值大的值while (left <= right && arr[right] > arr[key]){right--;}//找比基准值小的值while (left <= right && arr[left] < arr[key]){left++;}//防止最后一次 left <= rightif (left <= right){Swap(&arr[left++], &arr[right--]);}}//left > right,key == 0,arr[right] < arr[key]//基准值与arr[right]交换Swap(&arr[key], &arr[right]);//返回基准值下标位置return right;
}//挖坑法找基准值
int _PitQuickSort(int* arr, int left, int right)
{int hole = left;//坑int key = arr[hole];//基准值int num = 0;while (left < right){测试死循环//printf("%d\n", ++num);//找比基准值小的值while (left < right && arr[right] >= key){right--;}arr[hole] = arr[right];//将找到的值放入坑内hole = right;//记录坑的位置//找比基准值大的值while (left < right && arr[left] < key){left++;}arr[hole] = arr[left];//将找到的值放入坑内hole = left;//记录坑的位置}arr[hole] = key;return hole;
}//lomuto前后指针找基准值
int _LomutoQuickSort(int* arr, int left, int right)
{int prev = left, pcur = left + 1;int key = left;while (pcur <= right){//寻找比基准值小的值if (arr[pcur] < arr[key] && ++prev != pcur) {Swap(&arr[pcur], &arr[prev]);}pcur++;}Swap(&arr[key], &arr[prev]);return prev;
}//快速排序
void QuickSort(int* arr, int left,int right)
{if (left >= right){return;}//找基准值int key = _PitQuickSort(arr, left, right);//左子序列QuickSort(arr, left, key - 1);//右子序列QuickSort(arr, key + 1, right);
}//非递归快速排序
//借用数据结构-栈
void StackQuickSort(int* arr, int left, int right)
{ST st;STInit(&st);StackPush(&st, right);StackPush(&st, left);while (!StackEmpty(&st)){//取左右栈顶int begin = StackTop(&st);StackPop(&st);int end = StackTop(&st);StackPop(&st);int prev = begin;int pcur = begin + 1;int key = begin;//双指针法找基准值while (pcur <= end){if (arr[pcur] < arr[key] && ++prev != pcur){Swap(&arr[prev], &arr[pcur]);}pcur++;}Swap(&arr[prev], &arr[key]);key = prev;//基准值划分左右区间：[begin,key-1],[key+1,end]if (key + 1 < end){StackPush(&st, end);StackPush(&st, key + 1);}if (key - 1 > begin){StackPush(&st, key - 1);StackPush(&st, begin);}}STDestroy(&st);
}//归并排序
void _MergeSort(int* arr, int left, int right, int* tmp)
{if (left >= right){return;}int mid = (left + right) / 2;_MergeSort(arr, left, mid, tmp);_MergeSort(arr, mid + 1, right, tmp);//合并 [left,mid] [mid+1,right]int begin1 = left, end1 = mid;int begin2 = mid + 1, end2 = right;int index = begin1;while (begin1 <= end1 && begin2 <= end2){if (arr[begin1] < arr[begin2]){tmp[index++] = arr[begin1++];}else{tmp[index++] = arr[begin2++];}}// begin1 || begin1  越界while (begin1 <= end1){tmp[index++] = arr[begin1++];}while (begin2 <= end2){tmp[index++] = arr[begin2++];}//拷贝tmpfor (int i = left; i <= right; i++){arr[i] = tmp[i];}
}void MergeSort(int* arr, int n)
{int* tmp = (int*)malloc(sizeof(int) * n);_MergeSort(arr, 0, n - 1, tmp);free(tmp);tmp = NULL;
}//计数排序
void ConunSort(int* arr, int n)
{int max = arr[0], min = arr[0];//找最大值和最小值的差值for (int i = 1; i < n; i++){if (arr[i] > max){max = arr[i];}if (arr[i] < min){min = arr[i];}}int range = max - min + 1;int* count = (int*)malloc(sizeof(int) * range);if (count == NULL){perror("malloc fail!!!");exit(1);}//初始化数组memset(count, 0, range * sizeof(int));//统计数组每个数据出现的次数for (int i = 0; i < n; i++){count[arr[i] - min]++;}//取count数据放入arr中int index = 0;for (int i = 0; i < range; i++){while (count[i]--){arr[index++] = i + min;}}
}

main.cpp

#include"Sort.h"void prarr(int* arr, int n)
{for (int i = 0; i < n; i++){printf("%d ", arr[i]);}printf("\n");
}void test01()
{srand(time(0));int numsize = 50000;int begin = 0;int end = 0;int* a1 = (int*)malloc(sizeof(int) * numsize);int* a2 = (int*)malloc(sizeof(int) * numsize);int* a3 = (int*)malloc(sizeof(int) * numsize);int* a4 = (int*)malloc(sizeof(int) * numsize);int* a5 = (int*)malloc(sizeof(int) * numsize);int* a6 = (int*)malloc(sizeof(int) * numsize);int* a7 = (int*)malloc(sizeof(int) * numsize);int* a8 = (int*)malloc(sizeof(int) * numsize);int* a9 = (int*)malloc(sizeof(int) * numsize);for (int i = 0; i < numsize; 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];a9[i] = a1[i];}//冒泡排序begin = clock();BubbleSort(a1, numsize);end = clock();printf("冒泡排序：%d\n",end-begin);//堆排序begin = clock();HeapSortSmall(a2, numsize);end = clock();printf("堆排序：%d\n", end - begin);//直接插入排序begin = clock();InsertSort(a3, numsize);end = clock();printf("直接插入排序：%d\n", end - begin);//希尔排序begin = clock();ShellSort(a4, numsize);end = clock();printf("希尔排序：%d\n", end - begin);//直接选择排序begin = clock();SelectSort(a5, numsize);end = clock();printf("直接选择排序：%d\n", end - begin);//快速排序begin = clock();QuickSort(a6, 0, numsize - 1);end = clock();printf("快速排序：%d\n", end - begin);//非递归快速排序begin = clock();StackQuickSort(a7, 0, numsize - 1);end = clock();printf("非递归快速排序：%d\n", end - begin);//归并排序begin = clock();MergeSort(a8, numsize);end = clock();printf("归并排序：%d\n", end - begin);//计数排序begin = clock();ConunSort(a9, numsize);end = clock();printf("计数排序：%d\n", end - begin);free(a1);free(a2);free(a3);free(a4);free(a5);free(a6);free(a7);free(a8);free(a9);a1 = NULL;a2 = NULL;a3 = NULL;a4 = NULL;a5 = NULL;a6 = NULL;a7 = NULL;a8 = NULL;a9 = NULL;
}int main()
{//int arr[10] = { 10,6,7,5,3,4,8,2,1,9 };//printf("排序前：");//prarr(arr,10);BubbleSort(arr, 10);HeapSortSmall(arr, 10);InsertSort(arr, 10);ShellSort(arr, 10);SelectSort(arr, 10);QuickSort(arr, 0, 9);StackQuickSort(arr, 0, 9);MergeSort(arr, 10);//ConunSort(arr, 10);//printf("排序后：");//prarr(arr, 10);//测试test01();return 0;
}