深入C中常用的三種排序方法總結(jié)以及探討分析
例如我們統(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、冒泡排序的程序如下：
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)：
從上面的排序的過程可以看出，如果一個(gè)已經(jīng)排好序的一組數(shù)或者經(jīng)過很少的輪數(shù)就可以排完這些數(shù)，但是循環(huán)還是要繼續(xù)進(jìn)行，這樣設(shè)計(jì)出的程序浪費(fèi)了大量的時(shí)間，所以對(duì)一這個(gè)算法我們可以重新設(shè)計(jì)。
經(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、排序的基本思想：先從第一個(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ì)容易一些。
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;}
對(duì)于選擇排序，我們也可以看到一個(gè)問題，如第一輪排序中，我們要找的是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)以后就較好地解決了這個(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、程序的編寫如下：
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;}
對(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ù)。
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");
}
以上是對(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ǔ)言編程的愛好者使用。
- C++實(shí)現(xiàn)數(shù)組的排序/插入重新排序/以及逆置操作詳解
- C++ 先對(duì)數(shù)組排序,在進(jìn)行折半查找
- C語(yǔ)言使用stdlib.h庫(kù)函數(shù)的二分查找和快速排序的實(shí)現(xiàn)代碼
- C++實(shí)現(xiàn)基數(shù)排序的方法詳解
- 用c語(yǔ)言實(shí)現(xiàn)冒泡排序,選擇排序,快速排序
- C++ 關(guān)于STL中sort()對(duì)struct排序的方法
- C++ 冒泡排序數(shù)據(jù)結(jié)構(gòu)、算法及改進(jìn)算法
- C#歸并排序的實(shí)現(xiàn)方法(遞歸,非遞歸,自然歸并)
- 利用C++的基本算法實(shí)現(xiàn)十個(gè)數(shù)排序
相關(guān)文章
C語(yǔ)言實(shí)現(xiàn)猜數(shù)字小游戲
這篇文章主要介紹了C語(yǔ)言實(shí)現(xiàn)猜數(shù)字小游戲，附有詳細(xì)代碼,需要的小伙伴可以參考一下，希望對(duì)你的遼西有所幫助2021-10-10
這篇文章主要給大家介紹了關(guān)于C++中int類型按字節(jié)打印輸出的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家學(xué)習(xí)或者使用C++具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2019-05-05
這篇文章主要為大家詳細(xì)介紹了C++表達(dá)式new與delete知識(shí)點(diǎn)，學(xué)習(xí)如何動(dòng)態(tài)創(chuàng)建對(duì)象，動(dòng)態(tài)創(chuàng)建的對(duì)象與一般對(duì)象的區(qū)別，動(dòng)態(tài)創(chuàng)建的對(duì)象的初始化以及釋放動(dòng)態(tài)分配的內(nèi)存等知識(shí)點(diǎn)，感興趣的朋友可以參考一下2016-05-05
本篇文章是對(duì)使用C++實(shí)現(xiàn)DBSCAN聚類算法的方法進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
解析C++的線性表鏈?zhǔn)酱鎯?chǔ)設(shè)計(jì)與相關(guān)的API實(shí)現(xiàn)
這篇文章主要介紹了解析C++中的線性表鏈?zhǔn)酱鎯?chǔ)設(shè)計(jì)與相關(guān)的API實(shí)現(xiàn),文中的實(shí)例很好地體現(xiàn)了如何創(chuàng)建和遍歷鏈表等基本操作,需要的朋友可以參考下2016-03-03
C++ COM編程之QueryInterface函數(shù)（二）
這篇文章主要介紹了C++ COM編程之QueryInterface函數(shù)（二）,本文是第二篇,第一篇請(qǐng)參閱相關(guān)文檔,需要的朋友可以參考下2014-10-10
C語(yǔ)言銀行系統(tǒng)課程設(shè)計(jì)
這篇文章主要為大家詳細(xì)介紹了C語(yǔ)言銀行系統(tǒng)課程設(shè)計(jì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2018-01-01
c語(yǔ)言合并兩個(gè)已排序數(shù)組的示例(c語(yǔ)言數(shù)組排序)
如何將兩個(gè)已排序數(shù)組合并成一個(gè)排序數(shù)組,下面我們給出使用c語(yǔ)言合并兩個(gè)已排序數(shù)組的示例,需要的朋友可以參考下2014-03-03
文章給大家分享了用C語(yǔ)言音樂播放器的實(shí)例代碼，對(duì)此有需要的朋友參考學(xué)習(xí)下。2018-07-07
這篇文章主要介紹了C++中的聚合類定義與用法,結(jié)合實(shí)例形式分析了C++中聚合類的簡(jiǎn)單定義、使用方法與相關(guān)注意事項(xiàng),需要的朋友可以參考下2017-08-08