轉載請注明出處
http://blog.csdn.net/pony_maggie/article/details/35819279
作者:小馬
從題目看,首先不是全部是若干。排序算法很多,我個人的能力也有限,不可能都講到。另外,是簡單匯總,是希望能用最簡單的代碼,最簡短的語言說明問題,不搞太多理論分析。
就像前面說的,排序算法有很多,而且不存在哪一種最不好,哪一種最好這樣的說法。根據用途不同選擇最適合的就行了。不過僅從時間復雜度來看,基本上有兩種,一種是O(n^2), 一種是O(nlogn)。
所謂的時間復雜度,其實是基于多少次基本操作定義的,在排序算法中,基本操作指兩類,一是比較,二是記錄從一個位置移動另一個位置。下面講到的排序算法都會涉及到這些操作。
一直接插入排序
先從一個最簡單的切入。它的思種是這樣的,把一個數插入到已排好的序列中。比如已有一個有序序列:
{ 12, 23, 25, 40}
現在有一個數18要插入進來,并且保證插入后序列還是有序。18開始和序列中的所有數逐一比較(從右向左比較),比40小,40后移,比25小,25后移,比23小,23后移,跟12比,發現比12大,停在這里,插入到23的位置,最終變為:
{ 12, 18, 23, 25, 40}
上面的過程叫一趟插入排序,基于這個思想, 我們可以認為數組第一個元素是有序的,所以可以從第二個元素開始,每個元素都做一趟插入排序就可以得到一個有序序列。代碼就很簡單了,
~~~
int insertSort(int nArray[], int nLength)
{
int i = 0;
int j = 0;
int nSerity = 0;//備份要插入的那個元素
for (i = 1; i < nLength; i++)
{
if (nArray[i] < nArray[i-1])
{
nSerity = nArray[i];
nArray[i] = nArray[i-1];
for (j = i-2; (j >= 0)&&(nSerity < nArray[j]); j--)
{
nArray[j+1] = nArray[j];
}
nArray[j+1] = nSerity;
}
}
return 0;
}
~~~
很容易看出它的時間復雜度是O(n^2)
二冒泡排序
這個排序算法基本是大學老師必講的,因為它除了簡單之外,也確實比較好玩。思路是這樣的,一個無序序列a[n], a[1]和a[2]比較,如果a[1]>a[2], 它們就交換位置,否則不做處理。繼續a[2]和a[3]同樣的原理比較,一直到a[n-1]和a[n]比較。
上面的過程叫一趟冒泡,請你在腦海里想像下這個過程,我下面要說的這個結論希望你能想明白,那就是經過一趟冒泡后,序列中最大的那個元素已經被換到a[n]的位置了。有沒有覺得這個過程就像冒泡一樣,只不過這個泡是向下冒的。
做第二趟冒泡時,只要對a[1]~a[n-1]操作就行了,結果是序列中第二大的那個元素在a[n-1]的位置了。然后經過n趟冒泡后,排序就完成了。
通過上面的過程也很容易得出冒泡排序的時間復雜度是O(n^2),可以上代碼了,
~~~
//bChange作用是為了對于已排好序的序列,能
//及時退出來。
int bubbleSort(int nArray[], int nLength)
{
int i = 0;
int j = 0;
int nTemp = 0;
bool bChange = true;
for (i = 0; (i < nLength) &&(bChange); i++)
{
bChange = false;
for (j = 0; j < (nLength - i - 1); j++)
{
if (nArray[j] > nArray[j+1])
{
nTemp = nArray[j];
nArray[j] = nArray[j+1];
nArray[j+1] = nTemp;
bChange = true;
}
}
}
return 0;
}
~~~
可以好好理解一下代碼中bChange變量的作用,這里不多說解釋了,留給大家思考。
這篇就打算寫這么多了,主要篇幅太長怕大家看著厭煩,過幾天有空了再接著寫吧。
代碼下載地址:
http://download.csdn.net/detail/pony_maggie/7568971
或
https://github.com/pony-maggie/SortDemo