1.整体思路:
(1)首先要实现选择排序、冒泡排序、归并排序、快速排序、插入排序这五种排序的功能。
//arr是传入的数组,len是数组长度
//由于归并排序、快速排序使用递归算法,因此不能再排序函数中计算时间。
void select_sort(int arr[], int len);
void maopao_sort(int arr[], int len);
void merge_sort(int arr[], unsigned int first, unsigned int last);
void quick_sort(long int arr[], int begin, int end);
void charu_sort(long int arr[], int len);
(2)其次实现五种排序方法计算时间的函数。
在计算时间的函数中,用while循环20个样本,每个数组内容随机生成,每生成一次,记录当前时间(begintime)并调用相应排序函数,再次记录时间(endtime),算出排序所用的时间(endtime - begintime)。
void select_time(int len);
void maopao_time(int len);
void merge_time(int len);
void quick_time(int len);
void charu_time(int len);
(3)main函数中switch结构来选择所要用的排序算法,len长度的初始值为10,用while循环来增加len长度,将len值传入所需的函数中调用来计算输出不同数组长度的时间。
2.算法分析
(1)选择排序;
核心思想:选出一个最值将其与第一个数进行交换,len个数是len-1趟;
(2)冒泡排序;
核心思想:每趟比价中进行len-1次的两两比较,第j次比较中进行len-j次的比较,每趟结束后,将最值沉底;
(3)合并排序;
核心思想:将待排序序列分为两部分,依次对分得的两个部分再次使用归并排序,之后再对其进行合并;
(4)快速排序;
核心思想:数组中取出第一个数(默认)作为基准数。将比这个数大的数全放到它的右边,小于或等于它的数全放到它的左边。 再对左右区间重复上述步骤,直到各区间只有一个数。
(5)插入排序;
核心思想:将数组的第一个数记为有序序列,其后len-1个数组成无序列,将无序序列中的数依次插入有序序列。
3.算法实现