常用C語言排序算法解析

1、常用 C 語言排序算法解析摘 要：排序是計算機科學中最重要的研究問題之一，也是學習C 語言程序設計過程中重點研究問題之一。 主要介紹了順序比較法、 選擇 排序法、冒泡排序法、改進的冒泡排序法和直接插入排序法，并從排 序算法的思想、 模擬排序執(zhí)行過程、 實現(xiàn)排序的算法代碼及算法性能 分析 4 個方面進行了詳細的解析，可以幫助 C 語言初學者輕松理解 幾種常用的排序算法。關鍵詞： C 語言；排序；算法思想；數組 在數據處理中，數據排序是相當重要的， 它可以使數據更有條理， 方便數據的處理。 排序是程序設計的常見問題， 解決排序問題也有多 種算法，常用的算法有順序比較排序法、選擇排序法、冒泡排序法、

2、 直接插入排序法、快速排序和希爾排序法等排序算法。在學習 C 語 言程序設計過程中排序算法也是重點研究問題之一，本文主要用 C 語言來描述幾種常見的排序算法， 以及分析實現(xiàn)算法的基本思路、 模 擬相應算法實現(xiàn)排序的過程及算法性能分析。 文中所涉及的排序均為 升序排序。順序比較排序法算法思想假設數組有 n 個元素，從第一個元素開始為第一趟， 第一個元素 和第二個元素開始到第n個元素按順序作比較，如果第一個元素大于 某個元素則第一個元素和該元素進行交換，第一個元素和其后的 n1 個元素一一進行兩兩比較結束后將是所有元素中的最小值。 接下來第 二趟從第二個元素開始逐一和其后的 n2 個元素兩兩比較，

3、在進行 n2 次比較后第二個元素將是剩下 n1 個元素中的最小值。依次類推一直 到第n1趟最后兩個元素進行比較并得到第 n1個元素是剩下的兩個元 素中的較小值。模擬排序執(zhí)行過程假設一個整型數組有 5個元素，分別為 23、12、5、16、10，排 序執(zhí)行過程如下所示：第一趟： 23 12 5 16 10 （第一趟比較前元素）第一次： 122351610（由于 2312 兩元素交換）第二次： 523121610（由于 125 兩元素交換）第三次： 523121610（由于 516 兩元素不交換）第四次： 523121610（由于 512 兩元素交換）第二次： 512231610（由于 1210 兩

4、元素交換）第三趟： 510231612（第三趟比較前元素）第一次： 510162312（由于 2316 兩元素交換）第二次： 510122316（由于 1612 兩元素交換）第四趟： 510122316（第四趟比較前元素）第一次： 510121623（由于 2316 兩元素交換）實現(xiàn)順序比較排序法核心代碼 for(i=0；i4；i+) /外循環(huán)控制排序趟數， n 個數排 n1 趟 for( j=i+1 ；jaj ) /如果當前趟的第一個元素大于當前元素，則進行 交換t=ai ；ai=aj ；aj=t ； 算法性能分析有 n 個元素參加排序要進行 n1 趟比較，第 i 趟要進行 ni 次兩兩 比

5、較。時間復雜度為 0 (n2)。順序比較排序算法穩(wěn)定，比較次數已 知，但是該算法速度慢。冒泡排序法算法思想假設數組有 n 個元素，第一趟從第一個元素開始依次比較兩個相 鄰元素的值，如果前一個元素的值大于后一個元素的值則兩個相鄰元 素進行交換，第一趟比較n1次，經過一趟排序n個元素中的最大值 存放到最后一個數組元素中。第二趟從第一個元素開始到第 n1 個元 素相鄰兩個元素作比較， 如果前一個數大于后一個數則兩個相鄰的元 素進行交換， 經過 n2 次比較，這一趟中最大值放在第 n1 個數組元素 的位置。依次類推一直到第 n1 趟第一個元素和第二個元素兩個元素進行比較， 兩個元素中的較大值放在第二個

6、數組元素的位置， 較小值 放在第一個數組元素的位置。模擬排序執(zhí)行過程假設一個整型數組有 5 個元素，分別為 23、12、5、16、10，用5 12 10 16 23變量 k 保存最小值的下標，排序執(zhí)行過程如下所示：第一趟：23 12 5 16 10（第一趟比較前元素）/ * . -r r / c|二、 4*/r. AA l=u=（、第一次：12 23 5 16 10（由于 2312 兩元素交換位置）第二次：12 5 23 16 10（由于 235 兩元素交換位置）第三次：12 5 16 23 10（由于 2316 兩元素交換位置）第四次：12 5 16 10 23（由于 2310 兩元素交換位

7、置）第二趟：12 5 16 10 23（第二趟比較前元素）第一次：5 12 16 10 23（由于 125 兩元素交換位置）第二次：5 12 16 10 23（由于 1210 兩元素交換位置） 第第一次：尺氏-、5 12 10 16 23L Jk C Jk / / /X（由于 510 兩元素交換位置）第四趟：5 10 12 16 23（第四趟比較前元素）第一次：5 10 12 16 23（由于 510 兩元素不交換位置）第三趟比較前元素）實現(xiàn)冒泡排序法核心代碼for（i=0；i4；i+） /外循環(huán)控制排序趟數， n 個數排 n1 趟 for（j=0；jaj+1 ) /相鄰元素比較，前者大于后者

8、則交換t=aj ；aj=aj+1 ；aj+1=t ； 算法性能分析有 n 個元素參加排序要進行 n1 趟比較，第 i 趟要進行 ni 次兩兩 比較。時間復雜度為 O (n2)。冒泡排序算法穩(wěn)定，比較次數已知， 但是該算法速度慢， 每次只能比較和移動相鄰兩個數據元素， 移動數 據元素的次數多。改進的冒泡排序法算法思想冒泡排序法存在的不足之處是在排序過程中， 雖然數據序列已經 按要求排序完成， 但程序無法判斷是否完成排序， 程序仍然要進行下 一趟的排序， 這樣勢必浪費了程序執(zhí)行的時間， 降低了程序的執(zhí)行效 率。為了解決這一不足，在程序中可以設置一個標志變量flag，每一趟排序開始前設置 flag

9、值為 1，表示待排序的數據序列是無序的。如 果在程序的執(zhí)行過程中發(fā)生數據交換操作，則修改 flag 值為 0。當前 趟排序結束后檢查 flag 標志，若 flag 的值為 1，表示在當前趟排序過 程中沒有進行過交換數據， 則結束排序過程， 否則繼續(xù)進行下一趟排 序。實現(xiàn)改進冒泡排序法核心代碼for（i=0；i4；i+） /外循環(huán)控制排序趟數， n 個數排 n1 趟flag=1 ； / 設置標志變量 flag 的值為 1for（j=0；jaj+1 ） /相鄰元素比較，前者大于后者則交換t=aj ；aj=aj+1 ；aj+1=t ；flag=0； /發(fā)生數據交換，修改標志 flag 的值為 0if

10、 （flag=1） /本趟排序中未發(fā)生數據交換，則終止循環(huán)，即排 序完成break；算法性能分析若數據序列的初始狀態(tài)為“正序” ，則冒泡排序過程只需進行一 趟排序，在排序過程中只需進行 n1 次比較，且不移動數據元素。若 數據序列的初始狀態(tài)為“逆序” ，則需進行 n（ n1） /2 次比較和數據 元素交換，而完成兩個數據元素交換需移動操作 3 次，故移動次數達 到最大 3n（n1） /2。改進的冒泡排序算法的時間復雜度為 O（n2）， 改進的冒泡排序算法是穩(wěn)定的排序算法。選擇排序法4.1 算法思想假設數組有 n 個元素，第一趟從第一個元素開始， 第一個元素和 第二個元素開始到第 n 個元素按順

11、序作比較， 按排序要求找到最小元 素的位置， 然后用該位置和第一個元素的下標進行比較， 如果不相等 則兩元素進行交換， 這樣第一個元素將是 n 個元素中的最小值。 接下 來第二趟從第二個元素開始逐一和其后的 n2 個元素兩兩比較，在進 行 n2 次比較后找到剩下 n1 個元素中的最小值的位置， 然后用該位置 和第一個元素的下標進行比較， 如果不相等則兩元素進行交換， 第二 個元素將是后 n1 個元素中的最小值。 依次類推一直到第 n1 趟最后兩 個元素進行比較并得到兩個元素中的較小值的位置。模擬排序執(zhí)行過程假設一個整型數組有 5 個元素，分別為 23、12、5、16、10，用 變量 k 保存最

12、小值的下標，排序執(zhí)行過程如下所示：第一趟：23 12 5 16 10 （第一趟比較前元素）第一次：k=1（由于2312)第二次：k=2（由于125)第三次：k=2（由于516)第四次：k=2（由于510)第一趟比較后，由于0! =2,則a0與a2交換第二趟：5 12 23 16 10 （第二趟比較前元素）第一次：k=1（由于1223)第二次：k=1（由于1210）第二趟比較后，由于1! =4,則a1與a4交換。第三趟： 5 10 23 16 12第一次： k=3 （由于 2316）第二次： k=4 （由于 1612）第三趟比較后，由于2! =4,則a2與a4交換。第四趟： 5 10 12 16

13、 23第一次： k=4 （由于 1623）第四趟比較后，由于3! =4,則a3與a4交換。10 12 16 23實現(xiàn)選擇排序法核心代碼for（i=0；i4； i+） /外循環(huán)控制排序趟數, n 個數排 n1 趟 k=i ； /假設當前趟的第一個數為最小值,下標記在k 中for（j=i+1 ；jaj ） /若其后有比最小值更小的,則將其下標記在k 中k=j；if（k! =i） /若 k 和 i 值不相等,說明在其后找到比其更小的數 / 交換最小值和當前趟序列的第一個數t=ai；ai=ak ；ak=t算法性能分析有 n 個元素參加排序要進行 n1 趟比較，第 i 趟要進行 ni 次兩兩 比較，每趟

14、最多進行一次數據交換，其余元素的相對位置不變。時間 復雜度為0 （n2）。選擇排序算法穩(wěn)定，比較次數與冒泡排序一樣， 數據移動次數比冒泡排序少，算法速度還是慢。5 直接插入排序法算法思想將序列分為有序序列和無序序列， 依次從無序序列中取出元素值 插入到有序序列的合適位置。 初始是有序序列中只有第一個數， 其余 n1個數組成無序序列，則n個數需進行n1次插入。初始是有序序列 中只有第一個數， 其余 n1 個數組成無序序列， 則 n 個數需進進 n1 次 插入。尋找在有序序列中插入位置可以從有序序列的最后一個數往前 找，在未找到插入點之前可以同時向后移動元素， 為插入元素準備空 間。假設數組有 n

15、 個元素，第一趟首先對前兩個元素進行比較， 按排 序要求排列好，第二趟將第 3 個元素與前兩個已排好序的元素做比 較，按排序要求找到其相應的位置，將第 3 個元素插入到該位置上。 以此類推，直到所有的元素排好序為止。模擬排序執(zhí)行過程待排序列： 23 12 5 16 10第一趟： 12 23 5 16 10 （23 插入 12 之后， 23 后移）第二趟： 5 12 23 16 10 （5插入 12之前， 12、23依次后移）第三趟： 5 12 16 23 10 （16 插入 23 之前， 23 后移）第四趟： 5 10 12 16 23 （10插入 12之前，12、16、23 依次后 移）實現(xiàn)直接插入排序法核心代碼for（i=1；i=0&taj+1=aj ；/當前元素后移一個位置j；aj+1=t； /找到插入位置后將待插入數插入該位置，注意下標值j 加 1 為插入位置算法性能分析有n個元素參加排序要進行n1趟比較。時間復雜度為O （n2） 直接插入排序算法穩(wěn)定， 執(zhí)行速度快， 但是該算法的數據比較次數不 確定，比較次數越多，插入點后的數據移動次數越多，特