如何進行數據結構6種內部排序算法的比較

今天就跟大家聊聊有關如何進行數據結構6種內部排序算法的比較，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。

1、需求分析

（1）輸入數據的形式為：偽隨機數產生程序產生，且每次輸入數不少于100個，至少要用5組不同的輸入數據

（2）輸出的形式為：輸出關鍵字參加的比較次數和關鍵字的移動次數(關鍵字交換計為3次移動)的數據

（3）程序能達到的功能：對起泡排序，直接插入排序，簡單選擇排序，快速排序，希爾排序，堆排序這6種常用的內部排序算法進行比較，比較的指標為有關鍵字參加的比較次數和關鍵字的移動次數(關鍵字交換計為3次移動)

（4）測試數據：正確輸入為由偽隨機數產生程序產生100個隨機數，然后輸出比較結果，錯誤輸入為輸入極少量數據，此時輸出結果不能比較

（5）C語言編寫

2、概要設計

本程序設計了一個順序表結構來存儲需要排序的數據，主程序運行之后，先初始化6個順序表，然后就進入一個需要循環5次的大循環里，在循環里面有一個小循環需要執行100次產生100個隨機數給6個順序表，此時這6個順序表的數據相同且是隨機數，然后分別調用void InsertSort(SqList *L)冒泡排序，void InsertSort(SqList *L)直接插入排序，void SelectSort(SqList *L)簡單選擇排序，void QuickSort(SqList *L) 快速排序，void ShellSort(SqList *L)希爾排序，void HeapSort(SqList *L)堆排序，來對待排序列排序。其中void InsertSort(SqList *L)，void SelectSort(SqList *L)，void HeapSort(SqList *L)這幾個模塊中，當兩個數據需要交換位置時調用了void swap(SqList *L,int i,int j)模塊。void HeapSort(SqList *L) 模塊中調用了void HeapAdjust(SqList *L,int s,int m,int &a,int &b)，使得將L->r[1...i-1]重新調整為大頂堆 。void QuickSort(SqList *L) 模塊中調用了void QSort(SqList *L,int low,int high,int &k,int &l)來對對順序表L中的子序列L->r[low..high]作快速排序，void QSort(SqList *L,int low,int high,int &k,int &l)中又調用了int Partition(SqList *L,int low,int high,int &k,int &l)來將L->r[low..high]一分為二，算出樞軸值。

3、詳細設計

順序表結構里有用于int類型的存儲排序數據的數組，r[0]用作哨兵或臨時變量，以及int類型的用于記錄順序表的長度變量。

typedef struct{

int r[MAXSIZE+1];

int length;

}SqList;

4、調試分析

（1）調試過程中遇到的問題：

1、一開始產生隨機數時，對順序表的數組里都賦了值，結果出來時，第一個數會沒有排序，其它的數都正常，原因是r[0]是用作哨兵或者存放臨時變量，所以一開始賦值時，r[0]不應該賦值。

2、計算關鍵字交換的次數時，定義的變量為int l;計算結果出來之后，數字非常大。是因為對于局部變量，不賦初值的話，其實它里面存的是一個隨機的值，而并不是0，所以定義時應定義為int l = 0;

3、在計算關鍵字的比較和交換時，由于模塊之間要相互調用，所以計算的值要當做參數傳輸，但返回時不能返回兩個返回值，困擾了較久，然后用了int &k,int &l，即可以改變實參的方法就解決了問題

（2）算法的時空分析：

排序法 平均時間   最差情形      穩定度     額外空間     備注

冒泡    O(n2)            O(n2)             穩定         O(1)          n小時較好

選擇    O(n2)            O(n2)             不穩定     O(1)           n小時較好

插入    O(nlogn)         O(n2)              穩定       O(1)      大部分已排序時較好

希爾  O(n^1.5)        不詳           不穩定    O(1)       

快速    O(nlogn)        O(n2)             不穩定      O(nlogn)      n大時較好

堆      O(nlogn)     O(nlogn)       不穩定   O(1)           n大時較好

冒泡排序優化：當序列還沒比較但已經有序時，其實已經不要再繼續后面的循環判斷工作了，所以增加一個標量flag來實現這算法的改進

void BubbleSort2(SqList *L){

int i,j;

Status flag = TRUE;

for(i = 1;i<L->length && flag;i++){

flag = FALSE;

for(j = L->length;j>=i;j--){

if(L->r[j] > L->r[j+1]){

swap(L,j,j+1);

flag = TRUE;

}

}

}

}

（3）經驗與體會：開始打代碼前要理一下思想，找到最佳入口來寫代碼，模塊之間的調用也要先構思好，不然后面代碼之間過于混亂，當出現bug時，會很難找到，要充分利用調試的功能

5、用戶使用說明

本程序中要用戶輸入100個數是不太可能的。所以本程序執行之后就會自動產生隨機數。直接比較結果就會自動顯示。使用簡單，直接運行就行。

6、測試結果

由測試的數據可以看到冒泡排序和簡單排序中關鍵字的比較次數相同且不會波動，這是由于無論數據的數的變化，只要總數不變，冒泡排序和簡單排序都要執行循環中的比較語句。簡單排序中關鍵字的移動自述最少且波動幅度不大，是由于直接插入排序是將記錄從無序區直接插入到有序區，所以沒有數據之間的交換，所以移動次數較少，但是比較次數較多。堆排序中比較次數和移動次數兩者相差不大，是由于堆排序中將是頻繁將最大值與末尾比較然后交換。希爾排序和快排中關鍵字的移動次數波動較大。是由于這兩種排序進行數據之間交換位置的動作較大，因此當數據較混亂和較整齊時，移動次數的結果會相差較大。

5、附錄

#include <stdio.h>

#include <stdlib.h>

#define MAXSIZE 100

//排序用的順序表結構

typedef struct{

int r[MAXSIZE+1];//用于存儲要排序數組，r[0]用做哨兵或臨時變量

int length;

}SqList;

//交換兩個值

void swap(SqList *L,int i,int j){

int temp = L->r[i];

L->r[i] = L->r[j];

L->r[j] = temp;

}

//冒泡排序

void BubbleSort(SqList *L){

int i,j,k=0,l=0;

for (i = 1;i<L->length;i++){//外層循環，確定所有數都與其它數比較

//k++;

for(j = i+1;j<=L->length;j++){//內層循環，用一個數跟其它數比較大小

k++;

if(L->r[i] > L->r[j]){

swap(L,i,j);

l = l+3;

}

}

}

printf("冒泡排序中關鍵字的比較次數為%d:",k);

printf("\n冒泡排序中關鍵字的移動次數為%d:",l);

printf("\n");

}

//直接排序

void InsertSort(SqList *L) {

int i,j,k=0,l=0;

for(i = 2;i<=L->length;i++){

k++;

if(L->r[i] < L->r[i-1]){

L->r[0] = L->r[i];//設置哨兵

l++;

for(j = i-1;L->r[j] > L->r[0];j--){

L->r[j+1] = L->r[j];//記錄后移

l++;

k++;

}

k++;//這一步容易忽略，跳出循環的時候，是比較了一次，不符合條件才跳出的

L->r[j+1] = L->r[0];//插入到正確位置

l++;

}

}

printf("直接排序中關鍵字的比較次數為%d:",k);

printf("\n直接排序中關鍵字的移動次數為%d:",l);

printf("\n");

}

//簡單選擇排序

void SelectSort(SqList *L){

int i,j,min;

int k=0,l=0;

for(i = 1;i<L->length;i++){

//k++;

min = i;

for(j = i+1;j<=L->length;j++){

k++;

if(L->r[min] > L->r[j]){

min = j;

}

}

if(i != min){//判斷 i!min，則證明有數據比 r[min]還要小，則需交換

swap(L,i,min);

l = l+3;

}

}

printf("簡單排序中關鍵字的比較次數為:%d",k);

printf("\n簡單排序中關鍵字的移動次數為:%d",l);

printf("\n");

}

//希爾排序

void ShellSort(SqList *L) {

int i,j;

int k = 0,l = 0;

int increment = L->length;

do{

increment = increment/5+1;//增量序列

for(i = increment+1;i<=L->length;i++){

k++;

if(L->r[i] < L->r[i-increment]){// 需要將L->r[i]插入有序增量子表

L->r[0] = L->r[i];

l++;

for(j = i-increment;L->r[0]<L->r[j] && j>0;j = j-increment){

k++;

L->r[j+increment] = L->r[j];

l++;

}

k++;//這一步容易忽略，跳出循環的時候，是比較了一次，不符合條件才跳出的

L->r[j+increment] = L->r[0];

l++;

}

}

}while(increment > 1);

printf("希爾排序中關鍵字的比較次數為:%d",k);

printf("\n希爾排序中關鍵字的移動次數為:%d",l);

printf("\n");

}

//已知L->r[s..m]中記錄的關鍵字除L->r[s]之外均滿足堆的定義

//本函數調整L->r[s]的關鍵字，使L->r[s..m]成為一個大頂堆

void HeapAdjust(SqList *L,int s,int m,int &a,int &b){

int temp,j;

temp = L->r[s];

b++;

for(j = 2*s;j<=m;j = j*2){

a++;

if( L->r[j] < L->r[j+1] && j<m)

++j;//j為關鍵字中較大的記錄的下標

a++;

if(temp >= L->r[j])

break;

L->r[s] = L->r[j];

b++;

s = j;

}

L->r[s] = temp;

b++;

}

//堆排序

void HeapSort(SqList *L) {

int i ;

int k = 0,l = 0;

for(i = L->length/2;i>0;i--){//把L中的r構建成一個大頂堆

HeapAdjust(L,i,L->length,k,l);

}

for(i = L->length;i>1;i--){

swap(L,1,i);//將堆頂記錄和當前未經排序子序列的最后一個記錄交換

l = l+3;

HeapAdjust(L,1,i-1,k,l);//將L->r[1...i-1]重新調整為大頂堆

}

printf("堆排序中關鍵字的比較次數為:%d",k);

printf("\n堆排序中關鍵字的移動次數為:%d",l);

printf("\n");

}

//交換順序表L中子表的記錄，使樞軸記錄到位，并返回其所在位置

//此時在它之前（后）的記錄均不大（小）于它

int Partition(SqList *L,int low,int high,int &k,int &l){

int pivotkey;

pivotkey = L->r[low];

while(low<high){

while(L->r[high] >= pivotkey && low<high ){

k++;

high--;

}

k++;//這一步容易忽略，跳出循環的時候，是比較了一次，不符合條件才跳出的

swap(L,low,high);

l = l+3;

while(L->r[low] <= pivotkey && low<high ){

k++;

low++;

}

k++;//這一步容易忽略，跳出循環的時候，是比較了一次，不符合條件才跳出的

swap(L,low,high);

l = l+3;

}

return low;

}

//對順序表L中的子序列L->r[low..high]作快速排序

void QSort(SqList *L,int low,int high,int &k,int &l){

int pivot;//樞軸

if(low<high){

pivot = Partition(L,low,high,k,l);//將L->r[low..high]一分為二，算出樞軸值

QSort(L,low,pivot-1,k,l);//對低子表遞歸排序

QSort(L,pivot+1,high,k,l);//對高子表遞歸排序

}

}

//快速排序

void QuickSort(SqList *L) {

int k=0,l=0;

QSort(L,1,L->length,k,l);

printf("快速排序中關鍵字的比較次數為:%d",k);

printf("\n快速排序中關鍵字的移動次數為:%d",l);

printf("\n");

}

int main(){

int x,y;

SqList L,L1,L2,L3,L4,L5;

L.length = 100;

for(int i = 0;i<5;i++){

printf("第%d次待排序列為：\n",i+1);

for(x=1; x<101; x++) {

y = rand()% 100;

L.r[x] = y;

printf("%3d",y);

}

L1=L2=L3=L4=L5=L;

//fflush(stdin);

printf("\n排序后的結果\n");

BubbleSort(&L);

printf("直接排序后的結果\n");

InsertSort(&L1);

printf("簡單排序后的結果\n");

SelectSort(&L2);

printf("希爾排序后的結果\n");

ShellSort(&L3);

printf("堆排序后的結果\n");

HeapSort(&L4);

printf("快速排序后的結果\n");

QuickSort(&L5);

    for(x=1; x<101; x++) {

printf("%3d",L.r[x]);

}

printf("\n");

}

while(1){//設置一個死循環，為了不讓程序結束而關閉窗口

}

return 0;

} 

看完上述內容，你們對如何進行數據結構6種內部排序算法的比較有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。