數(shù)據(jù)結(jié)構(gòu)的各種排序-創(chuàng)新互聯(lián)

文章目錄

• • • • 內(nèi)部排序算法性能比較
      • 1. 插入排序
      • • 1.1 直接插入排序
        • 1.2 折半插入排序
        • 1.3 希爾排序(不穩(wěn)定)
      • 2. 交換排序
      • • 2.1 冒泡排序
        • 2.2 快速排序
      • 3. 選擇排序
      • • 3.1 簡單選擇排序（不穩(wěn)定）
        • 3.2 堆排序（不穩(wěn)定）
      • 4. 歸并排序
      • 5. 基數(shù)排序

專注于為中小企業(yè)提供網(wǎng)站建設(shè)、成都網(wǎng)站制作服務(wù),電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)康平免費做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動了近千家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網(wǎng)站建設(shè)實現(xiàn)規(guī)模擴充和轉(zhuǎn)變。內(nèi)部排序算法性能比較

算法種類	最好情況	平均情況	最壞情況	空間復(fù)雜度	穩(wěn)定性
直接插入排序	O(n)	O(n^2)	O(n^2)	O(1)	穩(wěn)定
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	穩(wěn)定
簡單選擇排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不穩(wěn)定
希爾排序				O(1)	不穩(wěn)定
快速排序	O(nlog2n)	O(nlog2n)	O(n^2)	O(log2n)	不穩(wěn)定
堆排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(1)	不穩(wěn)定
2-歸路排序	O(nlog2n)	O(nlog2n)	O(nlog2n)	O(n)	穩(wěn)定
基數(shù)排序	O(d(n+r))	O(d(n+r))	O(d(n+r))	O( r )	穩(wěn)定

1. 插入排序

插入排序:每次將一個待排序的記錄按其關(guān)鍵字大小插入前面已排好的子序列，直到全部記錄插入完成。

1.1 直接插入排序

示例:對以下記錄進行排序
{49,38,65,97,76,13,27,49'}

原始記錄:49,38,65,97,76,13,27,49';
//()括號內(nèi)的記錄為已經(jīng)排序好的子序列
第一趟:(38,49),65,97,76,13,27,49';
第二趟:(38,49,65),97,76,13,27,49';
第四趟:(38,49,65,97),76,13,27,49';
第五趟:(38,49,65,,76,97),13,27,49';
第六趟:(13,38,49,65,76,97),27,49';
第七趟:(13,27,38,49,65,76,97),49';
第八趟:(13,27,38,49,49',65,76,97);

1.2 折半插入排序

折半插入:將比較和移動操作分離。先查找位置再移動元素。(只適用于有序表)

void InsertSort(ElemType A[],int n){int i,j,low,mid,high;
   for(i=2;i<=n;i++){   //折半查找
       A[0]=A[i];
       low=1;
       high=i-1;
       while(low<=high){  mid=(low+high)/2;
          if(A[mid]>A[0]){  high=mid-1;//查找左半子表
          }else{  low=mid+1;//查找右半子表
          }
          //移動元素
          for(j=i-1;j>=high+1;--j){A[j+1]=A[j];//統(tǒng)一后移元素,空出插入位置
          }
          A[high+1]=A[0];//插入操作
      }
   }
}

1.3 希爾排序(不穩(wěn)定)

希爾排序:先追求表中元素部分有序,在逐漸逼近全局有序

算法思想:
1.先將待排序記錄分割為特殊"子表",即把相隔某個"增量"的記錄組成一個子表。
2.對各個子表分別進行直接插入排序。
3.最后對全局記錄進行一次插入排序。

示例:對以下記錄進行排序
{50,26,38,80,70,90,8,30,40,20}

原始序列:50,26,38,80,70,90,8,30,40,20

d=5:50,8,30,40,20,90,26,38,80,70;//(50,90),(26,8),(38,30),(80,40),(70,20)
d=3:26,8,30,40,20,80,50,38,90,70;//將間隔為3的分割為一組
d=1:8,20,26,30,38,40,50,70,80,90;//直接插入排序

2. 交換排序

交換:是指根據(jù)序列中兩個元素關(guān)鍵字的比較結(jié)果來對換這兩個記錄在序列中的位置

2.1 冒泡排序

基本思想:從前往后(或從后往前)兩兩比較相鄰元素的值，若為逆序，則交換它們，直到序列比較完。稱之為第一趟冒泡排序。
示例:對以下記錄進行排序
{49,38,65,97,76,13,27,45}

原始序列:49,38,65,97,76,13,27,45
//每趟排序都會將一個元素放置到其最終位置上
第一趟:38,49,65,76,13,27,45,97;
第二趟:38,49,65,13,27,45,76,97;
第三趟:38,49,13,27,45,65,76,97;
第四趟:38,13,27,45,49,65,76,97;
第五趟:13,27,38,45,49,65,76,97;

2.2 快速排序

快速排序:基于分治法

算法思想:
1.在待排序表L[1...n]中任取一個元素pivot作為樞軸(基準(zhǔn),通常取首元素)
2.通過一趟排序?qū)⒋判虮韯澐譃楠毩⒌膬刹糠諰[1...k-1]和L[k+1...n]
3.使L[1...k-1]中所有元素小于pivot,L[k+1...n]中所有元素大于pivot
4.pivot放在了其最終位置L(k)上,以上過程稱為一趟快速排序.
5.重復(fù)上述過程......

示例:對以下記錄進行排序
{49,38,65,97,76,13,27,49'}

原始序列:49,38,65,97,76,13,27,49';
取pivot=49;
待補充......

3. 選擇排序 3.1 簡單選擇排序（不穩(wěn)定）

簡單選擇排序:每一趟在待排序元素中選取關(guān)鍵字最小的元素加入有序子序列
示例:對以下記錄進行排序
{49,38,65,97,76,13,27,49'}

原始序列:49,38,65,97,76,13,27,49'
//每次選取關(guān)鍵字最小的元素,與前面相應(yīng)位置進行交換
第一趟:13,38,65,97,76,49,27,49';//13與49交換位置
第二趟:13,27,65,97,76,49,38,49';//27與38交換位置
第三趟:13,27,38,97,76,49,65,49';//38與65交換位置
第四趟:13,27,38,49,76,97,65,49';//49與97交換位置
第五趟:13,27,38,49,49',97,65,76;//49'與76交換位置
第六趟:13,27,38,49,49',65,97,76;//65與97交換位置
第七趟:13,27,38,49,49',65,76,97;//76與97交換位置

3.2 堆排序（不穩(wěn)定） 4. 歸并排序 5. 基數(shù)排序

概念:不基于比較和移動元素進行排序，而基于關(guān)鍵字各位的大小進行排序。借助多關(guān)鍵字排序的思想對但邏輯關(guān)鍵字進行排序的方法

算法思想:
1.將整個關(guān)鍵字拆分為d位(組)
2.按照各個關(guān)鍵字權(quán)重遞增的次序，做d趟"分配"和"收集"
3.分配:順序掃描各個元素,根據(jù)當(dāng)前處理的關(guān)鍵字位,將元素插入相應(yīng)的隊列
4.收集:把各個隊列中結(jié)點依次出隊并鏈接

基本操作 :
(1)按“各”位進行分配;
(2)從左到右進行收集;

示例:對如下10個記錄進行排序
{520,211,438,888,007,111,985,666,233,168}
1.按個位進行分配

0	1	2	3	4	5	6	7	8	9
520	211	233			985	666	007	438
	111					996		888
								168

收集:520,211,111,233,985,666,996,007,438,888,168

2.按十位進行分配

0	1	2	3	4	5	6	7	8	9
007	211	520	233			666		985	996
	111		438			168		888

收集:007,211,111,520,233,438,666,168,985,888,996

3.按百位進行分配

0	1	2	3	4	5	6	7	8	9
007	111	211		438	520	666		888	985
	168	233							996

收集:007,111,168,211,233,438,520,666,888,985,996

你是否還在尋找穩(wěn)定的海外服務(wù)器提供商？創(chuàng)新互聯(lián)www.cdcxhl.cn海外機房具備T級流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確流量調(diào)度確保服務(wù)器高可用性，企業(yè)級服務(wù)器適合批量采購，新人活動首月15元起，快前往官網(wǎng)查看詳情吧

網(wǎng)站題目：數(shù)據(jù)結(jié)構(gòu)的各種排序-創(chuàng)新互聯(lián)
文章來源：http://bm7419.com/article34/dihjpe.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供網(wǎng)站內(nèi)鏈、電子商務(wù)、網(wǎng)站維護、App設(shè)計、網(wǎng)站營銷、定制網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請盡快告知，我們將會在第一時間刪除。文章觀點不代表本網(wǎng)站立場，如需處理請聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時需注明來源： 創(chuàng)新互聯(lián)