如何進(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ù)這篇文章可以有所收獲。
創(chuàng)新互聯(lián)2013年至今，先為湖南等服務(wù)建站，湖南等地企業(yè)，進(jìn)行企業(yè)商務(wù)咨詢服務(wù)。為湖南企業(yè)網(wǎng)站制作PC+手機(jī)+微官網(wǎng)三網(wǎng)同步一站式服務(wù)解決您的所有建站問(wèn)題。
1、需求分析
（1）輸入數(shù)據(jù)的形式為：偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生，且每次輸入數(shù)不少于100個(gè)，至少要用5組不同的輸入數(shù)據(jù)
（2）輸出的形式為：輸出關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)(關(guān)鍵字交換計(jì)為3次移動(dòng))的數(shù)據(jù)
（3）程序能達(dá)到的功能：對(duì)起泡排序，直接插入排序，簡(jiǎn)單選擇排序，快速排序，希爾排序，堆排序這6種常用的內(nèi)部排序算法進(jìn)行比較，比較的指標(biāo)為有關(guān)鍵字參加的比較次數(shù)和關(guān)鍵字的移動(dòng)次數(shù)(關(guān)鍵字交換計(jì)為3次移動(dòng))
（4）測(cè)試數(shù)據(jù)：正確輸入為由偽隨機(jī)數(shù)產(chǎn)生程序產(chǎn)生100個(gè)隨機(jī)數(shù)，然后輸出比較結(jié)果，錯(cuò)誤輸入為輸入極少量數(shù)據(jù)，此時(shí)輸出結(jié)果不能比較
（5）C語(yǔ)言編寫(xiě)
2、概要設(shè)計(jì)
本程序設(shè)計(jì)了一個(gè)順序表結(jié)構(gòu)來(lái)存儲(chǔ)需要排序的數(shù)據(jù)，主程序運(yùn)行之后，先初始化6個(gè)順序表，然后就進(jìn)入一個(gè)需要循環(huán)5次的大循環(huán)里，在循環(huán)里面有一個(gè)小循環(huán)需要執(zhí)行100次產(chǎn)生100個(gè)隨機(jī)數(shù)給6個(gè)順序表，此時(shí)這6個(gè)順序表的數(shù)據(jù)相同且是隨機(jī)數(shù)，然后分別調(diào)用void InsertSort(SqList *L)冒泡排序，void InsertSort(SqList *L)直接插入排序，void SelectSort(SqList *L)簡(jiǎn)單選擇排序，void QuickSort(SqList *L) 快速排序，void ShellSort(SqList *L)希爾排序，void HeapSort(SqList *L)堆排序，來(lái)對(duì)待排序列排序。其中void InsertSort(SqList *L)，void SelectSort(SqList *L)，void HeapSort(SqList *L)這幾個(gè)模塊中，當(dāng)兩個(gè)數(shù)據(jù)需要交換位置時(shí)調(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ái)對(duì)對(duì)順序表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ái)將L->r[low..high]一分為二，算出樞軸值。
3、詳細(xì)設(shè)計(jì)
順序表結(jié)構(gòu)里有用于int類型的存儲(chǔ)排序數(shù)據(jù)的數(shù)組，r[0]用作哨兵或臨時(shí)變量，以及int類型的用于記錄順序表的長(zhǎng)度變量。
typedef struct{
int r[MAXSIZE+1];
int length;
}SqList;
4、調(diào)試分析
（1）調(diào)試過(guò)程中遇到的問(wèn)題：
1、一開(kāi)始產(chǎn)生隨機(jī)數(shù)時(shí)，對(duì)順序表的數(shù)組里都賦了值，結(jié)果出來(lái)時(shí)，第一個(gè)數(shù)會(huì)沒(méi)有排序，其它的數(shù)都正常，原因是r[0]是用作哨兵或者存放臨時(shí)變量，所以一開(kāi)始賦值時(shí)，r[0]不應(yīng)該賦值。
2、計(jì)算關(guān)鍵字交換的次數(shù)時(shí)，定義的變量為int l;計(jì)算結(jié)果出來(lái)之后，數(shù)字非常大。是因?yàn)閷?duì)于局部變量，不賦初值的話，其實(shí)它里面存的是一個(gè)隨機(jī)的值，而并不是0，所以定義時(shí)應(yīng)定義為int l = 0;
3、在計(jì)算關(guān)鍵字的比較和交換時(shí)，由于模塊之間要相互調(diào)用，所以計(jì)算的值要當(dāng)做參數(shù)傳輸，但返回時(shí)不能返回兩個(gè)返回值，困擾了較久，然后用了int &k,int &l，即可以改變實(shí)參的方法就解決了問(wèn)題
（2）算法的時(shí)空分析：
排序法 平均時(shí)間 最差情形 穩(wěn)定度 額外空間 備注
冒泡 O(n2) O(n2) 穩(wěn)定 O(1) n小時(shí)較好
選擇 O(n2) O(n2) 不穩(wěn)定 O(1) n小時(shí)較好
插入 O(nlogn) O(n2) 穩(wěn)定 O(1) 大部分已排序時(shí)較好
希爾 O(n^1.5) 不詳 不穩(wěn)定 O(1)
快速 O(nlogn) O(n2) 不穩(wěn)定 O(nlogn) n大時(shí)較好
堆 O(nlogn) O(nlogn) 不穩(wěn)定 O(1) n大時(shí)較好
冒泡排序優(yōu)化：當(dāng)序列還沒(méi)比較但已經(jīng)有序時(shí)，其實(shí)已經(jīng)不要再繼續(xù)后面的循環(huán)判斷工作了，所以增加一個(gè)標(biāo)量flag來(lái)實(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)與體會(huì)：開(kāi)始打代碼前要理一下思想，找到最佳入口來(lái)寫(xiě)代碼，模塊之間的調(diào)用也要先構(gòu)思好，不然后面代碼之間過(guò)于混亂，當(dāng)出現(xiàn)bug時(shí)，會(huì)很難找到，要充分利用調(diào)試的功能
5、用戶使用說(shuō)明
本程序中要用戶輸入100個(gè)數(shù)是不太可能的。所以本程序執(zhí)行之后就會(huì)自動(dòng)產(chǎn)生隨機(jī)數(shù)。直接比較結(jié)果就會(huì)自動(dòng)顯示。使用簡(jiǎn)單，直接運(yùn)行就行。
6、測(cè)試結(jié)果
由測(cè)試的數(shù)據(jù)可以看到冒泡排序和簡(jiǎn)單排序中關(guān)鍵字的比較次數(shù)相同且不會(huì)波動(dòng)，這是由于無(wú)論數(shù)據(jù)的數(shù)的變化，只要總數(shù)不變，冒泡排序和簡(jiǎn)單排序都要執(zhí)行循環(huán)中的比較語(yǔ)句。簡(jiǎn)單排序中關(guān)鍵字的移動(dòng)自述最少且波動(dòng)幅度不大，是由于直接插入排序是將記錄從無(wú)序區(qū)直接插入到有序區(qū)，所以沒(méi)有數(shù)據(jù)之間的交換，所以移動(dòng)次數(shù)較少，但是比較次數(shù)較多。堆排序中比較次數(shù)和移動(dòng)次數(shù)兩者相差不大，是由于堆排序中將是頻繁將最大值與末尾比較然后交換。希爾排序和快排中關(guān)鍵字的移動(dòng)次數(shù)波動(dòng)較大。是由于這兩種排序進(jìn)行數(shù)據(jù)之間交換位置的動(dòng)作較大，因此當(dāng)數(shù)據(jù)較混亂和較整齊時(shí)，移動(dòng)次數(shù)的結(jié)果會(huì)相差較大。
5、附錄
#include <stdio.h>
#include <stdlib.h>
#define MAXSIZE 100
//排序用的順序表結(jié)構(gòu)
typedef struct{
int r[MAXSIZE+1];//用于存儲(chǔ)要排序數(shù)組，r[0]用做哨兵或臨時(shí)變量
int length;
}SqList;
//交換兩個(gè)值
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)，用一個(gè)數(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)鍵字的移動(dòng)次數(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)的時(shí)候，是比較了一次，不符合條件才跳出的
L->r[j+1] = L->r[0];//插入到正確位置
l++;
}
}
printf("直接排序中關(guān)鍵字的比較次數(shù)為%d:",k);
printf("\n直接排序中關(guān)鍵字的移動(dòng)次數(shù)為%d:",l);
printf("\n");
}
//簡(jiǎ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("簡(jiǎn)單排序中關(guān)鍵字的比較次數(shù)為:%d",k);
printf("\n簡(jiǎn)單排序中關(guān)鍵字的移動(dòng)次數(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)的時(shí)候，是比較了一次，不符合條件才跳出的
L->r[j+increment] = L->r[0];
l++;
}
}
}while(increment > 1);
printf("希爾排序中關(guān)鍵字的比較次數(shù)為:%d",k);
printf("\n希爾排序中關(guān)鍵字的移動(dòng)次數(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]成為一個(gè)大頂堆
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)建成一個(gè)大頂堆
HeapAdjust(L,i,L->length,k,l);
}
for(i = L->length;i>1;i--){
swap(L,1,i);//將堆頂記錄和當(dāng)前未經(jīng)排序子序列的最后一個(gè)記錄交換
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)鍵字的移動(dòng)次數(shù)為:%d",l);
printf("\n");
}
//交換順序表L中子表的記錄，使樞軸記錄到位，并返回其所在位置
//此時(shí)在它之前（后）的記錄均不大（小）于它
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)的時(shí)候，是比較了一次，不符合條件才跳出的
swap(L,low,high);
l = l+3;
while(L->r[low] <= pivotkey && low<high ){
k++;
low++;
}
k++;//這一步容易忽略，跳出循環(huán)的時(shí)候，是比較了一次，不符合條件才跳出的
swap(L,low,high);
l = l+3;
}
return low;
}
//對(duì)順序表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);//對(duì)低子表遞歸排序
QSort(L,pivot+1,high,k,l);//對(duì)高子表遞歸排序
}
}
//快速排序
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)鍵字的移動(dòng)次數(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)單排序后的結(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è)置一個(gè)死循環(huán)，為了不讓程序結(jié)束而關(guān)閉窗口
}
return 0;
}
看完上述內(nèi)容，你們對(duì)如何進(jìn)行數(shù)據(jù)結(jié)構(gòu)6種內(nèi)部排序算法的比較有進(jìn)一步的了解嗎？如果還想了解更多知識(shí)或者相關(guān)內(nèi)容，請(qǐng)關(guān)注創(chuàng)新互聯(lián)行業(yè)資訊頻道，感謝大家的支持。
當(dāng)前文章：如何進(jìn)行數(shù)據(jù)結(jié)構(gòu)6種內(nèi)部排序算法的比較
網(wǎng)頁(yè)路徑：http://chinadenli.net/article26/jhjcjg.html
成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供動(dòng)態(tài)網(wǎng)站、自適應(yīng)網(wǎng)站、外貿(mào)網(wǎng)站建設(shè)、響應(yīng)式網(wǎng)站、外貿(mào)建站、定制開(kāi)發(fā)
聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)
- APP定制開(kāi)發(fā)需要哪些流程 2016-01-11
- 臨沂網(wǎng)站制作常德SEO網(wǎng)站優(yōu)化百度網(wǎng)站優(yōu)化 2023-01-02
- 企業(yè)網(wǎng)站制作所造成難以收錄的主因是什么 2022-10-20
- 企業(yè)網(wǎng)站制作中如何兼顧到網(wǎng)站的優(yōu)化呢 2021-03-24
- 如何確定成都網(wǎng)站制作的計(jì)劃目標(biāo)？ 2022-07-05
- 網(wǎng)站制作一般有哪些功能，看完茅塞頓開(kāi) 2022-10-17
- 成都網(wǎng)站制作公司淺析外貿(mào)網(wǎng)站的幾個(gè)注意點(diǎn) 2016-10-06
- 成都網(wǎng)站制作公司哪家好 2023-01-05
- 成都網(wǎng)站制作淺析網(wǎng)站建設(shè)到底怎樣定位才是的好呢 2016-10-17
- 網(wǎng)站生成靜態(tài)頁(yè)面是不是會(huì)更好？ 2016-03-07
- 網(wǎng)站制作中的面包屑導(dǎo)航是什么？ 2022-11-02
- 企業(yè)為什么要做手機(jī)網(wǎng)站? 2016-11-10