基于C語言排序的算法改進與應用

摘 要：介紹了程序語言中排序的原理及應用，闡述了基于C語言的三種主要排序方法，提出了每種排序方法的改進，計算出改進后算法的時間復雜度，編寫了每種排序方法程序設計的主要語句，通過實例應用，對每種排序方法的算法改進前后進行對比，證明了改進后算法的優越性。

關鍵詞：C語言；排序；改進；應用

中圖分類號：TP312 文獻標識碼：A

1 引言

我們日常生活中經常會碰到一些需要按順序排列的情況，諸如大小、高矮等，這些一般都是排列對象數量較小、憑人力在有限的時間內能夠完成的任務。本文討論的排序是面向計算機程序處理的，是計算機程序設計中經常需要進行的一類操作，可以定義為：將一組雜亂無序的記錄或數據元素通過一定的方法重新排列為按某個關鍵字的有序序列[1]。

在計算機程序設計中所使用的排序按所訪問的存儲器不同可以分為內部排序和外部排序；按相同關鍵字處理方法的不同可以分為穩定排序和不穩定排序；按計算機需要進行運算的時間復雜度和空間復雜度的大小，可以分為好、平均、差等類別，其時間復雜度和空間復雜度越小代表排序算法占用計算機資源越少，該排序方法就越好[2]。

基于C語言的排序一般有七種：選擇排序，插入排序，起泡排序，快速排序，堆排序，歸并排序，基數排序，其中最主要的是選擇法、插入法、起泡法三種，本文主要就以上三種方法進行討論。

2 三種排序及其改進方法簡述

2.1 選擇排序

基本方法：在待排序數據元素中持續選擇最大（最小）的元素放在新序列的第一位、第二位……，直到所有數據全部選擇完畢。用語言描述排序過程為：第一次從原序列中選擇最大的數，放在第一位，第二次從剩下的序列中選擇最大的數放在第二位，以此類推，最后將最小的數放在最后一位，從而完成排序[3]。

這種排序存在一個問題：沒有考慮原序列的初始排序情況，即使原來的序列元素已經按從大到小排列，程序也必須執行次比較，時間復雜度為，如果原序列元素龐大，就會占用許多系統資源，造成不必要的浪費。

改進方法：在待排列序列中將數據元素兩兩比對，大者上升，上升的數據元素再次兩兩比對，大者上升，直到結束。排序過程為：在一棵二叉樹上，從底層開始，將數據元素兩兩比較，選擇較大的一個上升，再次將第二層的數據元素進行兩兩比較，選擇較大的一個上升，直到選出最大的一個，放在二叉樹頂層，然后將這個最大數所在結點全部清空，再從最底層進行兩兩比較，依次循環，選出最小的一個，完成排序過程，改進的選擇排序又叫樹形選擇排序或者錦標賽排列。

這種排序方法每選擇一個較大元素需要進行比較，其時間復雜度為，相對原來的基本方法，可以節約系統資源。

本算法的主要語句：

2.2 插入排序

基本方法：將待排序的數據元素插入到已經排序的數據序列中，得到一個新的序列，直到所有待排序的元素全部插入完畢。遞增排序過程為：首先將待排序序列的第一個元素看作有序序列，將第二個元素拿來與之比較，比其大則插在其后面，反之插在前面；其次再將得到的新序列看作有序序列，將第三個元素拿來從前向后比較，插到比自身大的元素之前，依次插入，直到最后一次元素插入完畢，完成排序過程[4]。

直接插入排序方法每插入一個元素都要從新序列的首部開始，其時間復雜度為，隨著待排序元素的增加，其占用的時間和空間就越多，增加系統負擔。

改進方法：將待排序的元素插入到已排序的序列中，不是從頭開始比較，而是從中間開始比較，確定應該插入在前一半還是后一半中，再從這一半的中間比較，確定更小的一半，最終找到合適的位置插入。

本算法的主要語句：

改進的插入排序又叫折半排序，其空間占用不變，但在時間上減少了元素相互比較的次數，但沒有減少元素的移動次數，其時間復雜度仍為。

2.3 起泡排序

基本方法：起泡排序的核心思想是“比較+交換”，兩兩比較，逆序交換，直到全部比較并交換完畢。遞增排序過程為：將前二個元素比較，如果第一個大，則將二個數交換，再進行第二個第三個元素的比較，逆序交換，直到最大的數沉到最后；然后再次從頭開始，將前二個元素比較，重復過程，直到第二大的元素沉到倒數第二個位置，如此循環，完成排序過程[5]。

起泡排序的平均時間復雜度為。如果原序列為正序序列，循環比較還是要進行到底，需要N-1次比較，如果待排序元素龐大，會產生不必要的浪費。

改進方法：以標準元素為中心，按大小前后列隊，再將前后隊伍以此方法按大小列隊，最終完成排序。排序過程為：選擇待排序序列第一個元素作標準，將其他元素與其比較，小的列前面，大的列后面，然后分別在前后部分內部按上述方法列隊，最終完成所有元素的遞增排序，改進后的起泡排序可以叫列隊排序。

本算法主要語句如下：

If （low>high）{

Pivotloc=partition（L，low，high）；

Qsort（L，low，pivotloc-1）；

Qsort（L， pivotloc+1，high）；}

改進后的排序方法在最壞的情況下時間復雜度為，但在待排序序列為完全正序的情況下，其最好的時間復雜度為。

3 排序方法實例應用

3.1 二叉樹選擇排序

設有{65，54，78，99，86，27，42，67}序列需要排序，用二叉樹選擇排序法，第一遍比較選出最大的數99，如圖1所示，第二遍比較選出次大的數79，如圖2所示，依次比較，最終得到排序結果{16，30，41，52，53，68，79，99}。

圖1 二叉樹選擇排序第一遍比較

圖2 二叉樹選擇排序第二遍比較

3.2 折半插入排序

設有一個有序序列{54，65，78，86，99}，插入一個數27，與其中間元素78比較，確定更小的范圍{54，65，78}，再次與其中間元素65比較，確定{54，65}，再確定合適插入的位置，得到{27，54，65，78，86，99}，如此循環，將所有元素插入完畢，從而完成排序。

3.3 列隊起泡排序

設有{65，54，78，99，86，27，42，67}序列需要排序，按列隊起泡方法，

第一次列隊得{54，27，42，65，78，99，86，67}；

第二次列隊得{27，42，54，65，67，78，99，86}；

第三次列隊得{27，42，54，65，67，78，86，99}，完成遞增排序。

4 總結

討論了C語言中最重要、最常用的三種排序方法：選擇排序法、插入排序法、起泡排序法，分析各種方法的基本排序過程，探討各方法改進后的排序過程，編寫了主要程序語句，通過計算時間復雜度對各種方法改進前后進行對比，結合實例應用，結果表明：三種排序的改進方法具有良好的優越性，可以很好地應用于程序設計中，是節約系統資源的有效途徑。

參考文獻

[1] 譚浩強.C程序設計（第2版）[M].北京：清華大學出版社，1999.

[2] 嚴蔚敏，吳偉民.數據結構[M].北京：清華大學出版社，1994.

[3] 王蕓.選擇法排序在C語言中的實現方法探討[J].科技信息，

2011（23）：89-91.

[4] 達文姣，等.鏈式存儲結構上直接插入排序算法的研究與實現

[J].自動化與儀器儀表，2011（6）：40-43.

[5] 梁鳳蘭.C語言中常用的三種排序方法的探討[J].甘肅科技縱

橫，2006（5）：16-17.

作者簡介：

李支元（1975-），男，碩士，講師.研究領域：多因素評估決策系

統.