摘 要：介紹了程序語言中排序的原理及應(yīng)用，闡述了基于C語言的三種主要排序方法，提出了每種排序方法的改進(jìn)，計(jì)算出改進(jìn)后算法的時(shí)間復(fù)雜度，編寫了每種排序方法程序設(shè)計(jì)的主要語句，通過實(shí)例應(yīng)用，對(duì)每種排序方法的算法改進(jìn)前后進(jìn)行對(duì)比，證明了改進(jìn)后算法的優(yōu)越性。

關(guān)鍵詞：C語言；排序；改進(jìn)；應(yīng)用

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A

1 引言

我們?nèi)粘Ｉ钪薪?jīng)常會(huì)碰到一些需要按順序排列的情況，諸如大小、高矮等，這些一般都是排列對(duì)象數(shù)量較小、憑人力在有限的時(shí)間內(nèi)能夠完成的任務(wù)。本文討論的排序是面向計(jì)算機(jī)程序處理的，是計(jì)算機(jī)程序設(shè)計(jì)中經(jīng)常需要進(jìn)行的一類操作，可以定義為：將一組雜亂無序的記錄或數(shù)據(jù)元素通過一定的方法重新排列為按某個(gè)關(guān)鍵字的有序序列[1]。

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

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

2 三種排序及其改進(jìn)方法簡(jiǎn)述

2.1 選擇排序

基本方法：在待排序數(shù)據(jù)元素中持續(xù)選擇最大（最?。┑脑胤旁谛滦蛄械牡谝晃?、第二位……，直到所有數(shù)據(jù)全部選擇完畢。用語言描述排序過程為：第一次從原序列中選擇最大的數(shù)，放在第一位，第二次從剩下的序列中選擇最大的數(shù)放在第二位，以此類推，最后將最小的數(shù)放在最后一位，從而完成排序[3]。

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

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

這種排序方法每選擇一個(gè)較大元素需要進(jìn)行比較，其時(shí)間復(fù)雜度為，相對(duì)原來的基本方法，可以節(jié)約系統(tǒng)資源。

本算法的主要語句：

2.2 插入排序

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

直接插入排序方法每插入一個(gè)元素都要從新序列的首部開始，其時(shí)間復(fù)雜度為，隨著待排序元素的增加，其占用的時(shí)間和空間就越多，增加系統(tǒng)負(fù)擔(dān)。

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

本算法的主要語句：

改進(jìn)的插入排序又叫折半排序，其空間占用不變，但在時(shí)間上減少了元素相互比較的次數(shù)，但沒有減少元素的移動(dòng)次數(shù)，其時(shí)間復(fù)雜度仍為。

2.3 起泡排序

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

起泡排序的平均時(shí)間復(fù)雜度為。如果原序列為正序序列，循環(huán)比較還是要進(jìn)行到底，需要N-1次比較，如果待排序元素龐大，會(huì)產(chǎn)生不必要的浪費(fèi)。

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

本算法主要語句如下：

If （low>high）{

Pivotloc=partition（L，low，high）；

Qsort（L，low，pivotloc-1）；

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

改進(jìn)后的排序方法在最壞的情況下時(shí)間復(fù)雜度為，但在待排序序列為完全正序的情況下，其最好的時(shí)間復(fù)雜度為。

3 排序方法實(shí)例應(yīng)用

3.1 二叉樹選擇排序

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

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

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

3.2 折半插入排序

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

3.3 列隊(duì)起泡排序

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

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

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

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

4 總結(jié)

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

參考文獻(xiàn)

[1] 譚浩強(qiáng).C程序設(shè)計(jì)（第2版）[M].北京：清華大學(xué)出版社，1999.

[2] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京：清華大學(xué)出版社，1994.

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

2011（23）：89-91.

[4] 達(dá)文姣，等.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)上直接插入排序算法的研究與實(shí)現(xiàn)

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

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

橫，2006（5）：16-17.

作者簡(jiǎn)介：

李支元（1975-），男，碩士，講師.研究領(lǐng)域：多因素評(píng)估決策系

統(tǒng).