所有未排序的數組是經過檢查合法的
主要的內排序包括冒泡、插入、希爾、堆排序、歸并、快速、桶排序等
其C語言實現的源文件下載地址：http://download.csdn.net/detail/mcu_tian/9530227
冒泡排序
冒泡排序應該是排序中最簡單的算法了
主要思路如下：
1： 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2：對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最后一對。在這一點，最后的元素應該會是最大的數。
3：針對所有的元素重復以上的步驟，除了最后一個。
4： 持續每次對越來越少的元素重復上面的步驟，直到沒有任何一對數字需要比較。
C語言的一般實現如下：
void bubble_sort(int *array,int num)
{
int i = 0;
int j = 0;
int temp;
for(;j < num;++j)
{
for(i= num;i >j ;–i)
{
if(array[i] < array[i-1])
{
temp =array[i];
array[i] = array[i-1];
array[i-1] = temp;
}
}
}
}
冒泡算法實現和原理都很簡單，而且是穩定的排序算法，但是該算法不論什么情況下，算法的比較交換的次數都是恒定的，都為1+2+3+4+… …+n-1
算法的復雜度為O（n^2）
插入排序
插入排序是最簡單常用的排序算法，將數組分為兩部分，排好序的數列，以及未排序的數列，將未排序的數列中的元素與排好序的數列進行比較，然后將該元素插入到已排序列的合適位置中。
直接插入排序
直接插入排序是插入排序中最簡單的一種實現
該算法的主要思路是
⒈ 從第一個元素開始，該元素可以認為已經被排序
⒉ 取出下一個元素，在已經排序的元素序列中從后向前掃描
⒊ 如果該元素（已排序）大于新元素，將該元素移到下一位置
⒋ 重復步驟3，直到找到已排序的元素小于或者等于新元素的位置
⒌ 將新元素插入到下一位置中
⒍ 重復步驟2~5
該排序算法的C語言的一般實現如下：
void insertion_sort(int *array,int num)
{
int i,j;
int temp;
i = 0;
j = 0;
for(;i < num;i++)
{
for(j=i;(j > 0)&&(array[j] < array[j-1]);j–)
{
temp =? array[j-1];
array[j-1] = array[j];
array[j] = temp;
}
}
}
該算法的最壞情況，如逆序，那么復雜度為O(N^2)
最好的情況，如已經預先排好序或者基本排好，那么復雜度為O（N）
上面實現的算法中，排序數量比較大的時候，在比較插入操作時，直接比較操作的代價和交換操作很大，是呈線性增長。
因此該算法適用于少量數據的排序。
?
希爾排序
希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個文件恰被分成一組，算法便終止。
希爾排序是特殊的插入排序
上述的增量會逐漸減少，直至減少到1，該過程中，增量會形成一個序列，稱為增量序列。
希爾排序的算法的時間復雜度跟增量序列密切相關。
具體實現如下：
1:按希爾增量序列進行排序，即增量序列為（N/2,N/4………1）
C語言的實現如下
void shell_sort(int *array,int num)//
{
int increment = 0;
int temp = 0;
int j = 0;
int k = 0;
int m = 0;
for(increment = num/2;increment > 0;increment /= 2)
{
printf(“increment:%d \n “,increment);
for(j = 0;j < increment;j++)
{
for(k = j;k < num;k = k+increment)
{
printf(“k:%d \n “,k);
for(m = k;(m >j)&&(array[m] < array[m-increment]);m = m -increment)
{
temp = array[m];
array[m] = array[m-increment];
array[m-increment] = temp;
}
}
}
}
}
使用希爾增量時希爾排序的最壞時間復雜度為O（N^2）
2:按照Hibbard增量序列進行排序，即增量序列為（2^k-1………7,3,1） 其中(2^k-1)<n
此種增量的希爾排序的最壞運行時間為O(N^3/2)
3：按照sedgwick增量序列進行排序，增量序列為（1,5,19,41,109……）
此種增量的希爾排序的的最壞運行時間為O（N^7/6）
以上兩種的實現，跟前面的希爾增量序列實現的代碼差不多1，除了最外層的循環迭代由于增量與序列的不同，稍微有點變化之外。
堆排序
堆排序(Heapsort)是指利用堆積樹（堆）這種數據結構所設計的一種排序算法。
將待排序的的序列構建成堆，大根堆，即父節點比子節點的數值要大，小根堆，父節點比子節點要小。
然后將堆的根（最大值或者最小值）取下，剩余的數據再構建成堆，再取下根值，如此迭代，直到只剩最后一個值。
出于效率的原因，堆在數組中實現，其中數組的下表對應著堆積樹的節點序列，取下的根節點，將堆中的最后一個元素進行交換，那么一直到最后，該數組就是為一個排列好的數組。
其實現如下：
void heap_sort(int *array,int num)
{
/*
初次建立大根堆，注意數組下表與堆元素序列的對應問題，數組的下表是從0開始的
o(n)
*/
int k;
for(k = num/2;k >= 0;k–)
{
int flag;
int tmp;
int i = k ;
while(2*i+1 < num)
{
if(2*i+1 == num-1)
{
flag = 2*i + 1;
}
else
{
if(array[2*i+1] > array[2*i+2])
{
flag = 2*i + 1;
}
else
{
flag = 2*i + 2;
}
}
if(array[i] > array[flag]) break;
else
{
tmp = array[flag];
array[flag] = array[i];
array[i] = tmp;
i = flag;
}
}
}
/*取下根，與堆的最后一個元素交換，再重新建堆，如此迭代往復*/
int max;
int end;
int i;
for(i = 0;i < num;i ++)
{
//put the max num to the end
end = num -1 -i;
max = array[0];
array[0] = array[end];
array[end] = max;
//rebuild the? heap,the length of array is end – 1
int flag;
int tmp;
int i = 0;
while(2*i+1 < end)
{
if(2*i+1 == end-1)
{
flag = 2*i + 1;
}
else
{
if(array[2*i+1] > array[2*i+2])
{
flag = 2*i + 1;
}
else
{
flag = 2*i + 2;
}
}
if(array[i] > array[flag]) break;
else
{
tmp = array[flag];
array[flag] = array[i];
array[i] = tmp;
i = flag;
}
}
}
}
在實現過程的時候，第一階段堆的構建最多用到2N次比較，在取掉最大值，重新建堆的一次過程中，最多用到2logi。
因此在最壞的情況下，總數最多為2NlogN-O（N）次比較。
在實踐中慢于sedgewick增量排序，是 不穩定的排序方法
歸并排序
歸并排序（MERGE-SORT）是建立在歸并操作上的一種有效的排序算法,該算法是采用分治法（Divide and Conquer）的一個非常典型的應用。
將已有序的子序列合并，得到完全有序的序列；即先使每個子序列有序，再使子序列段間有序。若將兩個有序表合并成一個有序表，稱為二路歸并，也就是下面用到的方法。
歸并排序使用遞歸實現，遞歸的終止條件為當一個序列只有一個元素的時候，為已排序序列，即返回，然后返回的兩個序列都為已排序序列，使用歸并進行合并排序。
其實現C代碼如下：
//兩個序列在同一個數組中，而且在位置上是相鄰的，根據形參將兩個序列標記出來，將兩個序列歸并結果到臨時數組中，然后在復制到數組中。
//實現過程中，很多地雷，尤其數組下標，一不小心就越界了。core dump
void merge(int *array,int *tmp_array,int lpos,int rpos,int end)
{
int left_end = rpos – 1;
int right_end = end;
int left_pos = lpos;
int right_pos = rpos;
int i;
int tmp = 0;
while((left_pos <= left_end)&&(right_pos <= right_end))
{
if(array[left_pos] < array[right_pos])
{
tmp_array[tmp] = array[left_pos];
++left_pos;
}
else
{
tmp_array[tmp] = array[right_pos];
++right_pos;
}
++tmp;
}
while(left_pos <= left_end)
{
tmp_array[tmp] = array[left_pos];
left_pos++;
++tmp;
}
while(right_pos <= right_end)
{
tmp_array[tmp] = array[right_pos];
right_pos++;
++tmp;
}
for(i = 0;i < tmp;i++)
{
array[lpos + i] = tmp_array[i];
}
}
//遞歸的實現，終止條件為只有一個數，返回
//遞歸返回之后，該序列部分為已經排好序
//將兩次的返回序列，進行歸并排序
void m_sort(int *array,int *tmp_array,int left,int right)
{
int centre = (left + right)/2;
if(left < right)
{
m_sort(array,tmp_array,left,centre);
m_sort(array,tmp_array,centre+1,right);//centre記住只能+，不能是-，坑死老爹了，要是-的話，如left = 0，right = 1的時候，centre就是 -1呀，都越界到天邊去了。調了好久。
merge(array,tmp_array,left,centre+1,right);
}
}
//這個也可以不要其實就可以了，但是為了保持與前面排序算法的實現保的函數形參保持一致，還是加上了。
void recursion_merge_sort(int *array,int num)
{
int *tmp_array;
tmp_array = malloc(num*sizeof(int));
assert(tmp_array != NULL);
m_sort(array,tmp_array,0,num-1);
free(tmp_array);
}
該實現，并沒有在每次遞歸中使用臨時數組，而是公用了一個指針傳遞過來的數組，這樣大大的減少了算法過程中，不會導致內存線性的消耗。
歸并排序的算法復雜度為O（NlogN），但是一般不用于主存的內部排序，因為可能增加排序的時候附加的內存，主要用在外部排序，對于內部排序，主要還是快排。
快速排序
快速排序采用的思想是分治思想。
快速排序是找出一個元素（理論上可以隨便找一個）作為基準(pivot),然后對數組進行分區操作,使基準左邊元素的值都不大于基準值,基準右邊的元素值 都不小于基準值，如此作為基準的元素調整到排序后的正確位置。遞歸快速排序，將其他n-1個元素也調整到排序后的正確位置。最后每個元素都是在排序后的正 確位置，排序完成。所以快速排序算法的核心算法是分區操作，即如何調整基準的位置以及調整返回基準的最終位置以便分治遞歸。
快速排序的關鍵問題在找基準值的問題，由于找的值不能太小也不太大，大概使分區后，兩個區的元素數量基本上沒有太大的偏差。
基準值的選取不能是最大值和最小值，雖然這樣最后能夠完成排序，但是算法的效率就會大大的打折扣。
若是隨機選取值，都有可能取得值過大或者過小。
比較安全的做法是使用三數中值分割法，即使用兩端的值加上中間位置的值中的中間值作為基準值，這樣可以消除最壞的情況。
在選取基準值之后，然后就類似于歸并遞歸式一樣，進行分割遞歸。
但是待排序的數組小于20以后，可以選取直接使用插入排序，因為對于小數組進行分割遞歸的話，其效率往往還不如直接使用插入。
下面為C實現的代碼
//使用三數中值法選取中至作為基準值，然后將三個數值中的中值放在倒數第二個，最大值放置于最后面
//這樣放置元素之后，那么這三個值最小值和最大值已經放在了合適的位置，不需要再進行比較移動了，在后面的算法中可以體現
//返回數組中的倒數第二個值，即基準值，這樣放的優點是能夠使左右兩邊的在遍歷的時候，可以應對極端情況，可以遍歷到所有元素。
int median_three(int *array,int left,int right)
{
int centre;
int tmp;
int i;
centre = (left+right)/2;
if(array[left] > array[right])
{
tmp = array[right];
array[right] = array[left];
array[left]= tmp;
}
if(array[centre] > array[right])
{
tmp = array[right];
array[right] = array[centre];
array[centre]= tmp;
}
if(array[left] > array[centre])
{
tmp = array[centre];
array[centre] = array[left];
array[left] = tmp;
}
tmp = array[centre];
array[centre] = array[right-1];
array[right-1] = tmp;
return array[right-1];
}
//快排實現
void q_sort(int*array,int left,int right)
{
int pivot;
int left_i;
int right_i;
int tmp;
if(right-left < 3)
{
insertion_sort(array+left,right-left+1); ?//當待排的數量小于3的時候，就直接快排，其實小于20可以，這里是了驗證
}
else
{
pivot = median_three(array,left,right);//找出基準值
left_i = left + 1; //從左邊加一個，在三數中值的時候，小于中間值的已經放在了左邊，因此沒有必要再進行比較操作
right_i = right -2;//同上，加上中間值放在倒數第二個位置
while(1)
{
while(array[left_i] < pivot )//相等就停止，左右兩邊都是，這樣可以使相等的值，最大限度地在基準值的左右兩邊均勻分布
{
++left_i;
}
while(array[right_i] > pivot)
{
–right_i;
}
if(left_i < right_i)
{
tmp = array[left_i];
array[left_i] = array[right_i];
array[right_i] = tmp;
}
else //當左邊的游標等于或者大于右邊的右邊時候，該趟分割結束
{
break;
}
}
//由于校準值放在數組的倒數第二個，因此將其放到合適的位置去，即與左游標對應的值與其進行交換即可
tmp = array[left_i];
array[left_i] = array[right-1];
array[right-1] = tmp;
//繼續迭代
q_sort(array,left,left_i);
q_sort(array,left_i+1,right);
}
}
void quick_sort(int *arrary,int num)
{
q_sort(arrary,0,num-1);
}
快速排序是實踐中最快的已知算法，平均運行時間為O(NlogN)，最壞的情況是O（N^2）
只要不要在選取校準值太壞以及以及在處理相等的值時停止，最壞的情況基本上是可以避免的。
桶排序
桶排序非常高效
但是該算法只能用于整數排序。
算法的實現
其具體的算法實現為，使用一個數組，初始化的值為0，數組長度不小于于待排序的所有數據的最大值
遍歷一遍待排序的數據序列，將數列中的數據對應到數組中的下標，將數組中該元素置為1或者加1。
例如
滿足條件的數組A[i] ，初始化值都為0
待排序的序列a,b,c
遍歷一遍待排序的序列，將序列中的元素對應到元素的位置，將值+1，例如：A[a] +=1;
然后再遍歷一遍數組，
for(i = 0;i < max;i++)
{
while(A[i])
{
輸出該值；
A[i]–
}
}
則輸出的值的序列就是排序過后的序列了。
該算法的運算復雜度為O(max) ? ?max ?為待排序列中的最大值
max的確定可以遍歷一遍數組確定，也可以根據輸入的范圍估計。
但是該算法不能用于浮點排序，只能用于整數排序，如果是有負數，那么負數和下標的對應關系需要注意。
而且當max很大的時候，并且排序的元素不是很多的時候，會占用大量的內存空間，造成大量的內存浪費，效率反而會降低。
因此該種算法只適用于該max值不大的整數排序。
在C++中可以使用bool
或者使用位運算，用位中0和1標識序列中存在的數值
但是該只能用于沒有重復的數據，或者是可以忽略重復的數據。
位的排序在以前的博客中有寫到，鏈接為：
http://blog.csdn.net/mcu_tian/article/details/46834589
參考資料：數據結構與算法分析：C語言描述（原書第2版）
