排序是程序設計中非常重要的內容,它的功能是將一組無序的的數據,排列成有序的數據序列,經過排列後的數據,要麼是從大到小排列,要麼是從小到大排列。一般也只有這兩種情況。
例如我們統計班級學生的成績,那麼一般是按照學號來進行統計,原來成績是無序排列的,這樣的話非常不適合於我們對成績的查詢,那麼一般我們進行成績查詢之前,先進行排序,如按照高分到低分的排序,這樣可以很快地查出本班的最高分和最低分,和成績比較靠前或靠後的學生。
排序有很多種方法,常用的有三種:冒泡排序、選擇排序、插入排序等,下面我們就對這三種方法做一下分析和比較,以便大家能夠更好的理解和應用。
一、冒泡排序
1、冒泡排序的基本思想:對於n個數進行排序(現假定是從大到小排序,以下均按此進行),將相鄰兩個數依次比較,將大數調在前頭:也就是說第一個數和第二個數比較,大數放前,小數放後,第二個和第三個進行比較,大數放前、小數放後,然後依次類推。。。經過第一輪比較以後,我們找到一個最小數在最下面(沉底)。然後進行下一輪比較,最後一個數就不用再參加比較了,所以本輪就可以少比較一次。
很顯然,需要用雙重循環來設計這個問題,外層循環控制進行的輪數,內層循環控制每輪比較的次數,那麼到底需要多少輪、每輪需要多少次,我們通過一個實例看一下:
2、排序過程舉例:
外循環
1輪
2輪
3輪
4輪
內循環
5個數比較4次
4個數比較3次
3個數比較2次
2個數比較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
最小的數5沉底,其余4個數繼續比較
次小數6沉底,其余3個數
7沉底,其余2個數比較
最後兩個數一次比較
那麼通過這個排序過程,我們了解了怎樣去進行排序,那麼到底誰是氣泡呢,我們可以從中找出答案,那麼從大到小進行排序,較大的一些數就是氣泡。隨著排序的進行,氣泡逐步上升。
從這個排序過種中,還可以看出,5個數實際經過4輪就可以了,實踐證明,n個數最多需要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;}
在此程序段的上面加上輸入部分和在程序段加上排序後的輸出。
程序的改進:
4、算法的改進:
從上面的排序的過程可以看出,如果一個已經排好序的一組數或者經過很少的輪數就可以排完這些數,但是循環還是要繼續進行,這樣設計出的程序浪費了大量的時間,所以對一這個算法我們可以重新設計。
經過修改後的程如下:
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、排序的基本思想:先從第一個數開始起,用第一個數和其它的數進行比較,如果比第一個數大就交換位置,否則不進行交換,這樣經過第一輪比較我們就能夠找出最大值放在第一位置,然後從第二個位置起再找次大數,這樣依次下去,就可以進行整個數的排序,實踐證明,n個數最多需要n-1輪排序就可以了。
2、排序過程舉例:
外循環
1輪
2輪
3輪
4輪
內循環
5個數比較4次
4個數比較3次
3個數比較2次
2個數比較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
最大的數9找到,其余4個數找次大數
次大數8找到,其余3個數找
7找到,其余2個數找
最後兩個數一次比較
選擇排序較冒泡容易理解,程序編寫也要相對容易一些。
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才是最大值,所以其它的交換完全沒有必要進行,其它各輪都存在這樣的情況,所以我們可以想辦法取消這種情況,也就是說我們真正找到的最大值的位置後再進行交換。
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;}
}
這樣算法經過改進以後就較好地解決了這個問題。