十大排序大總結
BubbleSort（冒泡排序）
定義：在同一個數組中，從數組第一個數開始，相鄰兩個數進行比較，按照小左大右或者大右小左的順序，依次循環遍歷，進行排序！
void BubbleSort(int *arr,int Length)
{
int i = 0;
int j = 1;
int sys = 0;
for (i = 0; i < Length-1; i++)
{
for (j = 0; j < Length-i-1; j++)
{
if (arr[j]>arr[j+1])
{
arr[j] = arr[j]^arr[j+1];
arr[j+1] = arr[j]^arr[j+1];
arr[j] = arr[j]^arr[j+1];
}
}
sys++;
}
return ;
}</code></pre>
改進版冒泡排序
在原有的基礎上，我們添加了標記！記錄了最后一次交換的位置！
如5，1，4，6，3，2，7，8，9。最后一次交換的位置在2處，并且設定我們每次循環的到2，不對7，8，9
進行比較，節省我們運算的效率！
冒泡排序是對 全部已經排好 序列排序最快的
void BetterBubbleSort(int *arr,int Length)
{
int i = 0;
int j = 1;
int pmark;
int sys = 0;
for (; i < Length-1; i++)
{
pmark = 0;
for (j = 0; j < Length-i-1; j++)
{
if (arr[j]>arr[j+1])
{
arr[j] = arr[j]^arr[j+1];
arr[j+1] = arr[j]^arr[j+1];
arr[j] = arr[j]^arr[j+1];
pmark = j+1;
}
}
i == Length - pmark - 1;
sys++;
}
return ;
}</code></pre>
不帶中間變量實現兩個相同類型不同值變量間的互換
- 加減法
int a = 5;
int b = 3;
a = a+b;
b = a-b;
a = a-b;
- 異或^
int a = 5;
int b = 3;
a = a^b;
b = a^b;
a = a^b;
ps:若對于 *a ， *b 值進行交換， *a ， *b 不能指向同一塊地址空間！
SelectSort選擇排序
首先，用第一個數去和所有數進行比較，選出其中最小的數，放在第一位，在用第二個數去和全部數進行比較，最小的放在第二位，依次循環遍歷！
void SelectSort(int *Arr,int nLength)
{
int i = 0;
int j = 1;
int min = 0;
for (i = 0; i < nLength; i++)
{
for (j = i; j < nLength-1; j++)
{
if (Arr[i] > Arr[j])
{
Arr[j] = Arr[j]^Arr[i];
Arr[i] = Arr[j]^Arr[i];
Arr[j] = Arr[j]^Arr[i];
}
}
}
}
代碼優化：把每次都交換的位置，換成比較完之后，有一個int記下來，不用每次比較完進行交換，而是最后直接用記錄的數組下標進行交換！
InsertSort插入排序
把當前數組分成兩部分，第一部分有序，第二部分無序，將無序數組依次插入有序數組里去！
例如數組：10，20，3，8，55.用一個temp保存無序數組第一個
適合場景：每個元素距離其最終位置不遠時，我們選擇插入排序。
- 首先把10當成有序數組的最后一位，20當成無序數組的第一位，20和10比較，20比10大不移動。
- 之后用無序數組向后移動一位，變成3，3和20比較，比20小，把3放10和20中間，在用3和10比，比10小，放10前面。
- 此時有序最后一位仍是20，用8再去和前面幾位有序數組進行比較，一次循環遍歷！
void InsertSort(int arr[],int nLength)
{
int j;//有序數組的最后位置
int i;//無序數組的第一個
int temp;
if(arr == NULL || nLength <=0)return;
for(i = 1;i<nLength;i++)
{
j = i-1;
temp = arr[i]; //保存無序數組的第一個
//進行比較
while(temp < arr[j] && j >=0)
{
//將前一個元素向后移動
arr[j+1] = arr[j];
j--;
}
//將元素放入其對應位置
arr[j+1] = temp;
}
}</code></pre>
快排
快排的優點：是 比較次數最少 的排序！
挖坑填補法
例如數組： 7 ，2，8，4，3，5。我們用temp標記7
- 我們將第一數7當標準值，此時相當于7是一個坑（用粗斜體標記），然后我們從后面依次找比標準值7小的數，
第一個5就比7小，我們將5放到7的坑里。數組變成5，2，8，4，3， 7 ，這是坑變成最后位數！
- 然后我們在前面找一個比標準值大的數，第3個數8比標準值大，這是我們將8填到數7的坑里！這是數組變成了：
5，2， 7 ，4，3，8，我們對已經操作的數，不再進行考慮比較！
- 這時我們在從前面開始找一個數比標準值小的數3，填坑。數組變成了：2，3，4， 7 ，8，此時前面和后面的數，
皆比標準值小和大！
- 標準值前面的數我們看做一個區域，標準值后面的數我們看成一個區域。依次遞歸循環此區域。
//挖坑填補法
int Sort(int arr[],int nLow,int nHigh)
{
int temp ;
temp = arr[nLow]; //保存標準值
while(nLow < nHigh)
{
//從后向前找比標準值小的
while( nLow < nHigh)
{
if(arr[nHigh] > temp)
{
nHigh--;
}
//小的放前面
else
{
arr[nLow] = arr[nHigh];
nLow++;
break;
}
}
//從前往后找比標準值大的
while( nLow < nHigh)
{
if(arr[nLow] < temp)
{
nLow++;
}
//大的放后面
else
{
arr[nHigh] = arr[nLow];
nHigh--;
break;
}
}
}
//填坑
arr[nLow] = temp;
return nLow;
}
void QuickSort(int arr[],int nLow,int nHigh)
{
int nIndex;
if(arr == NULL )return;
if(nLow < nHigh)
{
//找到標準值位置
nIndex = Sort(arr,nLow,nHigh);
//根據標準值將當前數組分割成兩部分
Sort(arr,nLow,nIndex-1);
Sort(arr,nIndex+1,nHigh);
}
}</code></pre>
區間（域）分割法
快排的一種，比挖坑填補法快！類似與挖坑填補法，是其優化升級版吧！
例如，數組：7，5，4，3，6
- 我們選最后一個數6作為標準值，有兩個標記，一個是循環標記I，一個是區域標記s。s= i - 1
s用紅體標記，i用粗斜體標記！s， 7 ，5，4，3，6
- 用數6去和第一個數7比較，比標準值大， 7 , 5 ,4，3，6，則將遍歷元素移動到下一處，比標準值6小，
則將數5和7交換， 5 ， 7 ，4，3，6。
- 將遍歷指針指下一處， 5 ，7， 4 ，3，6，比標準值小，將4和第二個數交換。5， 4 ， 7 ，3，6
移動遍歷指針，5， 4 ，7， 3 ，6
- 比標準值小，將3和第三個數交換。5，4， 3 ， 7 ，6，移動遍歷指針。5，4， 3 ，7， 6
- 這時遍歷結束，判斷++s與i是否相等，若不等，5，4，3， 7 ， 6 ，數組[s]與數組[i]交換。
- 5，4，3， 6 ， 7 ，此時標準值6前小后大，遞歸遍歷！
//區間分割法
int Sort(int arr[],int nLow,int nHigh)
{
int nSmall;//小區間的右邊界
nSmall = nLow-1;
for(nLow;nLow < nHigh;nLow++)
{
//和標準值進行比較
if(arr[nLow] < arr[nHigh])
{
//擴張小區間
if(++nSmall != nLow)
{
arr[nSmall] = arr[nSmall] ^ arr[nLow];
arr[nLow] = arr[nSmall] ^ arr[nLow];
arr[nSmall] = arr[nSmall] ^ arr[nLow];
}
}
}
//標準值放入對應位置
if(++nSmall != nHigh)
{
arr[nSmall] = arr[nHigh] ^ arr[nSmall];
arr[nHigh] = arr[nHigh] ^ arr[nSmall];
arr[nSmall] = arr[nHigh] ^ arr[nSmall];
}
return nSmall;
}
void QuickSort(int arr[],int nLow,int nHigh)
{
int nIndex;
if(arr == NULL )return;
if(nLow < nHigh)
{
//找到標準值位置
nIndex = Sort(arr,nLow,nHigh);
//根據標準值將當前數組分割成兩部分
QuickSort(arr,nLow,nIndex-1);
QuickSort(arr,nIndex+1,nHigh);
}
}</code></pre>
快排區間分割優化
若我們選擇的標準值恰好是最小值或者最大值，這是快排發生交換的次數最多，如果我們在選擇下標的時候進行優化，
我們用隨機數選擇3個下標，之后選其中位數，會最大限度的減少極值下標的可能！
//找中間值下標
int GetIndex(int arr[],int nLow,int nHigh)
{
int a,b,c;
srand(time(NULL));
//隨機出三個在下標范圍之內的下標
a = rand()%(nHigh-nLow+1) + nLow;
b = rand()%(nHigh-nLow+1) + nLow;
c = rand()%(nHigh-nLow+1) + nLow;
//找到三個的中間值
if(arr[a] > arr[b])
{
if(arr[b] > arr[c])
return b;
else
{
if(arr[a] < arr[c])
return a;
else
return c;
}
}
else
{
if(arr[a] > arr[c])
return a;
else
{
if(arr[b] < arr[c])
return b;
else
return c;
}
}
}
//區間分割法
int Sort(int arr[],int nLow,int nHigh)
{
int nSmall;//小區間的右邊界
int nIndex;
nSmall = nLow-1;
//降低標準值是最大最小值得概率
nIndex = GetIndex(arr,nLow,nHigh);
if(nIndex != nHigh)
{
arr[nIndex] = arr[nIndex] ^ arr[nHigh];
arr[nHigh] = arr[nIndex] ^ arr[nHigh];
arr[nIndex] = arr[nIndex] ^ arr[nHigh];
}
for(nLow;nLow < nHigh;nLow++)
{
//和標準值進行比較
if(arr[nLow] < arr[nHigh])
{
//擴張小區間
if(++nSmall != nLow)
{
arr[nSmall] = arr[nSmall] ^ arr[nLow];
arr[nLow] = arr[nSmall] ^ arr[nLow];
arr[nSmall] = arr[nSmall] ^ arr[nLow];
}
}
}
//標準值放入對應位置
if(++nSmall != nHigh)
{
arr[nSmall] = arr[nHigh] ^ arr[nSmall];
arr[nHigh] = arr[nHigh] ^ arr[nSmall];
arr[nSmall] = arr[nHigh] ^ arr[nSmall];
}
return nSmall;
}
void QuickSort(int arr[],int nLow,int nHigh)
{
int nIndex;
if(arr == NULL )return;
if(nLow < nHigh)
{
//找到標準值位置
nIndex = Sort(arr,nLow,nHigh);
//根據標準值將當前數組分割成兩部分
QuickSort(arr,nLow,nIndex-1);
QuickSort(arr,nIndex+1,nHigh);
}
}</code></pre>
快排終極優化
如果數量過少時，直接采用插入排序！
CountSort計數排序
基于 非比較 排序
適用場景：數據分配非常密集的時候！
例如數組：2，1，3，1，2，2，3，4
- 首先在數組中找到最大值和最小值。
- 然后申請一個max-min+1的數組空間。
- 遍歷數組，如第一個數2，就在申請的數組空間下標為2-最小值的位置+1。
相當于在申請的數組第2個位置，計數加一，每次遇到相同的值都加一。
- 相當于在申請的數組空間對應下標對應著參數數組中的值，記錄其出現的次數。
- 遍歷申請的數組空間，對應著下標將值依次存入參數數組。
void CountSort(int arr[],int nLength)
{
int *pCount = NULL;
int i;
int j;
int nMin,nMax;
if(arr == NULL || nLength <=0)return;
//找最大值和最小值
nMax = arr[0];
nMin = arr[0];
for(i = 1;i<nLength;i++)
{
if(arr[i] > nMax)
{
nMax = arr[i];
}
if(arr[i] < nMin)
{
nMin = arr[i];
}
}
//開辟計數數組
pCount = (int *)malloc(sizeof(int ) * (nMax-nMin+1));
memset(pCount,0,sizeof(int ) * (nMax-nMin+1));
//計數
for(i = 0;i<nLength;i++)
{
pCount[arr[i]-nMin]++;
}
//放回原數組
j = 0;
for(i = 0;i< nMax-nMin+1;i++)
{
while(pCount[i] != 0)
{
arr[j] = i+nMin;
j++;
pCount[i]--;
}
}
}</code></pre>
ShellSort希爾排序
插入排序的優化，按步長進行分組，然后在組內進行插入排序，然后在二分法步長，重復此過程。（ps:不一定要二分步長）
使用場景：數據少的時候！
例如：35，5，9，12，21，8，7，4，13，25，21，14，長度，n
- 第一次：$ gap=\displaystyle\frac{n}{2}=6 $，也就是說差6為一組，35和7一組，5和4，9和13，12和25，21和21，8和14。
每組內進行插入排序，所以35和7互換位置，5和3互換位置。數組：7，4，9，12，21，8，33，5，13，25，21，14
- 第二次：$ gap=\displaystyle\frac{gap}{2}=3 $，差3為一組，7，12，33，25一組，4，21，5，21一組，9，8，13，14一組。每組內進行插入排序，25和33換，31和5換。數組：7，4，8，12，5，9，25，21，13，33，21，14
- 第三次：$ gap=\displaystyle\frac{gap}{2}=1 $向下取整。所以直接對整個數組進行一次插入排序。
- 總結：每次進行組內的插入排序，都是為了讓元素距其最終位置更近一步！
void ShellSort(int arr[],int nLength)
{
int gap;
int i; //小組
int j;//插入排序
int k;
int temp;//保存無序數組的第一個
if(arr == NULL || nLength <=0)return;
//定步長
for(gap = nLength/2 ; gap >0 ; gap/=2)
{
//按照步長分組
for(i = 0;i<gap;i++)
{
//各組內部插入排序
for(j = i+gap;j<nLength;j+=gap)
{
k = j - gap; //有序數組的最后一個
temp = arr[j]; //無序數組的第一個
while(arr[k] > temp && k >=i)
{
arr[k +gap] = arr[k];
k-=gap;
}
arr[k+gap] = temp;
}
}
}
}</code></pre>
希爾排序的優化
分組時，讓各組一起進行插入排序，都只進行一次，然后循環進行，代碼看起來簡潔，但是實際耗時基本相同！
void ShellSort2(int arr[],int nLength)
{
int gap;
int i; //小組
int j;//插入排序
int k;
int temp;//保存無序數組的第一個
if(arr == NULL || nLength <=0)return;
//定步長
for(gap = nLength/2 ; gap >0 ; gap/=2)
{
for(i = gap;i<nLength;i++)
{
//各組內部插入排序
k = i - gap; //有序數組的最后一個
temp = arr[i]; //無序數組的第一個
while(arr[k] > temp && k >=0)
{
arr[k +gap] = arr[k];
k-=gap;
}
arr[k+gap] = temp;
}
}
}</code></pre>
MergeSort歸并排序
先拆分再合并。有2路，3路，5路等，這里用2路作為舉例說明。先將數組按照二分法（2路）進行遞歸拆分，
拆分到每個塊里只剩一個元素，然后和相鄰元素進行比較排序合并，在比較在合并。
流程
void Merge(int arr[],int nLow,int nHigh)
{
int nBegin1;
int nEnd1;
int nBegin2;
int nEnd2;
int *pTemp = NULL;
int i;
nBegin1 = nLow;
nEnd1 = (nLow+nHigh)/2;
nBegin2 = nEnd1+1;
nEnd2 = nHigh;
pTemp = (int *)malloc(sizeof(int ) *(nHigh-nLow+1));
//合并
i = 0;
while(nBegin1 <=nEnd1 && nBegin2 <= nEnd2)
{
if(arr[nBegin1] < arr[nBegin2])
{
pTemp[i] = arr[nBegin1];
nBegin1++;
}
else
{
pTemp[i] = arr[nBegin2];
nBegin2++;
}
i++;
}
//將有剩余的數組元素放入臨時數組
while(nBegin1 <= nEnd1)
{
pTemp[i] = arr[nBegin1];
i++;
nBegin1++;
}
while(nBegin2 <= nEnd2)
{
pTemp[i] = arr[nBegin2];
i++;
nBegin2++;
}
//將臨時數組元素放回原數組
for(i = 0;i < nHigh-nLow +1;i++ )
{
arr[i+nLow] = pTemp[i];
}
//釋放
free(pTemp);
pTemp = NULL;
}
void MergeSort(int arr[],int nLow,int nHigh)
{
int nMid;
if(arr == NULL )return;
//兩路歸并
nMid = (nLow + nHigh)/2;
if(nLow < nHigh)
{
//先拆分
MergeSort(arr,nLow,nMid);
MergeSort(arr,nMid+1,nHigh);
//合并
Merge(arr,nLow,nHigh);
}
}</code></pre>
HeapSort堆排序
堆排序是順序儲存，分為大根堆（大堆）和小根堆（小堆）。
大堆：父親結點一定是三個結點最大的！
小堆：父親結點一定是三個結點最小的！
并且左右兒子結點并沒有什么大小順序關系，我們只是把這個順序存儲的結構看作是二叉樹的結構，
我們僅僅是看作二叉樹的形式，實際上也是在數組進行操作，并且根據完全 二叉樹性質(第5條) 來進行排序，對此我們要先掌握二叉樹的基本知識。
適用場景：在n個元素里找前幾個最大的或最小的，我們用堆，并且找大的用小堆，找小的用大堆。
例如：一個數組｛10，2，7，4，6，12，11，9，8｝
- 首先數組按照二叉樹的形勢，我們只是按照二叉樹對應的性質來將數組假想成二叉樹的樣子（并沒有真正的改變數組的結構）。
- 我們按照圖2的方式，從下往上從右往左的調整結點的位置，使其遵循大堆的特點！
- 圖三是我們第一次調整好成大堆的樣子。
- 圖四我們將堆頂和數組最后一個元素對換。
- 然后重新按照前面的步驟調整成大堆，最后我們二叉樹的第一個結點就是最大的數，依次類推。 二叉樹鏈接
堆排序類型題
類型題小結：
- 在一個數組中找出前4個最大的數？
答：首先我們想到的是用小堆，我們建立一個只有四個結點的小堆(圖在下面)，將數組元素一次放入小堆，并調整成小堆，這是用數組第五元素和堆頂元素比較，若比堆頂元素大的話，則把堆頂元素放入小堆，并移走小堆的最后一個元素（左邊最下面），循環完數組小堆里的數就是前4大的！
- 在50億個數里找出前50大？
答：還是用小堆，建50個結點，將數據根據內存容量分流，依次按流通過小堆，每個流里選出前50大的，最后在整合到一起，在選出前50的數？
- 在一個數據流中找到中位數？數據流：一直不間斷提供數據，隨時提供，不是一個固定的數組。
建立一個大堆和小堆，將數據丟入大堆，并且調整大堆，把大堆堆頂扔小堆里，當來數據的時候，調整小堆，把小堆堆頂放大堆里，來數據時，放入大堆并調整大堆，把大堆堆頂放入小堆里。依次循環過程。此時，小堆堆頂是較大數里最小的，大堆堆頂是比較小數里最大的。若數據的個數為奇數時，小堆堆頂是其中位數。當數據的個數為偶數時，小堆堆頂和大堆堆頂的和除2是其中位數。
堆排序代碼
#define nLeft nRootID*2+1
define nRight nRootID*2+2
void Adjust2(int arr[],int nLength,int nRootID)
{
int nMax;
//在有孩子的情況下 假設左孩子是大的
for(nMax = nLeft;nLeft < nLength;nMax = nLeft /*下一次繼續假設左孩子是最大的8*/)
{
//兩個孩子
if(nRight < nLength)
{
//右孩子大
if(arr[nMax] < arr[nRight])
{
nMax = nRight;
}
}
//大的 和父親比較 大 則交換
if(arr[nMax] > arr[nRootID])
{
arr[nMax] = arr[nRootID] ^ arr[nMax];
arr[nRootID] = arr[nRootID] ^ arr[nMax];
arr[nMax] = arr[nRootID] ^ arr[nMax];
nRootID = nMax;
}
else
{
break;
}
}
}
void HeapSort(int arr[],int nLength)
{
int i;
if(arr == NULL || nLength <=0)return;
//建初始堆
for(i = nLength/2-1;i>=0;i--)
{
Adjust2(arr,nLength,i);
}
//排序
for(i = nLength-1;i>0;i--)
{
//最大值放后面
arr[i] = arr[i] ^ arr[0];
arr[0] = arr[i] ^ arr[0];
arr[i] = arr[i] ^ arr[0];
//調整根節點
Adjust2(arr,i,0);
}
}</code></pre>
來自：http://www.jianshu.com/p/a1bfc6114022