轉載請注明出處
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
