摘 要:介紹了程序語言中排序的原理及應(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)粘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).