C语言_数据结构：随机10000个数字，进行所学的8（9）大排序

---

题目：

由计算机生成10000个整数，使用所学几种排序算法进行排序，统计排序所用的时间，分析各种排序的性能。

创建数组

//创建数组 int *CreatArray() { int *arr = (int*)malloc(sizeof(int)*MAX); srand((unsigned int)time(NULL)); for (int i = 0; i < MAX; i++) { int randNum = rand() % MAX; arr[i] = randNum; } return arr; }

1、冒泡排序

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

2、选择排序

//选择排序 void SelectSort(int arr[], int length) { //选择排序，减少了交换次数 for (int i = 0; i < length; i++) { int min = i; for (int j = i + 1; j < length; j++) { if (arr[j] < arr[i]) { min = j; } } if (min != i) { Swap(&arr[min],&arr[i]); } } }

3、插入排序

//插入排序 void InsertSort(int arr[], int length) { int j; for (int i = 1; i < length; i++) { if (arr[i] < arr[i - 1]) { int temp = arr[i]; for (j = i - 1; j >= 0 && temp < arr[j]; j -- ) { arr[j + 1] = arr[j]; } arr[j + 1] = temp; } } }

4、希尔排序

//希尔排序 void ShellSort(int arr[],int length ) { int increasement = length; int i,j,k; do{ //确定分组的增量 increasement = increasement / 3 + 1; for (i = 0; i < increasement; i++) { for (j = i + increasement; j < length; j+=increasement) { if (arr[j] < arr[j - increasement]) { int temp = arr[j]; for (k = j - increasement; k >= 0 && temp < arr[k]; k -= increasement) { arr[k + increasement] = arr[k]; } arr[k + increasement] = temp; } } } } while (increasement > 1); }

5、快速排序

//快速排序 从小到大 void QuickSort(int arr[],int start,int end) { int i = start; int j = end; //基准数 int temp = arr[start]; if (i < j) { while(i < j){ //从右向左去找比基准数小的元素 while (i < j&&arr[j]>=temp){ j--; } //填坑 if (i < j) { arr[i] = arr[j]; i++; } //从左向右 找比基准数大的数 while (i < j&&arr[i] < temp) { i++; } //填坑 if (i < j) { arr[j] = arr[i]; j--; } } //把基准数放到i=j的位置 arr[i] = temp; //对左半部分（递归）进行快速排序 QuickSort(arr, start, i - 1); //对右部分（递归）进行快速排序 QuickSort(arr, j + 1, end); } }

6、归并排序

//归并排序 void MergeSort(int arr[],int start,int end,int *temp) { if (start >= end) { return; } int mid = (start + end) / 2; //分组 //左半边 MergeSort(arr, start, mid, temp); //右半边 MergeSort(arr, mid+1, end, temp); //合并 Merge(arr, start, end, mid, temp); }

7、堆排序

//堆排序 void HeapSort(int arr[], int length) { //初始化堆 for (int i = length / 2 - 1; i >= 0; i--) { HeapAdjust(arr,i,length); } //交换堆顶元素和最后一个元素 for (int i = length - 1; i >= 0;i--) { Swap(arr, 0, i); HeapAdjust(arr, 0, i); } }

8、基数排序

//基数排序 void RadixSort(int*a,int length) { int i, max = a[0], base = 1; for (i = 0; i < length; i++) { if (a[i] > max) { max = a[i]; } } int *t = (int*)malloc(sizeof(int)*length); while (max / base > 0) { int bucket[10] = { 0 }; for (i = 0; i < length; i++) { bucket[a[i] / base % 10]++; } for (i = 1; i < 10; i++) { bucket[i] += bucket[i - 1]; } for (i =length - 1; i>= 0; i--) { t[bucket[a[i] / base % 10 ]-1] = a[i]; bucket[a[i] / base % 10]--; } for (i = 0; i < length; i++) { a[i] = t[i]; } base = base * 10; } }

源码：C/C++数据结构_随机10000个数：排序~8大排序代码集.rar

源码下载【已校准，可用直接运行】

https://download.csdn.net/download/qq_39112175/12570913