排序是程序設(shè)計中非常重要的內(nèi)容，它的功能是將一組無序的的數(shù)據(jù)，排列成有序的數(shù)據(jù)序列，經(jīng)過排列后的數(shù)據(jù)，要么是從大到小排列，要么是從小到大排列。一般也只有這兩種情況。
例如我們統(tǒng)計班級學(xué)生的成績，那么一般是按照學(xué)號來進(jìn)行統(tǒng)計，原來成績是無序排列的，這樣的話非常不適合于我們對成績的查詢，那么一般我們進(jìn)行成績查詢之前，先進(jìn)行排序，如按照高分到低分的排序，這樣可以很快地查出本班的最高分和最低分，和成績比較靠前或靠后的學(xué)生。
排序有很多種方法，常用的有三種：冒泡排序、選擇排序、插入排序等，下面我們就對這三種方法做一下分析和比較，以便大家能夠更好的理解和應(yīng)用。
一、冒泡排序
1、冒泡排序的基本思想：對于n個數(shù)進(jìn)行排序（現(xiàn)假定是從大到小排序，以下均按此進(jìn)行），將相鄰兩個數(shù)依次比較，將大數(shù)調(diào)在前頭：也就是說第一個數(shù)和第二個數(shù)比較，大數(shù)放前，小數(shù)放后，第二個和第三個進(jìn)行比較，大數(shù)放前、小數(shù)放后，然后依次類推。。。經(jīng)過第一輪比較以后，我們找到一個最小數(shù)在最下面（沉底）。然后進(jìn)行下一輪比較，最后一個數(shù)就不用再參加比較了，所以本輪就可以少比較一次。
很顯然，需要用雙重循環(huán)來設(shè)計這個問題，外層循環(huán)控制進(jìn)行的輪數(shù)，內(nèi)層循環(huán)控制每輪比較的次數(shù)，那么到底需要多少輪、每輪需要多少次，我們通過一個實(shí)例看一下：
2、排序過程舉例：
外循環(huán) | 1輪 | 2輪 | 3輪 | 4輪 |
內(nèi)循環(huán) | 5個數(shù)比較4次 | 4個數(shù)比較3次 | 3個數(shù)比較2次 | 2個數(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個數(shù)繼續(xù)比較 | 次小數(shù)6沉底，其余3個數(shù) | 7沉底，其余2個數(shù)比較 | 最后兩個數(shù)一次比較 |
那么通過這個排序過程，我們了解了怎樣去進(jìn)行排序，那么到底誰是氣泡呢，我們可以從中找出答案，那么從大到小進(jìn)行排序，較大的一些數(shù)就是氣泡。隨著排序的進(jìn)行，氣泡逐步上升。
從這個排序過種中，還可以看出，5個數(shù)實(shí)際經(jīng)過4輪就可以了，實(shí)踐證明，n個數(shù)最多需要n-1輪排序就可以了。
3、冒泡排序的程序如下：
for(i=0;i<10;i++)
for(j=0;j<10-i;j++)
if(a[j]<a[j+1])
{t=a[j];a[j]=a[j+1];a[j+1]=t;}
在此程序段的上面加上輸入部分和在程序段加上排序后的輸出。
程序的改進(jìn)： 4、算法的改進(jìn)：
從上面的排序的過程可以看出，如果一個已經(jīng)排好序的一組數(shù)或者經(jīng)過很少的輪數(shù)就可以排完這些數(shù)，但是循環(huán)還是要繼續(xù)進(jìn)行，這樣設(shè)計出的程序浪費(fèi)了大量的時間，所以對一這個算法我們可以重新設(shè)計。
經(jīng)過修改后的程如下：
for(i=0;i<10&&!swap;i++)
{
swap=1;
for(j=0;j<10-I;j++)
if(a[j]<a[j+1])
{t=a[j];a[j]=a[j+1];a[j+1]=t;swap=0;}
}
二、選擇排序
1、排序的基本思想：先從第一個數(shù)開始起，用第一個數(shù)和其它的數(shù)進(jìn)行比較，如果比第一個數(shù)大就交換位置，否則不進(jìn)行交換，這樣經(jīng)過第一輪比較我們就能夠找出最大值放在第一位置，然后從第二個位置起再找次大數(shù)，這樣依次下去，就可以進(jìn)行整個數(shù)的排序，實(shí)踐證明，n個數(shù)最多需要n-1輪排序就可以了。
2、排序過程舉例：
外循環(huán) | 1輪 | 2輪 | 3輪 | 4輪 |
內(nèi)循環(huán) | 5個數(shù)比較4次 | 4個數(shù)比較3次 | 3個數(shù)比較2次 | 2個數(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個數(shù)找次大數(shù) | 次大數(shù)8找到，其余3個數(shù)找 | 7找到，其余2個數(shù)找 | 最后兩個數(shù)一次比較 |
選擇排序較冒泡容易理解，程序編寫也要相對容易一些。
for(i=0;i<10;i++)
for(j=i+1;j<10;j++)
if(a[i]<a[j])
{t=a[i];a[i]=a[j];a[j]=t;}
對于選擇排序，我們也可以看到一個問題，如第一輪排序中，我們要找的是9才是最大值，所以其它的交換完全沒有必要進(jìn)行，其它各輪都存在這樣的情況，所以我們可以想辦法取消這種情況，也就是說我們真正找到的最大值的位置后再進(jìn)行交換。
for(i=0;i<10;i++)
{ p=i;
for(j=i+1;j<10;j++)
if(a[p]<a[j])
p=j;
if(p!=i)
{t=a[i];a[i]=a[j];a[j]=t;}
}
這樣算法經(jīng)過改進(jìn)以后就較好地解決了這個問題。三、插入排序
1、插入排序基本思想：（假定從大到小排序）依次從后面拿一個數(shù)和前面已經(jīng)排好序的數(shù)進(jìn)行比較，比較的過程是從已經(jīng)排好序的數(shù)中最后一個數(shù)開始比較，如果比這個數(shù)，繼續(xù)往前面比較，直到找到比它大的數(shù)，然后就放在它的后面，如果一直沒有找到，肯定這個數(shù)已經(jīng)比較到了第一個數(shù)，那就放到第一個數(shù)的前面。
那么一般情況下，對于采用插入排序法去排序的一組數(shù)，可以先選 取第一個數(shù)做為已經(jīng)排好序的一組數(shù)。然后把第二個放到正確位置
2、程序的編寫如下：
for(i=1;i<10;i++)//i從0開始或者1開始都可以。其它不變。
for(j=i;j>0;j--)
if(a[j]<a[j-1])
{t=a[j];a[j]=a[j-1];a[j-1]=t;}
對于這個程序也有需要修該的地方，以上程序的排序?qū)嶋H上也是基于交換思想進(jìn)行排序，也可以進(jìn)行真正意義上的排序，即：先把待排序的數(shù)取出來，然后找出應(yīng)該插入的位置，找到后，將待插入位置后的數(shù)據(jù)統(tǒng)統(tǒng)后移，原待排數(shù)據(jù)已經(jīng)取出放于臨時變量中。然后把這個數(shù)據(jù)插入到正確的空余位置就可以了。
那么對于基于交換的插入排序，沒有找到位置之前，也進(jìn)行了交換，所以我們也可以進(jìn)行程序的改進(jìn)。那么此程序的改進(jìn)，肯定不能進(jìn)行減少交換次數(shù)，因?yàn)槲覀冎廊绻秸业轿恢迷龠M(jìn)行交換，那么肯定已經(jīng)找亂了原來的排序結(jié)果，所以只能是找位置，騰位置、放元素這幾道手續(xù)。
main()
{
int i,j,t,a[]={12,11,2,3,6,67,89,0,1,3};
for(i=1;i<10;i++)
{t=a[i];
j=i-1;
while(j>=0&&t>a[i])
{a[j+1]=a[j];
j--;
}
a[j+1]=t;
for(i=0;i<10;i++)
printf("%d ",a[i]);
printf("/n");
}
以上是對幾種排序方法進(jìn)行了探討，關(guān)于排序問題，是程序設(shè)計中的一項非常重要的內(nèi)容，所以在《數(shù)據(jù)結(jié)構(gòu)與算法》中作為一項重要的內(nèi)容做了深入的講解，我們這在這里只做簡單的探討，以備C語言的初學(xué)者或正在學(xué)習(xí)C語言編程的愛好者使用。
