題目：
各種內部排序演算法的時間復雜度分析結果只給出了演算法執行時間的階，或大概執行時間，試通過隨機的資料比較各演算法的關鍵字比較次數和關鍵字移動次數，以取得直觀感受，
基本要求：
（1） 從以下常用的內部排序演算法至少選取5種進行比較：直接插入排序；折半折入排序；希爾排序；起泡排序；快速排序；簡單選擇排序；堆排序；歸并排序，
（2） 待排序表的表長為20000；其中的資料要用偽亂數產生程式產生；至少要用5組不同的輸入資料作比較；比較的指標為有關鍵字參加的比較次數和關鍵字移動次數（關鍵字交換計為3次移動），
代碼：
#ifndef _HEAD_H #define _HEAD_H #include <stdio.h> #include <stdlib.h> #include <string.h> #include <time.h> #define MAX 20002 typedef int KeyType; typedef int InfoType; typedef struct SS { KeyType key; //關鍵字項 InfoType data; //其他資料項 } RecType; //排序的元素的型別 typedef struct SSS { char name[30]; //排序名稱 int com; //比較的次數 int mov; //移動的次數 }Analysis; //存盤分析效率的4資料 //交換函式 void swap(RecType &a, RecType &b) { RecType c; c = a; a = b; b = c; } int compare = 0 , move = 0; //關鍵字比較和移動的次數 Analysis Analy[5]; //五種演算法的分析資料 //直接插入排序演算法 //時間復雜度O(n^2) void InsertSort(RecType R[], int n); //折半插入排序法 //把無序區插入到有序區里，由于前面的插入排序法實作了有序，所以直接在 //有序區利用折半查找來尋找的改進演算法 void BinInsertSort(RecType R[], int n); //希爾排序演算法 void ShellSort(RecType R[], int n); //冒泡排序演算法 void BubbleSort(RecType R[], int n); /*快速排序演算法*/ int partition(RecType R[], int s, int t); //一趟劃分 //對R[s..t]的元素進行快速排序 void QuickSort(RecType R[], int s, int t); //選單 void menu(); //呼叫直接插入排序的實作函式，即選單1 void FirstFun(RecType a[], int n); //選單2 void SecondFun(RecType a[], int n); //選單3 void ThirdFun(RecType a[], int n); //選單4 void FourthFun(RecType a[], int n); //選單5 void FifthFun(RecType a[], int n); //選單6 void SixthFun(RecType a[], int n); #endif //五種常見的演算法 /////////////////////////////////////////////// //直接插入排序演算法 //時間復雜度O(n^2) void InsertSort(RecType R[], int n) { int i, j; RecType tmp; for (i = 1; i < n; i++) //for回圈內一定比較了n-1次，if判斷陳述句 { if (R[i].key < R[i - 1].key) //一旦出現了逆序的關鍵字，就進行插入 { tmp = R[i]; j = i - 1; compare++; do //往后移動一個位置，騰空間給tmp； { R[j + 1] = R[j]; move++; //移動加一 j--; compare++; //比較次數加一 } while (j >= 0 && R[j].key > tmp.key); R[j + 1] = tmp; //最后把tmp放在對應的位置 move+=2; //移動的temp } } } //////////////////////////////////////////////////// //折半插入排序法 //把無序區插入到有序區里，由于前面的插入排序法實作了有序，所以直接在 //有序區利用折半查找來尋找的改進演算法 void BinInsertSort(RecType R[], int n) { int i, j, low, high, mid; RecType tmp; for (i = 1; i < n; i++) //已經比較了n-1次 { if (R[i].key < R[i - 1].key) { tmp = R[i]; low = 0; high = i - 1; compare++; while (low <= high) { compare++; //while進入比較 mid = (low + high) / 2; if (tmp.key < R[mid].key) high = mid - 1; else low = mid + 1; } for (j = i - 1; j >= high + 1; j--) { R[j + 1] = R[j]; move++;//移動次數加一 } R[high + 1] = tmp; move += 2;//tmp交換 } } } /////////////////////////////////////////////////// //希爾排序演算法 void ShellSort(RecType R[], int n) { int i, j, d; RecType tmp; d = n / 2; while (d > 0) { for (i = d; i < n; i++) { tmp = R[i]; j = i - d; while (j >= 0 && tmp.key < R[j].key) { compare++; move++; R[j + d] = R[j]; j = j - d; } R[j + d] = tmp; move += 2;//tmp進行兩次操作 } d = d / 2; } } /////////////////////////////////////////////////// //冒泡排序演算法 void BubbleSort(RecType R[], int n) { int i, j; bool exchange; RecType tmp; for (i = 0; i < n - 1; i++) { exchange = false; for (j = n - 1; j > i; j--) if (R[j].key < R[j - 1].key) { compare ++; move += 3; tmp = R[j - 1]; R[j - 1] = R[j]; R[j] = tmp; exchange = true; } if (!exchange) return; } } ///////////////////////////////////////////////////////// /*快速排序演算法*/ int partition(RecType R[], int s, int t) //一趟劃分 { int i = s, j = t; RecType tmp = R[i]; //以R[i]為基準 while (i < j) //從兩端交替向中間掃描,直至i=j為止 { while (j > i && R[j].key >= tmp.key) { j--; //從右向左掃描,找一個小于tmp.key的R[j] compare++;//進行比較 } R[i] = R[j]; //找到這樣的R[j],放入R[i]處 move++; //移動+1 while (i < j && R[i].key <= tmp.key) { i++; //從左向右掃描,找一個大于tmp.key的R[i] compare++;//比較加一 } R[j] = R[i]; //找到這樣的R[i],放入R[j]處 move++; //移動加一 } R[i] = tmp; move+=2; //temp的交換 return i; } void QuickSort(RecType R[], int s, int t) //對R[s..t]的元素進行快速排序 { int i; if (s < t) //區間內至少存在兩個元素的情況 { i = partition(R, s, t); QuickSort(R, s, i - 1); //對左區間遞回排序 QuickSort(R, i + 1, t); //對右區間遞回排序 } } ///////////////////////////////////////////////////// void menu() { printf("***************************************************\n"); printf("\t\t1.直接插入排序法\n"); printf("\t\t2.折半插入排序法\n"); printf("\t\t3.希爾排序法\n"); printf("\t\t4.冒泡排序法\n"); printf("\t\t5.快速排序法\n"); printf("\t\t6.效率比較\n"); printf("\t\t7.退出\n"); printf("***************************************************\n"); } //呼叫直接插入排序的實作函式，即選單1 void FirstFun(RecType a[], int n) { int i; for (i = 0; i < MAX; i++) a[i].key = rand() % 100; printf("偽亂數生成的20002個亂數：\n\n\n"); for (i = 0; i < MAX; i++) printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n'); putchar(10); InsertSort(a, MAX); printf("\n\n\n利用直接插入排序后的數列如下：\n\n\n"); for (i = 0; i < MAX; i++) printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n'); printf("\n\n直接插入排序法：\n一共比較了%d次，移動了%d次\n",compare,move); Analy[0].com = compare; Analy[0].mov = move; strcpy(Analy[0].name, "直接插入排序"); } //選單2 void SecondFun(RecType a[], int n) { int i; for (i = 0; i < MAX; i++) a[i].key = rand() % 100; printf("偽亂數生成的20002個亂數：\n\n\n"); for (i = 0; i < MAX; i++) printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n'); putchar(10); compare = 0; move = 0; BinInsertSort(a, MAX); printf("\n\n\n利用折半插入排序后的數列如下：\n\n\n"); for (i = 0; i < MAX; i++) printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n'); printf("\n\n折半插入排序：\n一共比較了%d次，移動了%d次\n",compare,move); Analy[1].com = compare; Analy[1].mov = move; strcpy(Analy[1].name, "折半插入排序"); } //選單3 void ThirdFun(RecType a[], int n) { int i; for (i = 0; i < MAX; i++) a[i].key = rand() % 100; printf("偽亂數生成的20002個亂數：\n\n\n"); for (i = 0; i < MAX; i++) printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n'); putchar(10); compare = 0; move = 0; ShellSort(a,MAX); printf("\n\n\n利用希爾排序演算法后的數列如下：\n\n\n"); for (i = 0; i < MAX; i++) printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n'); printf("\n\n希爾排序演算法：\n一共比較了%d次，移動了%d次\n",compare,move); Analy[2].com = compare; Analy[2].mov = move; strcpy(Analy[2].name, "希爾排序演算法"); } //選單4 void FourthFun(RecType a[], int n) { int i; for (i = 0; i < MAX; i++) a[i].key = rand() % 100; printf("偽亂數生成的20002個亂數：\n\n\n"); for (i = 0; i < MAX; i++) printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n'); putchar(10); compare = 0; move = 0; BubbleSort(a,MAX); printf("\n\n\n利用冒泡排序法后的數列如下：\n\n\n"); for (i = 0; i < MAX; i++) printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n'); printf("\n\n冒泡排序演算法：\n一共比較了%d次，移動了%d次\n",compare,move); Analy[3].com = compare; Analy[3].mov = move; strcpy(Analy[3].name, "冒泡排序演算法"); } //選單5 void FifthFun(RecType a[], int n) { int i; for (i = 0; i < MAX; i++) a[i].key = rand() % 100; printf("偽亂數生成的20002個亂數：\n\n\n"); for (i = 0; i < MAX; i++) printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n'); putchar(10); compare = 0; move = 0; QuickSort(a,0,MAX); printf("\n\n\n利用快速排序演算法后的數列如下：\n\n\n"); for (i = 0; i < MAX; i++) printf("%3d%c", a[i].key, (i + 1) % 20 ? ' ' : '\n'); printf("\n\n快速排序演算法：\n一共比較了%d次，移動了%d次\n",compare,move); Analy[4].com = compare; Analy[4].mov = move; strcpy(Analy[4].name, "快速排序演算法"); } //選單6 void SixthFun(RecType a[], int n) { int i; printf("各種排序演算法的比較于移動次數的對比：\n\n"); //printf(" 名稱\t\t\t\t比較次數\t\t\t移動次數\n"); printf(" 名稱 比較次數 移動次數\n"); for(i = 0; i < 5; i++) printf("%-17s%-18d%d\n",Analy[i].name,Analy[i].com,Analy[i].mov); } int main () { RecType a[MAX]; int i, k; srand((unsigned)time(NULL)); menu(); printf("請選擇操作："); scanf("%d",&k); while(k!=7) { switch(k) { case 1: FirstFun(a,MAX); break; case 2: SecondFun(a,MAX); break; case 3: ThirdFun(a,MAX); break; case 4: FourthFun(a,MAX); break; case 5: FifthFun(a,MAX); break; case 6: SixthFun(a,MAX); break; default: break; } system("pause"); system("cls"); menu(); printf("請選擇操作："); scanf("%d",&k); } system("pause"); return 0; }
支持一下吧！
轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/13812.html
標籤：C
下一篇：Go語言中INI組態檔格式決議