下载文档原格式
快速排序算法c语言实验报告冒泡法和选择法排序C程序实验报告实验六：冒泡法排序物理学416班赵增月F12 2011412194日期：2013年10月31日一·实验目的 1.熟练掌握程序编写步骤；2.学习使用冒泡法和选择法排序；3.熟练掌握数组的定义和输入输出方法。
二·实验器材1.电子计算机；2.VC6.0三·实验内容与流程1.流程图（1）冒泡法(2)选择法 2.输入程序如下：（1）冒泡法#includestdio.h void main() { int a[10]; int i,j,t; printf(请输入10个数字：\n); for(i=0;i10;i++)scanf(%d,&a[i]); printf(\n); for(j=0;j9;j++)for(i=0;i9-j;i++) if(a[i]a[i+1]) { t=a[i]; a[i]=a[i+1]; a[i+1]=t; } printf(排序后如下：\n); for(i=0;i10;i++) printf(%d,a[i]); printf(\n); }（2）选择法#includestdio.h void main() { int a[10]; int i,j,t,k; printf(请输入10个数字：\n); for(i=0;i10;i++)scanf(%d,&a[i]);printf(\n); for(i=0;i9;i++) {k=i;for(j=i+1;j10;j++) if (a[k]a[j])k=j;t=a[i];a[i]=a[k];a[k]=t; }printf(排序后如下：\n); for(i=0;i10;i++)printf(%d,a[i]); printf(\n); }四．输出结果（1冒泡法）请输入10个数字：135****2468排序后如下：12345678910 （2）选择法输出结果请输入10个数字：135****6810排序后如下：12345678910五．实验反思与总结1.冒泡法和选择法是一种数组排序的方法，包含两层循环，写循环时，要注意循环变量的变化范围。
c快速排序题含解答共5道题目一：快速排序基本原理问题：简要解释快速排序的基本原理。
说明它是如何工作的。
解答：快速排序是一种基于分治思想的排序算法。
其基本原理如下：1. 分解：选择一个元素作为基准（通常选择数组的第一个元素），将数组分成两个子数组，小于基准的元素放在左边，大于基准的元素放在右边。
2. 递归：递归地对左右两个子数组进行排序。
3. 合并：已排序的子数组合并成最终的排序数组。
题目二：递归实现快速排序问题：使用递归的方式实现快速排序算法。
解答：```c#include <stdio.h>void swap(int *a, int *b) {int temp = *a;*a = *b;*b = temp;}int partition(int arr[], int low, int high) {int pivot = arr[low];int i = low + 1;int j = high;while (1) {while (i <= j && arr[i] <= pivot)i++;while (i <= j && arr[j] > pivot)j--;if (i <= j)swap(&arr[i], &arr[j]);elsebreak;}swap(&arr[low], &arr[j]);return j;}void quicksort(int arr[], int low, int high) {if (low < high) {int pivot = partition(arr, low, high);quicksort(arr, low, pivot - 1);quicksort(arr, pivot + 1, high);}}int main() {int arr[] = {64, 25, 12, 22, 11};int n = sizeof(arr) / sizeof(arr[0]);printf("Unsorted array: ");for (int i = 0; i < n; i++)printf("%d ", arr[i]);quicksort(arr, 0, n - 1);printf("\nSorted array: ");for (int i = 0; i < n; i++)printf("%d ", arr[i]);return 0;}```题目三：非递归实现快速排序问题：使用非递归的方式实现快速排序算法。
c语⾔快速排序的库函数整理这些库函数都是在平时编程中经常调⽤的快排函数View Code以下所介绍的所有排序都是从⼩到⼤排序快速排序的库函数都包含在头⽂件名为<stdlib.h>中<1>对int型数组排序int num[100];int cmp(const void *a,const void *b){return *(int *)a-*(int *)b;}int main(){......qsort(num,100,sizeof(num[0]),cmp);return0;}<2>对char型数组排序char st[100];int cmp(const void *a,const void *b){return *(char *)a-*(char *)b;}int main(){......qsort(st,100,sizeof(st[0]),cmp);return0;}<3>对double型数组排序double f[100];int cmp(const void *a,const void *b){return ((*(double *)a-*(double *)b>0)?1:-1);}int main(){......qsort(f,100,sizeof(f[0]),cmp);return0;}<4>对结构体排序struct node{double data;int flag;}f[100];int cmp(const void *a,const void *b){return (((struct node *)a)->data>((struct node *)b)->data?1:-1);}int main(){......qsort(f,100,sizeof(f[0]),cmp);return0;}<5>对结构体的⼆级排序struct node{double data;int flag;}f[100];int cmp(const void *a,const void *b){if(((struct node *)a)->data != ((struct node *)b)->data)return (((struct node *)a)->data > ((struct node *)b)->data?1:-1);elsereturn (((struct node *)a)->flag-((struct node *)b)->flag);}int main(){......qsort(f,100,sizeof(f[0]),cmp);return0;}<6>对字符串数组的排序int st[100];int cmp(const void *a,const void *b){return strcmp((char *)a,(char *)b);//根据字典序进⾏⽐较排序}int main(){......qsort(st,100,sizeof(st[0]),cmp);return0;}<7>对指针数组的排序char *s[100];//定义⼀个指针的数组int cmp(const void *a,const void *b){return (strcmp(*(char**)a,*(char**)b));//这⾥⽤char**表⽰指针的指针}int main(){......qsort(s,100,sizeof(s[0]),cmp);return0;}。
C语⾔⼋⼤排序算法C语⾔⼋⼤排序算法，附动图和详细代码解释！来源：C语⾔与程序设计、⽵⾬听闲等⼀前⾔如果说各种编程语⾔是程序员的招式，那么数据结构和算法就相当于程序员的内功。
想写出精炼、优秀的代码，不通过不断的锤炼，是很难做到的。
⼆⼋⼤排序算法排序算法作为数据结构的重要部分，系统地学习⼀下是很有必要的。
1、排序的概念排序是计算机内经常进⾏的⼀种操作，其⽬的是将⼀组“⽆序”的记录序列调整为“有序”的记录序列。
排序分为内部排序和外部排序。
若整个排序过程不需要访问外存便能完成，则称此类排序问题为内部排序。
反之，若参加排序的记录数量很⼤，整个序列的排序过程不可能在内存中完成，则称此类排序问题为外部排序。
2、排序分类⼋⼤排序算法均属于内部排序。
如果按照策略来分类，⼤致可分为：交换排序、插⼊排序、选择排序、归并排序和基数排序。
如下图所⽰：3、算法分析1.插⼊排序*直接插⼊排序*希尔排序2.选择排序*简单选择排序*堆排序3.交换排序*冒泡排序*快速排序4.归并排序5.基数排序不稳定排序：简单选择排序，快速排序，希尔排序，堆排序稳定排序：冒泡排序，直接插⼊排序，归并排序，奇数排序1、插⼊排序将第⼀个和第⼆个元素排好序，然后将第3个元素插⼊到已经排好序的元素中，依次类推（插⼊排序最好的情况就是数组已经有序了）因为插⼊排序每次只能操作⼀个元素，效率低。
元素个数N，取奇数k=N/2，将下标差值为k的数分为⼀组（⼀组元素个数看总元素个数决定），在组内构成有序序列，再取k=k/2，将下标差值为k的数分为⼀组，构成有序序列，直到k=1，然后再进⾏直接插⼊排序。
3、简单选择排序选出最⼩的数和第⼀个数交换，再在剩余的数中⼜选择最⼩的和第⼆个数交换，依次类推4、堆排序以升序排序为例，利⽤⼩根堆的性质（堆顶元素最⼩）不断输出最⼩元素，直到堆中没有元素1.构建⼩根堆2.输出堆顶元素3.将堆低元素放⼀个到堆顶，再重新构造成⼩根堆，再输出堆顶元素，以此类推5、冒泡排序改进1：如果某次冒泡不存在数据交换，则说明已经排序好了，可以直接退出排序改进2：头尾进⾏冒泡，每次把最⼤的沉底，最⼩的浮上去，两边往中间靠16、快速排序选择⼀个基准元素，⽐基准元素⼩的放基准元素的前⾯，⽐基准元素⼤的放基准元素的后⾯，这种动作叫分区，每次分区都把⼀个数列分成了两部分，每次分区都使得⼀个数字有序，然后将基准元素前⾯部分和后⾯部分继续分区，⼀直分区直到分区的区间中只有⼀个元素的时候，⼀个元素的序列肯定是有序的嘛，所以最后⼀个升序的序列就完成啦。
CC++实现快速排序算法的思路及原理解析⽬录快速排序2. 实现原理3. 动态演⽰4. 完整代码5. 结果展⽰6. 算法分析快速排序1. 算法思想快速排序的基本思想：通过⼀趟排序将待排记录分隔成独⽴的两部分，其中⼀部分记录的关键字均⽐另⼀部分的关键字⼩，则可分别对这两部分记录继续进⾏排序，以达到整个序列有序。
2. 实现原理2.1、设置两个变量 low、high，排序开始时：low=0，high=size-1。
2.2、整个数组找基准正确位置，所有元素⽐基准值⼩的摆放在基准前⾯，所有元素⽐基准值⼤的摆在基准的后⾯默认数组的第⼀个数为基准数据，赋值给key，即key=array[low]。
因为默认数组的第⼀个数为基准，所以从后⾯开始向前搜索（high–），找到第⼀个⼩于key的array[high]，就将 array[high] 赋给 array[low]，即 array[low] = array[high]。
（循环条件是 array[high] >= key；结束时 array[high] < key）此时从前⾯开始向后搜索（low++），找到第⼀个⼤于key的array[low]，就将 array[low] 赋给 array[high]，即 array[high] = array[low]。
（循环条件是 array[low] <= key；结束时 array[low] > key）循环 2-3 步骤，直到 low=high，该位置就是基准位置。
把基准数据赋给当前位置。
2.3、第⼀趟找到的基准位置，作为下⼀趟的分界点。
2.4、递归调⽤（recursive）分界点前和分界点后的⼦数组排序，重复2.2、2.3、2.4的步骤。
2.5、最终就会得到排序好的数组。
3. 动态演⽰4. 完整代码三个函数基准插⼊函数：int getStandard(int array[],int low,int high)（返回基准位置下标）递归排序函数：void quickSort(int array[],int low,int high)主函数：int main()#include <stdio.h>#include <stdlib.h>void display(int* array, int size) {for (int i = 0; i < size; i++) {printf("%d ", array[i]);}printf("\n");}int getStandard(int array[], int i, int j) {// 基准数据int key = array[i];while (i < j) {// 因为默认基准是从左边开始，所以从右边开始⽐较// 当队尾的元素⼤于等于基准数据时,就⼀直向前挪动 j 指针while (i < j && array[j] >= key) {j--;}// 当找到⽐ array[i] ⼩的时，就把后⾯的值 array[j] 赋给它if (i < j) {array[i] = array[j];}// 当队⾸元素⼩于等于基准数据时,就⼀直向后挪动 i 指针while (i < j && array[i] <= key) {i++;}// 当找到⽐ array[j] ⼤的时，就把前⾯的值 array[i] 赋给它if (i < j) {array[j] = array[i];}}// 跳出循环时 i 和 j 相等,此时的 i 或 j 就是 key 的正确索引位置// 把基准数据赋给正确位置array[i] = key;return i;}void QuickSort(int array[], int low, int high) {// 开始默认基准为 lowif (low < high) {// 分段位置下标int standard = getStandard(array, low, high);// 递归调⽤排序// 左边排序QuickSort(array, low, standard - 1);// 右边排序QuickSort(array, standard + 1, high);}}// 合并到⼀起快速排序// void QuickSort(int array[], int low, int high) {// if (low < high) {// int i = low;// int j = high;// int key = array[i];// while (i < j) {// while (i < j && array[j] >= key) {// j--;// }// if (i < j) {// array[i] = array[j];// }// while (i < j && array[i] <= key) {// i++;// }// if (i < j) {// array[j] = array[i];// }// }// array[i] = key;// QuickSort(array, low, i - 1);// QuickSort(array, i + 1, high);// }// }int main() {int array[] = {49, 38, 65, 97, 76, 13, 27, 49, 10};int size = sizeof(array) / sizeof(int);// 打印数据printf("%d \n", size);QuickSort(array, 0, size - 1);display(array, size);// int size = 20;// int array[20] = {0}; // 数组初始化// for (int i = 0; i < 10; i++) { // 数组个数// for (int j = 0; j < size; j++) { // 数组⼤⼩// array[j] = rand() % 1000; // 随机⽣成数⼤⼩ 0~999// }// printf("原来的数组：");// display(array, size);// QuickSort(array, 0, size - 1);// printf("排序后数组：");// display(array, size);// printf("\n");// }return 0;}5. 结果展⽰（递归调⽤，不好展⽰每次排序结果）6. 算法分析时间复杂度：最好： O ( n l o g 2 n ) O(n log_{2} n) O(nlog2n)最坏： O ( n 2 ) O(n^2) O(n2)平均： O ( n l o g 2 n ) O(n log_{2} n) O(nlog2n)空间复杂度： O ( n l o g 2 n ) O(n log_{2} n) O(nlog2n)稳定性：不稳定到此这篇关于C/C++实现快速排序算法的思路及原理解析的⽂章就介绍到这了,更多相关C++实现快速排序算法内容请搜索以前的⽂章或继续浏览下⾯的相关⽂章希望⼤家以后多多⽀持！。
《数据结构与算法》实验报告一、需求分析问题描述：在教科书中，各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶，或大概执行时间。
试通过随机数据比较各算法的关键字比较次数和关键字移动次数，以取得直观感受。
基本要求：（l）对以下6种常用的内部排序算法进行比较：起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。
（2）待排序表的表长不小于100000；其中的数据要用伪随机数程序产生；至少要用5组不同的输入数据作比较；比较的指标为有关键字参加的比较次数和关键字的移动次数（关键字交换计为3次移动）。
（3）最后要对结果作简单分析，包括对各组数据得出结果波动大小的解释。
数据测试：二．概要设计1.程序所需的抽象数据类型的定义：typedef int BOOL; //说明BOOL是int的别名typedef struct StudentData { int num; //存放关键字}Data; typedef struct LinkList { int Length; //数组长度Data Record[MAXSIZE]; //用数组存放所有的随机数} LinkList int RandArray[MAXSIZE]; //定义长度为MAXSIZE的随机数组void RandomNum() //随机生成函数void InitLinkList(LinkList* L) //初始化链表BOOL LT(int i, int j,int* CmpNum) //比较i和j 的大小void Display(LinkList* L) //显示输出函数void ShellSort(LinkList* L, int dlta[], int t,int* CmpNum, int* ChgNum) //希尔排序void QuickSort (LinkList* L, int* CmpNum, int* ChgNum) //快速排序void HeapSort (LinkList* L, int* CmpNum, int* ChgNum) //堆排序void BubbleSort(LinkList* L, int* CmpNum, int* ChgNum) //冒泡排序void SelSort(LinkList* L, int* CmpNum, int* ChgNum) //选择排序void Compare(LinkList* L,int* CmpNum, int* ChgNum) //比较所有排序2 .各程序模块之间的层次（调用）关系：二、详细设计typedef int BOOL; //定义标识符关键字BOOL别名为int typedef struct StudentData //记录数据类型{int num; //定义关键字类型}Data; //排序的记录数据类型定义typedef struct LinkList //记录线性表{int Length; //定义表长Data Record[MAXSIZE]; //表长记录最大值}LinkList; //排序的记录线性表类型定义int RandArray[MAXSIZE]; //定义随机数组类型及最大值/******************随机生成函数********************/void RandomNum(){int i; srand((int)time(NULL)); //用伪随机数程序产生伪随机数for(i=0; i小于MAXSIZE; i++) RandArray[i]<=(int)rand(); 返回;}/*****************初始化链表**********************/void InitLinkList(LinkList* L) //初始化链表{int i;memset(L,0,sizeof(LinkList));RandomNum();for(i=0; i小于<MAXSIZE; i++)L->Record[i].num<=RandArray[i]; L->Length<=i;}BOOL LT(int i, int j,int* CmpNum){(*CmpNum)++; 若i<j) 则返回TRUE; 否则返回FALSE;}void Display(LinkList* L){FILE* f; //定义一个文件指针f int i;若打开文件的指令不为空则//通过文件指针f打开文件为条件判断{ //是否应该打开文件输出“can't open file”;exit(0); }for (i=0; i小于L->Length; i++)fprintf(f,"%d\n",L->Record[i].num);通过文件指针f关闭文件;三、调试分析1.调试过程中遇到的问题及经验体会:在本次程序的编写和调试过程中，我曾多次修改代码，并根据调试显示的界面一次次调整代码。
c语言快排算法快速排序是一种高效的排序算法，它的思想是通过分治法将一个大问题分解成若干个小问题，然后逐步解决这些小问题，最终得到整个问题的解决方案。
它的核心是选取一个支点，将序列分成左右两个子序列，左边的序列都比支点小，右边的序列都比支点大，然后再对左右两个子序列分别进行递归排序，最后将左右两个排好序的子序列合并成一个有序序列。
在C语言中，快速排序可以通过以下代码来实现：void quick_sort(int arr[], int left, int right){if(left < right){int i = left, j = right, pivot = arr[left];while(i < j){while(i < j && arr[j] >= pivot) j--;if(i < j) arr[i++] = arr[j];while(i < j && arr[i] < pivot) i++;if(i < j) arr[j--] = arr[i];}arr[i] = pivot;quick_sort(arr, left, i - 1);quick_sort(arr, i + 1, right);}}在这段代码中，left和right分别代表数组的左右边界，arr是待排序的数组。
首先选择arr[left]作为支点，然后使用两个指针i 和j分别从左右两端扫描数组，将比支点大的数移到右边，比支点小的数移到左边，直到i和j相遇。
最后将支点放到i的位置，再对左右两个子序列分别进行递归排序即可。
快速排序的时间复杂度为O(n*logn)，它的空间复杂度为O(logn)。
由于它的快速性和不需要额外空间的特点，使得它在实际应用中得到了广泛应用。
常用的c语言排序算法主要有三种即冒泡法排序、选择法排序、插入法排序。
一、冒泡排序冒泡排序：是从第一个数开始，依次往后比较，在满足判断条件下进行交换。
代码实现（以降序排序为例）#include<stdio.h>int main(){int array[10] = { 6,9,7,8,5,3,4,0,1,2 };int temp;for (int i = 0; i < 10; i++){//循环次数for (int j = 0; j <10 - i-1; j++){if (array[j] < array[j+1]){//前面一个数比后面的数大时发生交换temp = array[j];array[j] = array[j+1];array[j + 1] = temp;}}} //打印数组for (int i = 0; i < 10; i++) printf("%2d", array[i]); return 0;}}二、选择排序以升序排序为例：就是在指定下标的数组元素往后（指定下标的元素往往是从第一个元素开始，然后依次往后），找出除指定下标元素外的值与指定元素进行对比，满足条件就进行交换。
与冒泡排序的区别可以理解为冒泡排序是相邻的两个值对比，而选择排序是遍历数组，找出数组元素与指定的数组元素进行对比。
（以升序为例）#include<stdio.h>int main(){int array[10] = { 6,9,7,8,5,3,4,0,1,2 };int temp, index;for (int i = 0; i < 9; i++) {index = i;for (int j = i; j < 10; j++){if (array[j] < array[index])index = j;}if(i != index){temp = array[i]; array[i] = array[index]; array[index] = temp; }for(int i=0;i<10:i++) printf("%2d"array[i]）return 0；}三、快速排序是通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
c语言排列组合代码C语言排列组合是编程中非常重要的一个概念，它可以帮助我们解决很多实际问题。
下面我将为你介绍一些关于C语言排列组合的基本知识，并提供一些示例代码帮助你更好地理解。
首先，我们需要了解排列和组合这两个概念的区别。
排列指的是从一组元素中选取一部分进行排列放置，而组合则是从一组元素中选取一部分进行组合放置。
换句话说，排列要考虑元素的顺序，而组合则不考虑元素的顺序。
那么，如何实现C语言中的排列组合呢？一、排列1.全排列全排列是指将给定的一组元素进行全面的排列，即将每个元素都当作一个起始元素，与其他元素进行交换得到所有可能的排列。
以下是一个示例代码：```#include <stdio.h>// 交换两个元素的值void swap(char *a, char *b) {char temp = *a;*a = *b;*b = temp;}// 输出全排列结果void permute(char *str, int start, int end) {if (start == end) {printf("%s\n", str);} else {for (int i = start; i <= end; i++) {swap((str + start), (str + i));permute(str, start + 1, end);swap((str + start), (str + i)); // 恢复原始位置 }}}int main() {char str[] = "abc";int size = strlen(str);permute(str, 0, size - 1);return 0;}```2.部分排列部分排列是指从一组元素中选取一部分进行排列。
以下是一个示例代码：```#include <stdio.h>// 输出部分排列结果void partial_permute(char *str, int start, int end, int r) {if (r == 0) {for (int i = 0; i < start; i++) {printf("%c", str[i]);}printf("\n");} else {for (int i = start; i <= end; i++) {swap((str + start), (str + i));partial_permute(str, start + 1, end, r - 1);swap((str + start), (str + i)); // 恢复原始位置}}}int main() {char str[] = "abcd";int size = strlen(str);int r = 3; // 选取3个元素进行排列partial_permute(str, 0, size - 1, r);return 0;}```二、组合组合是指从一组元素中选取一部分进行组合。
#include<stdio.h>#include<math.h>#include<stdlib.h>#include<time.h>#define M 30001random(int a[30001]){int i;for(i=1;i<30001;i++)a[i]=rand()%30001;}//随机生成30000个数函数int change1(char a[81]){int b=0,n,i;for(i=0;a[i]!=0;i++);n=i-1;for(;i>1;i--)b+=((int)pow(10,n+1-i))*(a[i-1]-48);if(a[0]=='-')b=b*(-1);elseb+=((int)pow(10,n))*(a[0]-48);return b;}//字符转化成整型insort(int a[30001]){int i,j,temp,temp1,n;int count=0;n=30001;for(i=1;i<n;i++){temp=a[i];//for(j=i-1;j>=0;j--)/* 每次循环完毕数组的0到i-1项为一个有序的序列*/{count=0;/*这里count是标记位，可以减少比较次数*/if(a[j]>temp){temp1=a[j+1];a[j+1]=a[j];a[j]=temp1;count++;}//满足条件，前移if(count==0)break;//位置恰当，退出}}}//insort插入排序函数selsort(int a[30001]){int i,j,temp;for(i=1;i<30000;i++)for(j=i+1;j<30001;j++)if(a[i]>a[j]){temp=a[j];a[j]=a[i];a[i]=temp;}}//选择排序bubsort(int a[30001]){int i,j,temp;for(i=1;i<30001;i++)for(j=30000;j>i;j--){if(a[j-1]>a[j]){temp=a[j-1];a[j-1]=a[j];a[j]=temp;}}}//冒泡排序int partition(int a[30001],int low,int high){int pr;a[0]=a[low];pr=a[low];while(low<high){while(low<high&&a[high]>=pr) --high;a[low]=a[high];while(low<high&&a[low]<=pr) ++low;a[high]=a[low];}a[low]=a[0];return low;}//partionqsort(int a[30001],int low,int high) {int pr;if(low<high){pr=partition(a,low,high);qsort(a,low,pr-1);qsort(a,pr+1,high);}}//qsortquicksort(int a[30001]){//快速排序qsort(a,1,30000);}//quicksortvoid heapadjust(int a[M],int s,int m) {//建立堆函数int rc,j;rc=a[s];for(j=2*s;j<=m;j*=2){if(j<m&&a[j]<a[j+1])++j;if(rc>=a[j])break;a[s]=a[j];s=j;}a[s]=rc;}//heapadjust建立堆函数void heapsort(int a[30001]){int i,temp;for(i=M/2;i>0;--i)heapadjust(a,i,M);//建初始大顶堆for(i=M;i>1;--i){temp=a[i];a[i]=a[1];a[1]=temp;//交换，把最后一个记录和堆顶记录交换，最值移到最后heapadjust(a,1,i-1);//建立顶堆}}//heapadjust堆排序merge(int array[],int p,int q,int r){int i,k=0,begin1=p,end1=q,begin2=q+1,end2=r,*temp;temp=(int *)malloc((r-p+1)*sizeof(int));while((begin1<=end1)&&(begin2<=end2)){if(array[begin1]<array[begin2]){temp[k] = array[begin1]; begin1++;}else{temp[k] = array[begin2]; begin2++;}k++;}while(begin1<=end1){temp[k++] = array[begin1++];}while(begin2<=end2){temp[k++] = array[begin2++];}for (i = 0; i < (r - p +1); i++)array[p+i] = temp[i];free(temp);}//mergevoid mergesort(int array[], unsigned int first, unsigned int last) {int mid = 0;if(first<last){mid = (first+last)/2;mergesort(array, first, mid);mergesort(array, mid+1,last);merge(array,first,mid,last);}}//mergesort归并排序work1(char timep[2][30]){int A,a,B,b,margin;char newmin[3],newsec[3],oldmin[3],oldsec[3];newmin[0]=timep[0][14];newmin[1]=timep[0][15];newsec[0]=timep[0][17];newsec[1]=timep[0][18];oldmin[0]=timep[1][14];oldmin[1]=timep[1][15];oldsec[0]=timep[1][17];oldsec[1]=timep[1][18];newmin[2]=0;newsec[2]=0;oldmin[2]=0;oldsec[2]=0;A=change1(newmin);a=change1(newsec);B=change1(oldmin);b=change1(oldsec);margin=(B-A)*60+b-a;return margin;}//计算时间差void mark(char timep[30]){time_t timep1;int i;time(&timep1);for(i=0;ctime(&timep1)[i]!=0;i++)timep[i]=ctime(&timep1)[i];timep[i]=0;//起始时间记录}//起始时刻记录main(){int a[30001],num,i,margin,n;float t;char timep[2][30];time_t timep2;printf("1:插入排序\n\n");printf("2:选择排序\n\n");printf("3:冒泡排序\n\n");printf("4:快速排序\n\n");printf("5:堆排序\n\n");printf("6:归并排序\n\n");loop:printf("请选择排序方法,输入序号\n");scanf("%d",&num);switch(num){case 1:mark(timep[0]);random(a);n=1;insort(a);break;//插入排序函数case 2:mark(timep[0]);random(a);n=1;selsort(a);break;//选择排序函数case 3:mark(timep[0]);;random(a);n=1;bubsort(a);break;//冒泡排序函数case 4:mark(timep[0]);n=99;for(i=0;i<n;i++){random(a);quicksort(a);}break;//快速排序函数case 5:mark(timep[0]);n=99;for(i=0;i<n;i++){random(a);heapsort(a);}break;//堆排序函数case 6:mark(timep[0]);n=9;for(i=0;i<n;i++){random(a);mergesort(a,1,30001);}break;//归并排序函数default:{printf("ERROR,重新输入");goto loop;}}time(&timep2);for(i=0;ctime(&timep2)[i]!=0;i++)timep[1][i]=ctime(&timep2)[i];timep[1][i]=0;//运行末时刻记录margin=work1(timep);//计算时间差for(i=1;i<30001;i++)printf("%d ",a[i]);printf("\n\n\n所需时间为%.3f秒",((float)margin)/n);}。
