排序是程序設(shè)計(jì)中非常重要的內(nèi)容，它的功能是將一組無(wú)序的的數(shù)據(jù)，排列成有序的數(shù)據(jù)序列，經(jīng)過排列后的數(shù)據(jù)，要么是從大到小排列，要么是從小到大排列。一般也只有這兩種情況。

    例如我們統(tǒng)計(jì)班級(jí)學(xué)生的成績(jī)，那么一般是按照學(xué)號(hào)來(lái)進(jìn)行統(tǒng)計(jì)，原來(lái)成績(jī)是無(wú)序排列的，這樣的話非常不適合于我們對(duì)成績(jī)的查詢，那么一般我們進(jìn)行成績(jī)查詢之前，先進(jìn)行排序，如按照高分到低分的排序，這樣可以很快地查出本班的最高分和最低分，和成績(jī)比較靠前或靠后的學(xué)生。
排序有很多種方法，常用的有三種：冒泡排序、選擇排序、插入排序等，下面我們就對(duì)這三種方法做一下分析和比較，以便大家能夠更好的理解和應(yīng)用。

一、冒泡排序

    1、冒泡排序的基本思想：對(duì)于n個(gè)數(shù)進(jìn)行排序（現(xiàn)假定是從大到小排序，以下均按此進(jìn)行），將相鄰兩個(gè)數(shù)依次比較，將大數(shù)調(diào)在前頭：也就是說第一個(gè)數(shù)和第二個(gè)數(shù)比較，大數(shù)放前，小數(shù)放后，第二個(gè)和第三個(gè)進(jìn)行比較，大數(shù)放前、小數(shù)放后，然后依次類推。。。經(jīng)過第一輪比較以后，我們找到一個(gè)最小數(shù)在最下面（沉底）。然后進(jìn)行下一輪比較，最后一個(gè)數(shù)就不用再參加比較了，所以本輪就可以少比較一次。
很顯然，需要用雙重循環(huán)來(lái)設(shè)計(jì)這個(gè)問題，外層循環(huán)控制進(jìn)行的輪數(shù)，內(nèi)層循環(huán)控制每輪比較的次數(shù)，那么到底需要多少輪、每輪需要多少次，我們通過一個(gè)實(shí)例看一下：

2、排序過程舉例：

外循環(huán)	1輪				2輪			3輪		4輪
內(nèi)循環(huán)	5個(gè)數(shù)比較4次				4個(gè)數(shù)比較3次			3個(gè)數(shù)比較2次		2個(gè)數(shù)比較1次
7 5 8 6 9	1次	2次	3次	4次	1次	2次	3次	1 次	2次	1次
	7 5 8 6 9	7 8 5 6 9	7 8 6 5 9	7 8 6 9 5	8 7 6 9 5	8 7 6 9 5	8 7 9 6 5	8 7 9 6 5	8 9 7 6 5	9 8 7 6 5
	最小的數(shù)5沉底，其余4個(gè)數(shù)繼續(xù)比較				次小數(shù)6沉底，其余3個(gè)數(shù)			7沉底，其余2個(gè)數(shù)比較		最后兩個(gè)數(shù)一次比較

    那么通過這個(gè)排序過程，我們了解了怎樣去進(jìn)行排序，那么到底誰(shuí)是氣泡呢，我們可以從中找出答案，那么從大到小進(jìn)行排序，較大的一些數(shù)就是氣泡。隨著排序的進(jìn)行，氣泡逐步上升。

    從這個(gè)排序過種中，還可以看出，5個(gè)數(shù)實(shí)際經(jīng)過4輪就可以了，實(shí)踐證明，n個(gè)數(shù)最多需要n-1輪排序就可以了。

    3、冒泡排序的程序如下：

在此程序段的上面加上輸入部分和在程序段加上排序后的輸出。
程序的改進(jìn)：

   4、算法的改進(jìn)：

從上面的排序的過程可以看出，如果一個(gè)已經(jīng)排好序的一組數(shù)或者經(jīng)過很少的輪數(shù)就可以排完這些數(shù)，但是循環(huán)還是要繼續(xù)進(jìn)行，這樣設(shè)計(jì)出的程序浪費(fèi)了大量的時(shí)間，所以對(duì)一這個(gè)算法我們可以重新設(shè)計(jì)。
 經(jīng)過修改后的程如下：

二、選擇排序

    1、排序的基本思想：先從第一個(gè)數(shù)開始起，用第一個(gè)數(shù)和其它的數(shù)進(jìn)行比較，如果比第一個(gè)數(shù)大就交換位置，否則不進(jìn)行交換，這樣經(jīng)過第一輪比較我們就能夠找出最大值放在第一位置，然后從第二個(gè)位置起再找次大數(shù)，這樣依次下去，就可以進(jìn)行整個(gè)數(shù)的排序，實(shí)踐證明，n個(gè)數(shù)最多需要n-1輪排序就可以了。
        2、排序過程舉例：

外循環(huán)	1輪				2輪			3輪		4輪
內(nèi)循環(huán)	5個(gè)數(shù)比較4次				4個(gè)數(shù)比較3次			3個(gè)數(shù)比較2次		2個(gè)數(shù)比較1次
7 5 8 6 9	1次	2次	3次	4次	1次	2次	3次	1 次	2次	1次
	7 5 8 6 9	8 5 7 6 9	8 5 7 6 9	9 5 7 6 8	9 7 5 6 8	9 7 5 6 8	9 8 5 6 7	9 8 6 5 7	9 8 7 6 5	9 8 7 6 5
	最大的數(shù)9找到，其余4個(gè)數(shù)找次大數(shù)				次大數(shù)8找到，其余3個(gè)數(shù)找			7找到，其余2個(gè)數(shù)找		最后兩個(gè)數(shù)一次比較

選擇排序較冒泡容易理解，程序編寫也要相對(duì)容易一些。

對(duì)于選擇排序，我們也可以看到一個(gè)問題，如第一輪排序中，我們要找的是9才是最大值，所以其它的交換完全沒有必要進(jìn)行，其它各輪都存在這樣的情況，所以我們可以想辦法取消這種情況，也就是說我們真正找到的最大值的位置后再進(jìn)行交換。

這樣算法經(jīng)過改進(jìn)以后就較好地解決了這個(gè)問題。

三、插入排序

1、插入排序基本思想：（假定從大到小排序）依次從后面拿一個(gè)數(shù)和前面已經(jīng)排好序的數(shù)進(jìn)行比較，比較的過程是從已經(jīng)排好序的數(shù)中最后一個(gè)數(shù)開始比較，如果比這個(gè)數(shù)，繼續(xù)往前面比較，直到找到比它大的數(shù)，然后就放在它的后面，如果一直沒有找到，肯定這個(gè)數(shù)已經(jīng)比較到了第一個(gè)數(shù)，那就放到第一個(gè)數(shù)的前面。
那么一般情況下，對(duì)于采用插入排序法去排序的一組數(shù)，可以先選 取第一個(gè)數(shù)做為已經(jīng)排好序的一組數(shù)。然后把第二個(gè)放到正確位置
2、程序的編寫如下：

對(duì)于這個(gè)程序也有需要修該的地方，以上程序的排序?qū)嶋H上也是基于交換思想進(jìn)行排序，也可以進(jìn)行真正意義上的排序，即：先把待排序的數(shù)取出來(lái)，然后找出應(yīng)該插入的位置，找到后，將待插入位置后的數(shù)據(jù)統(tǒng)統(tǒng)后移，原待排數(shù)據(jù)已經(jīng)取出放于臨時(shí)變量中。然后把這個(gè)數(shù)據(jù)插入到正確的空余位置就可以了。

那么對(duì)于基于交換的插入排序，沒有找到位置之前，也進(jìn)行了交換，所以我們也可以進(jìn)行程序的改進(jìn)。那么此程序的改進(jìn)，肯定不能進(jìn)行減少交換次數(shù)，因?yàn)槲覀冎廊绻秸业轿恢迷龠M(jìn)行交換，那么肯定已經(jīng)找亂了原來(lái)的排序結(jié)果，所以只能是找位置，騰位置、放元素這幾道手續(xù)。

以上是對(duì)幾種排序方法進(jìn)行了探討，關(guān)于排序問題，是程序設(shè)計(jì)中的一項(xiàng)非常重要的內(nèi)容，所以在《數(shù)據(jù)結(jié)構(gòu)與算法》中作為一項(xiàng)重要的內(nèi)容做了深入的講解，我們這在這里只做簡(jiǎn)單的探討，以備C語(yǔ)言的初學(xué)者或正在學(xué)習(xí)C語(yǔ)言編程的愛好者使用。

最新評(píng)論