如何進(jìn)行數(shù)據(jù)結(jié)構(gòu)6種內(nèi)部排序算法的比較

今天就跟大家聊聊有關(guān)如何進(jìn)行數(shù)據(jù)結(jié)構(gòu)6種內(nèi)部排序算法的比較，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結(jié)了以下內(nèi)容，希望大家根據(jù)這篇文章可以有所收獲。

1、需求分析

（1）輸入數(shù)據(jù)的形式為：偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生，且每次輸入數(shù)不少于100個，至少要用5組不同的輸入數(shù)據(jù)

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

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

（4）測試數(shù)據(jù)：正確輸入為由偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生100個隨機(jī)數(shù)，然后輸出比較結(jié)果，錯誤輸入為輸入極少量數(shù)據(jù)，此時輸出結(jié)果不能比較

（5）C語言編寫

2、概要設(shè)計(jì)

本程序設(shè)計(jì)了一個順序表結(jié)構(gòu)來存儲需要排序的數(shù)據(jù)，主程序運(yùn)行之后，先初始化6個順序表，然后就進(jìn)入一個需要循環(huán)5次的大循環(huán)里，在循環(huán)里面有一個小循環(huán)需要執(zhí)行100次產(chǎn)生100個隨機(jī)數(shù)給6個順序表，此時這6個順序表的數(shù)據(jù)相同且是隨機(jī)數(shù)，然后分別調(diào)用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)這幾個模塊中，當(dāng)兩個數(shù)據(jù)需要交換位置時調(diào)用了void swap(SqList *L,int i,int j)模塊。void HeapSort(SqList *L) 模塊中調(diào)用了void HeapAdjust(SqList *L,int s,int m,int &a,int &b)，使得將L->r[1...i-1]重新調(diào)整為大頂堆 。void QuickSort(SqList *L) 模塊中調(diào)用了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)中又調(diào)用了int Partition(SqList *L,int low,int high,int &k,int &l)來將L->r[low..high]一分為二，算出樞軸值。

3、詳細(xì)設(shè)計(jì)

順序表結(jié)構(gòu)里有用于int類型的存儲排序數(shù)據(jù)的數(shù)組，r[0]用作哨兵或臨時變量，以及int類型的用于記錄順序表的長度變量。

typedef struct{

int r[MAXSIZE+1];

int length;

}SqList;

4、調(diào)試分析

（1）調(diào)試過程中遇到的問題：

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

2、計(jì)算關(guān)鍵字交換的次數(shù)時，定義的變量為int l;計(jì)算結(jié)果出來之后，數(shù)字非常大。是因?yàn)閷τ诰植孔兞?，不賦初值的話，其實(shí)它里面存的是一個隨機(jī)的值，而并不是0，所以定義時應(yīng)定義為int l = 0;

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

（2）算法的時空分析：

排序法 平均時間   最差情形      穩(wěn)定度     額外空間     備注

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

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

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

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

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

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

冒泡排序優(yōu)化：當(dāng)序列還沒比較但已經(jīng)有序時，其實(shí)已經(jīng)不要再繼續(xù)后面的循環(huán)判斷工作了，所以增加一個標(biāo)量flag來實(shí)現(xiàn)這算法的改進(jìn)

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）經(jīng)驗(yàn)與體會：開始打代碼前要理一下思想，找到最佳入口來寫代碼，模塊之間的調(diào)用也要先構(gòu)思好，不然后面代碼之間過于混亂，當(dāng)出現(xiàn)bug時，會很難找到，要充分利用調(diào)試的功能

5、用戶使用說明

本程序中要用戶輸入100個數(shù)是不太可能的。所以本程序執(zhí)行之后就會自動產(chǎn)生隨機(jī)數(shù)。直接比較結(jié)果就會自動顯示。使用簡單，直接運(yùn)行就行。

6、測試結(jié)果

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

5、附錄

#include <stdio.h>

#include <stdlib.h>

#define MAXSIZE 100

//排序用的順序表結(jié)構(gòu)

typedef struct{

int r[MAXSIZE+1];//用于存儲要排序數(shù)組，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++){//外層循環(huán)，確定所有數(shù)都與其它數(shù)比較

//k++;

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

k++;

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

swap(L,i,j);

l = l+3;

}

}

}

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

printf("\n冒泡排序中關(guān)鍵字的移動次數(shù)為%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];//設(shè)置哨兵

l++;

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

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

l++;

k++;

}

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

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

l++;

}

}

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

printf("\n直接排序中關(guān)鍵字的移動次數(shù)為%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，則證明有數(shù)據(jù)比 r[min]還要小，則需交換

swap(L,i,min);

l = l+3;

}

}

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

printf("\n簡單排序中關(guān)鍵字的移動次數(shù)為:%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++;//這一步容易忽略，跳出循環(huán)的時候，是比較了一次，不符合條件才跳出的

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

l++;

}

}

}while(increment > 1);

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

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

printf("\n");

}

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

//本函數(shù)調(diào)整L->r[s]的關(guān)鍵字，使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為關(guān)鍵字中較大的記錄的下標(biāo)

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構(gòu)建成一個大頂堆

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

}

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

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

l = l+3;

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

}

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

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

printf("\n");

}

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

//此時在它之前（后）的記錄均不大（?。┯谒?/p>

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++;//這一步容易忽略，跳出循環(huán)的時候，是比較了一次，不符合條件才跳出的

swap(L,low,high);

l = l+3;

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

k++;

low++;

}

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

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("快速排序中關(guān)鍵字的比較次數(shù)為:%d",k);

printf("\n快速排序中關(guān)鍵字的移動次數(shù)為:%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排序后的結(jié)果\n");

BubbleSort(&L);

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

InsertSort(&L1);

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

SelectSort(&L2);

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

ShellSort(&L3);

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

HeapSort(&L4);

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

QuickSort(&L5);

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

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

}

printf("\n");

}

while(1){//設(shè)置一個死循環(huán)，為了不讓程序結(jié)束而關(guān)閉窗口

}

return 0;

} 

看完上述內(nèi)容，你們對如何進(jìn)行數(shù)據(jù)結(jié)構(gòu)6種內(nèi)部排序算法的比較有進(jìn)一步的了解嗎？如果還想了解更多知識或者相關(guān)內(nèi)容，請關(guān)注億速云行業(yè)資訊頻道，感謝大家的支持。