C語言常用的三種排序方法總結與探討
2019-11-17 05:46:47
供稿：網友
C語言常用的三種排序方法總結與探討 排序是程序設計中非常重要的內容，它的功能是將一組無序的的數據，排列成有序的數據序列，經過排列后的數據，要么是從大到小排列，要么是從小到大排列。一般也只有這兩種情況。 例如我們統計班級學生的成績，那么一般是按照學號來進行統計，原來成績是無序排列的，這樣的話非常不適合于我們對成績的查詢，那么一般我們進行成績查詢之前，先進行排序，如按照高分到低分的排序，這樣可以很快地查出本班的最高分和最低分，和成績比較靠前或靠后的學生。排序有很多種方法，常用的有三種：冒泡排序、選擇排序、插入排序等，下面我們就對這三種方法做一下分析和比較，以便大家能夠更好的理解和應用。一、冒泡排序 1、冒泡排序的基本思想：對于n個數進行排序（現假定是從大到小排序，以下均按此進行），將相鄰兩個數依次比較，將大數調在前頭：也就是說第一個數和第二個數比較，大數放前，小數放后，第二個和第三個進行比較，大數放前、小數放后，然后依次類推。。。經過第一輪比較以后，我們找到一個最小數在最下面（沉底）。然后進行下一輪比較，最后一個數就不用再參加比較了，所以本輪就可以少比較一次。很顯然，需要用雙重循環來設計這個問題，外層循環控制進行的輪數，內層循環控制每輪比較的次數，那么到底需要多少輪、每輪需要多少次，我們通過一個實例看一下：2、排序過程舉例：外循環1輪2輪3輪4輪內循環5個數比較4次4個數比較3次3個數比較2次2個數比較1次75869 1次2次3次4次
1次2次3次1 次2次1次758697856978659786958769587695879658796
58976598765 最小的數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]) 在此程序段的上面加上輸入部分和在程序段加上排序后的輸出。程序的改進： 4、算法的改進：從上面的排序的過程可以看出，假如一個已經排好序的一組數或者經過很少的輪數就可以排完這些數，但是循環還是要繼續進行，這樣設計出的程序浪費了大量的時間，所以對一這個算法我們可以重新設計。 經過修改后的程如下：for(i=0;i<10&&!swap;i++){swap=1;for(j=0;j<10-I;j++) if(a[j]<a[j+1])
}二、選擇排序 1、排序的基本思想：先從第一個數開始起，用第一個數和其它的數進行比較，假如比第一個數大就交換位置，否則不進行交換，這樣經過第一輪比較我們就能夠找出最大值放在第一位置，然后從第二個位置起再找次大數，這樣依次下去，就可以進行整個數的排序，實踐證實，n個數最多需要n-1輪排序就可以了。 2、排序過程舉例：外循環1輪2輪3輪4輪內循環5個數比較4次4個數比較3次3個數比較2次2個數比較1次75869 1次2次3次4次1次2次3次1 次2次1次758698576985
76995768975689756898567986579876598765 最大的數9找到，其余4個數找次大數次大數8找到，其余3個數找7找到，其余2個數找最后兩個數一次比較選擇排序較冒泡輕易理解，程序編寫也要相對輕易一些。
for(i=0;i<10;i++)for(j=i+1;j<10;j++) if(a[i]<a[j]) 對于選擇排序，我們也可以看到一個問題，如第一輪排序中，我們要找的是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)}這樣算法經過改進以后就較好地解決了這個問題。三、插入排序1、插入排序基本思想：（假定從大到小排序）依次從后面拿一個數和前面已經排好序的數進行比較，比較的過程是從已經排好序的數中最后一個數開始比較，假如比這個數，繼續往前面比較，直到找到比它大的數，然后就放在它的后面，假如一直沒有找到，肯定這個數已經比較到了第一個數，那就放到第一個數的前面。那么一般情況下，對于采用插入排序法去排序的一組數，可以先選 取第一個數做為已經排好序的一組數。然后把第二個放到正確位置2、程序的編寫如下：for(i=1;i<10;i++)//i從0開始或者1開始都可以。其它不變。for(j=i;j>0;j--) if(a[j]<a[j-1]) 對于這個程序也有需要修該的地方，以上程序的排序實際上也是基于交換思想進行排序，也可以進行真正意義上的排序，即：先把待排序的數取出來，然后找出應該插入的位置，找到后，將待插入位置后的數據統統后移，原待排數據已經取出放于臨時變量中。然后把這個數據插入到正確的空余位置就可以了。那么對于基于交換的插入排序，沒有找到位置之前，也進行了交換，所以我們也可以進行程序的改進。那么此程序的改進，肯定不能進行減少交換次數，因為我們知道假如到找到位置再進行交換，那么肯定已經找亂了原來的排序結果，所以只能是找位置，騰位置、放元素這幾道手續。main(){int i,j,t,a[]=; for(i=1;i<10;i++)
{t=a[i];
