数据结构实验报告–排序算法选择

排序算法选择
一、目的与要求

1. 掌握树及图型结构的逻辑特点及存储实现；
2. 根据选题，按规范化流程完成课程设计报告：
   ⑴．提供需求分析。（15分）
   ⑵．列出概要设计。（包括：抽象数据类型的描述；程序结构图或功能模块图）（20分）
   ⑶．给出详细设计。（包括：①存储结构的描述；②算法的详细设计，对复杂算法，最好画出其N-S流程图；③函数的调用关系图）（30分）
   ⑷．进行调试分析（注：调试时遇到的问题及解决方法，程序的输出结果及对结果的分析）。（15分）
   ⑸. 整理设计总结。（设计心得体会，以及其他总结信息等）（10分）
   ⑹．附有程序清单（注：代码可具有适当注释，用来说明程序的功能、结构）。（10分）
   二、设计步骤
   1.提供需求分析。
   由用户选择对该组数据进行排序的方法：直接插入排序、冒泡排序、快速排序、简单选择排序。并可以查看每趟排序的结果。
   需要不同的排序方法函数
   2.列出概要设计
   抽象数据类型的描述 无
   程序结构图或功能模块图
   

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

 srand((unsigned)time(NULL)); int a[10]; for (int i = 0; i < 10; i++) a[i] = rand() % 100;//生成随机数组 

算法的详细设计

void InsertSort(int* a, int n)//直接插入 { assert(a); int i, j; for (i = 1; i < n; i++) { if (a[i] < a[i - 1]) { int temp = a[i]; for (j = i - 1; j >= 0 && a[j] > temp; j--) { a[j + 1] = a[j]; } a[j + 1] = temp; } printf("第%02d趟：", i); PrintArray(a, n); } } void shellInsert(int array[], int n)//Hibbard增量 希尔 { int t = (int)(log(n + 1) / log(2));//t为排序趟数，排序趟数应为log2(n+1)的整数部分 int i, dk; for (i = 1; i <= t; i++) { dk = (int)(pow(2, t - i + 1) - 1);//计算Hibbard增量 //根据当前增量进行插入排序 int k, j, temp; for (k = dk; k < n; k++)//分别向每组的有序区域插入 { temp = array[k]; for (j = k - dk; (j >= k % dk) && array[j] > temp; j -= dk)//比较与记录后移同时进行 array[j + dk] = array[j]; if (j != k - dk) array[j + dk] = temp;//插入 } } } void ShellSort(int* a, int n)//希尔插入 { assert(a); int gap = n; int i, j, k = 1; while (gap /= 2) { for (i = gap; i < n; i++) { int temp = a[i]; for (j = i - gap; j >= 0 && a[j] > temp; j -= gap) { a[j + gap] = a[j]; } a[j + gap] = temp; } printf("第%02d趟：", k++); PrintArray(a, n); } } void BubbleSort(int* a, int n)//冒泡排序 { assert(a); int i, j = n, k = 1; int flag = 1; while (flag) { flag = 0; for (i = 1; i < j; i++) { if (a[i] < a[i - 1]) { swap(&a[i], &a[i - 1]); flag = 1; } } j--; if (flag) { printf("第%02d趟：", k++); PrintArray(a, n); } } } void SelectionSort(int* a, int n)//直接选择 { assert(a); int min, i, j; for (i = 0; i < n; i++) { min = i; for (j = i; j < n; j++) { if (a[j] < a[min]) min = j; } swap(&a[i], &a[min]); printf("第%02d趟：", i+1); PrintArray(a, n); } } void QuickSort(int* a, int left, int right, int n)//快速排序 { assert(a); if (left < right) { static int k = 1; int i = left, j = right, x = a[left]; while (i < j) { while (i < j && a[j] >= x) // 从右向左找第一个小于x的数 j--; if (i < j) a[i++] = a[j]; while (i < j && a[i] < x) // 从左向右找第一个大于等于x的数 i++; if (i < j) a[j--] = a[i]; } a[i] = x; printf("第%02d趟：", k++); PrintArray(a, n); QuickSort(a, left, i - 1, n); QuickSort(a, i + 1, right, n);// 递归调用 } } void MergeSort(int*a, int left, int right, int* temp)//归并排序 { if (left >= right) return; int mid = (left + right) / 2;//left + ((right - left) >> 1); int begin1, begin2, end1, end2; int i = 0; MergeSort(a, left, mid, temp); MergeSort(a, mid + 1, right, temp); begin1 = left; end1 = mid; begin2 = mid + 1; end2 = right; i = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] > a[begin2]) { temp[i++] = a[begin2++]; } else { temp[i++] = a[begin1++]; } } while (begin1 <= end1) { temp[i++] = a[begin1++]; } while (begin2 <= end2) { temp[i++] = a[begin2++]; } //memcpy(a + left, temp + left, end1-left); for (i--; i >= left; i--) { a[i] = temp[i]; } } 

#include 
  
    #include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
       
         void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } void PrintArray(int* a, int n) { int i = 0; for (; i < n - 1; ++i) { printf("%d ", a[i]); } printf("%d\n", a[i]); } //自小到大 void InsertSort(int* a, int n)//直接插入 { assert(a); int i, j; for (i = 1; i < n; i++) { if (a[i] < a[i - 1]) { int temp = a[i]; for (j = i - 1; j >= 0 && a[j] > temp; j--) { a[j + 1] = a[j]; } a[j + 1] = temp; } printf("第%02d趟：", i); PrintArray(a, n); } } void shellInsert(int array[], int n)//Hibbard增量 希尔 { int t = (int)(log(n + 1) / log(2));//t为排序趟数，排序趟数应为log2(n+1)的整数部分 int i, dk; for (i = 1; i <= t; i++) { dk = (int)(pow(2, t - i + 1) - 1);//计算Hibbard增量 //根据当前增量进行插入排序 int k, j, temp; for (k = dk; k < n; k++)//分别向每组的有序区域插入 { temp = array[k]; for (j = k - dk; (j >= k % dk) && array[j] > temp; j -= dk)//比较与记录后移同时进行 array[j + dk] = array[j]; if (j != k - dk) array[j + dk] = temp;//插入 } } } void ShellSort(int* a, int n)//希尔插入 { assert(a); int gap = n; int i, j, k = 1; while (gap /= 2) { for (i = gap; i < n; i++) { int temp = a[i]; for (j = i - gap; j >= 0 && a[j] > temp; j -= gap) { a[j + gap] = a[j]; } a[j + gap] = temp; } printf("第%02d趟：", k++); PrintArray(a, n); } } void BubbleSort(int* a, int n)//冒泡排序 { assert(a); int i, j = n, k = 1; int flag = 1; while (flag) { flag = 0; for (i = 1; i < j; i++) { if (a[i] < a[i - 1]) { swap(&a[i], &a[i - 1]); flag = 1; } } j--; if (flag) { printf("第%02d趟：", k++); PrintArray(a, n); } } } void SelectionSort(int* a, int n)//直接选择 { assert(a); int min, i, j; for (i = 0; i < n; i++) { min = i; for (j = i; j < n; j++) { if (a[j] < a[min]) min = j; } swap(&a[i], &a[min]); printf("第%02d趟：", i+1); PrintArray(a, n); } } void QuickSort(int* a, int left, int right, int n)//快速排序 { assert(a); if (left < right) { static int k = 1; int i = left, j = right, x = a[left]; while (i < j) { while (i < j && a[j] >= x) // 从右向左找第一个小于x的数 j--; if (i < j) a[i++] = a[j]; while (i < j && a[i] < x) // 从左向右找第一个大于等于x的数 i++; if (i < j) a[j--] = a[i]; } a[i] = x; printf("第%02d趟：", k++); PrintArray(a, n); QuickSort(a, left, i - 1, n); QuickSort(a, i + 1, right, n);// 递归调用 } } void MergeSort(int*a, int left, int right, int* temp)//归并排序 { if (left >= right) return; int mid = (left + right) / 2;//left + ((right - left) >> 1); int begin1, begin2, end1, end2; int i = 0; MergeSort(a, left, mid, temp); MergeSort(a, mid + 1, right, temp); begin1 = left; end1 = mid; begin2 = mid + 1; end2 = right; i = left; while (begin1 <= end1 && begin2 <= end2) { if (a[begin1] > a[begin2]) { temp[i++] = a[begin2++]; } else { temp[i++] = a[begin1++]; } } while (begin1 <= end1) { temp[i++] = a[begin1++]; } while (begin2 <= end2) { temp[i++] = a[begin2++]; } //memcpy(a + left, temp + left, end1-left); for (i--; i >= left; i--) { a[i] = temp[i]; } } void table() { printf("请选择对该组数据进行排序的方法:\n"); printf("1.直接插入排序\n"); printf("2.希尔排序\n"); printf("3.冒泡排序\n"); printf("4.快速排序排序\n"); printf("5.简单选择排序\n"); printf("6.归并排序\n"); printf("0.退出\n"); } int main() { //int a[10] = { 9,4,3,2,5,6,1,7,0,8 }; srand((unsigned)time(NULL)); int a[10]; for (int i = 0; i < 10; i++) a[i] = rand() % 100;//生成随机数组 int n = sizeof(a) / sizeof(a[0]); int* temp = (int*)malloc(sizeof(int)*n); int x = 0; printf("排序前数组："); PrintArray(a, n); table(); scanf("%d", &x); printf("第00趟："); PrintArray(a, n); switch (x) { case 1: InsertSort(a, n);//直接插入 break; case 2: //shellInsert(a, n);//Hibbard增量 希尔 ShellSort(a, n);//希尔插入 break; case 3: BubbleSort(a, n);//冒泡排序 break; case 4: QuickSort(a, 0, n - 1, n);//快速排序 break; case 5: SelectionSort(a, n);//直接选择 break; case 6: MergeSort(a, 0, n-1, temp);//归并排序 break; case 0: break; } printf("排序后数组："); PrintArray(a, n); system("pause"); return 0; }