else
low = mid+1; }
for (int j = i - 1 ; j > high ; --j ) {
a[j+1] = a[j]; }
a[j+1] = temp ; } }
void bubble_sort(int *a) //冒泡排序 {
int temp;
for (int i = 1 ; i < len ; ++i ) {
for (int j = 0 ; j < len - i ; ++j ) {
if (a[j] > a[j+1] ) {
temp = a[j]; a[j] = a[j+1]; a[j+1] = temp ; } } } }
void quick_sort(int *a , int low , int high) //快速排序 {
if (low < high ) {
int mid;
mid = one_quick_sort(a , low , high ); quick_sort(a , low , mid - 1 ); quick_sort(a , mid+1 , high ); } }
int one_quick_sort(int *a , int low , int high) //一趟快速排序 {
int temp;
while (low < high ) {
while ( a[low ] <= a[high] && low < high ) {
--high; }
temp = a[low]; a[low] = a[high]; a[high] = temp ;
while (a[low] <= a[high] && low ++low; } temp = a[high] ; a[high] = a[low]; a[low] = temp; } return low; } void select_sort(int *a) //直接选择排序 { int n,temp; int t = len - 1 ; for (int j = len - 1 ; j >= 0 ; --j,--t ) { n = max_select_sort(a , t); if (j != n ) { temp = a[n]; a[n] = a[j]; a[j] = temp ; } } } int max_select_sort(int *a, int t) //选择最大数 { int temp = a[0]; int flag = 0 ; for (int i = 0 ; i <= t; ++i ) { if (a[i] > temp ) { temp = a[i]; flag = i ; } } return flag; } void merge_sort(int *a , int low , int high) { if (low < high) { int mid = (low + high) / 2 ; merge_sort(a , low , mid); merge_sort(a , mid + 1 , high); msort(a , low , high , mid); } } void msort(int *a , int low , int high,int mid) 数 { int i = low,j = mid+1,*b,r = 0; b = new int[high - low]; while(i <= mid && j <= high) { if (a[i] <= a[j]) { b[r] = a[i]; ++r ; ++i; } else { b[r] = a[j]; ++j; ++r; } } while (i <= mid ) { b[r] = a[i]; ++r; ++i ; } while (j <= high) { b[r] = a[j]; ++j; ++r ; } for (i = low ,j = 0 ; i <= high ; ++i ,++j ) { //归并排序 //归并排序调用函 a[i] = b[j]; } } void head_sort(int *a) //推排序 { int temp ; for (int i = len / 2 - 1 ; i>= 0 ; --i ) { head_adgust(a , i , len); } for ( i = len - 1 ; i >= 0 ; --i ) { temp = a[0]; a[0] = a[i]; a[i] = temp; head_adgust(a , 0 , i - 1 ); } } void head_adgust(int *a , int low , int high) //调整的最大堆 { int temp ; for (int i = 2 * low + 1 ; i < high ; i = i * 2 +1 ) { if (a[i] < a[i+1]) { ++i; } if (a[low] > a[i]) { break; } else { temp = a[low]; a[low] = a[i]; a[i] = temp; low = i ; } } } void shell_insert(int *a , int dk) 希尔插入函数 { int temp; for (int i = dk ; i < len ; ++i ) { if (a[i] < a[i-dk]) { temp = a[i]; for (int j = i - dk ; j >= 0 && temp < a[j] ; j = j-dk ) { a[j+dk] = a[j]; } a[j+dk] = temp ; } } } void shell_sort(int *a) //希尔排序 { int dks[3] = { 4 ,3, 1}; //定义步长 for (int i = 0 ; i < 3 ; ++i ) { shell_insert(a , dks[i]); } } void dadix_sort(int *a) //基数排序 { sort(a , a + 15 , cmp2); sort(a , a + 15 , cmp1); } int cmp1(int a,int b) //个位数比较函数 { if (a / 10 < b /10) { return 1; } return 0; } int cmp2(int a,int b) //十位数比较函数 { if (a % 10 < b % 10 ) { return 1; } return 0; } void rand_sort(int *a) //产生随机数据函数 { for (int i = 0 ; i < len ; ++i ) { a[i] = rand()0; } } void display(int *a) //打印排序好之后的函数 { for (int i = 0 ; i < len ; ++i ) { cout< cout< D）调试分析; 1、测试数据：测试数据主要通过函数rang_sort()，自动生成一系列数据 2、各个模块 分别测试，1-9分别测试了9种排序 E）课程总结： 通过数据结构大型作业，算法主要在于思想，以及思路的严谨性。实战型很强。通过练习，编程能力以及算法思想大大提高。