常用排序算法總結
概述
在計算機科學中端铛，排序算法是一種重要的操作理澎。合理的排序算法能夠大幅度提高計算機處理數(shù)據(jù)的性能。排序有內部排序和外部排序揩环，內部排序是數(shù)據(jù)記錄在內存中進行排序斜纪，而外部排序是因排序的數(shù)據(jù)很大，一次不能容納全部的排序記錄文兑，在排序過程中需要訪問外存盒刚。我們這里說說八大排序就是內部排序。
1.插入排序
1.1直接插入排序
算法思想
直接插入排序是一種簡單的排序算法绿贞，由 n-1 趟排序組成因块。第 p 趟排序后保證第 0 個位置到第 p 個位置上的元素為有序狀態(tài)。第 p+1 趟排序將第 p+2 個元素插入到前面 p+1個元素的有序表中籍铁。下圖顯示了直接插入排序算法的每一趟的排序情況涡上。
| 初始數(shù)據(jù)序列 | 32??18 ??65??48??27??9 |
|---|---|
| 第1趟排序之后 | 18??32??65??48??27??9 |
| 第2趟排序之后 | 18??32??65??48??27??9 |
| 第3趟排序之后 | 18??32??48??65??27??9 |
| 第4趟排序之后 | 18??27??32??48??65??9 |
| 第5趟排序之后 | 9??18??27??32??48??65 |
代碼實現(xiàn)
void DirectInsertSort(int *array,int n){
int p ,i;
for(p = 1;p<n;p++){
int temp = array[p];
i = p-1;
while(i>=0&&array[i]>temp){
array[i+1] = array[i];
i--;
}
array[i+1] = temp;
}
}
復雜度分析
直接插入排序算法主要應用比較和移動兩種操作，從空間上來看拒名，它只需要一個元素的輔助空間吩愧，用于位置的交換，有些教材也將這類排序算法稱為原地(In Place)排序算法增显。
從時間上分析雁佳，首先外層循環(huán)要進行 n-1 次，但每一趟插入排序的比較和移動的次數(shù)并不相同同云。第 p 趟插入時最好的情況時數(shù)據(jù)已經排好序糖权，每趟插入進行一次比較，兩次移動炸站；最壞的情況時比較 p 次星澳，移動 p+2 次，(逆序）（p = 1旱易，2禁偎，...,n-1)腿堤。記 M 為執(zhí)行一次排序算法移動的次數(shù)，C 為比較次數(shù)届垫，則：
??C min = n-1;
??M min = 2(n-1);
??C max = 1+2+...+(n-1),
??M max = 3+4+...+(n+1) = (n^2+3n-4)/2;
假設數(shù)據(jù)元素在各個位置的概率相等释液，即 1/n ，則平均的比較次數(shù)和移動次數(shù)為：
C ave = (n^2+n-2)/4,??M ave = (n^2+5n-6)/4;
因此装处，直接插入排序算法的時間復雜度是 O(n^2)误债。對于隨機順序的數(shù)據(jù)來說，移動和比較的次數(shù)接近最壞情況妄迁。
由于直接插入算法的元素移動是順序的寝蹈，該算法是穩(wěn)定的。
1.2折半插入排序
算法思想
直接插入排序算法是利用有序表的插入操作來實現(xiàn)對數(shù)據(jù)集合的排序登淘。在進行第 p+1 趟插入排序時箫老，需要在前面的有序序列 data[0],data[1],...data[p] 中找到 data[p+1] 第對應位置 i ，同時將 data[i],data[i+1],...data[p] 都向后移動一個位置黔州。由于有序表是排好序的耍鬓，故可以用折半查找（二分法）操作來確定 data[p+1] 的位置，這就是折半插入算法的思想流妻。
代碼實現(xiàn)
void HalfInsertSort(int *array,int n){
int left,right,middle,p;
for(p = 1;p<n;p++){
int temp = array[p];
left = 0;right = p-1;
while (left<=right) {
middle = (left+right)/2;
if(array[middle]>temp)
right = middle-1;
else
left = middle+1;
}
for(int i = p-1;i>=left;i--){
array[i+1] = array[i];
array[left] = temp;
}
}
}
復雜度分析
折半插入排序算法與直接插入算法相比牲蜀，需要的輔助空間與直接插入排序算法基本一致，時間上绅这，折半插入的比較次數(shù)比直接插入的最壞情況號涣达，最好情況下，時間復雜度為 O(n log2 n);折半插入算法的元素移動與直接插入相同证薇，復雜度為 O(n^2)度苔。
折半插入和直接插入算法的元素移動一樣是順序的，因此該排序算法也是穩(wěn)定的浑度。
1.3 希爾(shell)排序
算法思想
希爾排序的基本思想是寇窑，先將待排序的數(shù)據(jù)序列劃分成若干子序列，分別進行直接插入排序：待整個序列中的數(shù)據(jù)基本有序后箩张，再對全部的數(shù)據(jù)進行一次直接插入排序疗认。
對于子序列可以采用任意簡單的排序算法。
例如伏钠，對于序列 {65,34,25,87,12,38,56,46,14,77,92,23},可以劃分成如下 6 個子序列横漏。
如果初始序列是 array[0],?array[1],?array[2], ... ?array[n-1],?子序列間隔為 d ，則子序列可以描述為 ?array[i],?array[i+d],?array[i+2*d], ...?array[i+k*d],（其中 0<=i<d,i+k*d<n)熟掂。希爾排序中通過不斷地縮小增量缎浇，來將原始序列分成若干個子序列。例如赴肚，增量初始的時候可以選為待排序的元素個數(shù)的一半素跺，即 n/2 的向下取整二蓝，在后來的迭代過程中不斷縮小增量，下一次的增量為上一次的一半，即第二趟的選擇增量為 n/4 的向下取整，以此類推吃粒，知道增量變?yōu)?1 為止蛇摸。這時序列已經基本有序荐虐，對整個序列進行一次插入排序即可完成數(shù)據(jù)排序。
希爾排序算法流程
代碼實現(xiàn)
void ShellSort(int *array,int n){
int d = n/2;
while(d>=1){
for(int k = 0;k<d;k++){
for(int i = k+d;i<n;i++){
int temp = array[i];
int j = i-d;
while(j>=k&&array[j]>temp){
array[j+d] = array[j];
j -=d;
}
array[j+d] = temp;
}
}
d = d/2;
}
}
復雜度分析
希爾排序算法依賴于增量序列的選擇，時間復雜度在 O(nlog2n) 和 O(n^2) 之間，大致為 O(n^1.3) 和直接插入排序算法相比牡借，減少了算法復雜度。
希爾排序算法是不穩(wěn)定的袭异。
2.交換排序
2.1冒泡排序
2.1.1簡單冒泡排序
算法思想
以升序排序（不減排序）算法為例
冒泡排序算法一共要進行 n-1 趟排序钠龙，每一趟排序都要將待排序序列中最大的元素擠到最后。
第一趟：將第一個元素與第二個元素比較御铃，若為逆序碴里，則交換；然后比較第二個元素和第三個元素上真，若為逆序咬腋，則交換；以此類推谷羞，直到第 n-1 個元素和第 n 個元素比較，若為逆序溜徙，則交換湃缎，這樣，經過第一趟排序蠢壹，最大的元素被移動到了序列的最后嗓违。
第二趟排序，由于最大的元素已經在最右端了图贸，因此只需要對記錄{a[0],a[1],...a[n-1]}進行上述排序過程就可以了蹂季。
以此類推，進行 n-1 趟掃描疏日。
代碼實現(xiàn)
void bubbleSort(char *a,int n){
char tmp;
int i,j;
for(i = 0;i<n-1;i++){
for(j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
}
}
}
}
復雜度分析
這種冒泡排序算法直觀偿洁、簡便。但時間復雜度長沟优。
對任何序列涕滋，都需要進行 n-1 趟掃描，第 i 趟需要進行 n-i 次元素比較挠阁。造成了時間上的浪費宾肺。因此溯饵，大部分情況，我們都會選擇改進的冒泡排序锨用。
2.1.2改進的冒泡排序
算法思想
通過對每一趟排序進行監(jiān)控丰刊，若中間某一趟排序過程中數(shù)沒有進行交換，則說明序列已經排好增拥，此時跳出循環(huán)即可
代碼實現(xiàn)
void bubbleSort(char *a,int n){
char tmp;
int i,j;
for(i = 0;i<n-1;i++){
int flag=0;
for(j=0;j<n-i-1;j++){
if(a[j]>a[j+1]){
tmp = a[j];
a[j] = a[j+1];
a[j+1] = tmp;
flag=1;
}
}
if(flag==0)break;
}
}
復雜度分析
顯然啄巧，改進的冒泡排序算法的效率和待排序的初始順序密切相關。若待排序的元素是正序跪者，則是最好情況棵帽，此時只需要進行一趟排序，比較次數(shù)為 n-1 次渣玲，移動元素次數(shù)為 0 次逗概；若初始待排序列為逆序，則是最壞情況忘衍，此時需要執(zhí)行 n-1 趟排序逾苫，第 i 趟做了 n-i 次比較，執(zhí)行 3(n-i) 次元素交換
所以最壞情況時間復雜度為 O(n^2).平均時間復雜度也是 O(n^2) 枚钓。
由于冒泡排序算法只是進行元素間的順序移動铅搓，所以是穩(wěn)定的算法。
2.2快速排序
- 分割：取序列的一個元素作為軸元素搀捷，利用這個軸元素星掰，把序列分成三段，使所有小于等于軸元素的元素放在軸的左邊嫩舟，大于軸的元素放在軸的右邊氢烘。此時，軸元素已經被放到的正確的位置家厌。
- 分治：對左段和右段中的元素遞歸調用（1）中的過程播玖，分別對左端=段和右段中的元素進行排序。
- 此時饭于，排序完成
一般情況下蜀踏，我們采用左邊第一個元素作為軸元素的方法。
分割策略1
算法思想
首先用一個臨時變量對首元素進行備份掰吕，取兩個指針 left 和 right 果覆，他們的初始值分別是待排序列的兩端的下標，其中 left 指向最左邊殖熟，right 指向最右邊随静。在整個排序過程中保證 left 不大于 right ，用下面的方法不斷移動兩個指針:
- 從 right 的位置向左搜索，找到第一個小于或等于軸的元素燎猛，移動到 left 的位置恋捆。
- 再從 left 所指的位置向右搜索，找到第一個大于軸的元素重绷，移動到 right 所指的位置沸停。
- 重復上面的過程，直到 left = right 昭卓，最后把軸元素放在 left 所指的位置愤钾。
經過上面的過程，所有大于軸的元素放在了軸的右邊候醒，小于軸的元素放在了軸的左邊能颁。
代碼實現(xiàn)
int Partition(int *array,int left,int right){
int pivot = array[left];
while(left<right){
while (left<right&&array[right]>pivot) {
right--;
}
array[left] = array[right];
while (left<right&&array[left]<=pivot) {
left++;
}
array[right] = array[left];
}
array[left] = pivot;
return left;
}
分割策略2
算法思想
分別從待排序序列兩端相向掃描，從左邊找到第一個大于軸的元素倒淫，從右邊找到第一個小于軸的元素伙菊，然后交換二者。
然后把軸元素和 right 所指的元素交換敌土。
代碼實現(xiàn)
int Partition(int *array,int start,int end){
int pivot = array[start];
int left = start,right = end;
while (left<=right) {
while (left<=right&&array[left]<=pivot) {
left++;
}
while (right>=left&&array[right]>pivot) {
right--;
}
if(left<right){
swap(array[right], array[left]);
left++;right--;
}
}
swap(array[start], array[right]);
return right;
}
分治
代碼實現(xiàn)
void QuickSort(int *array,int left,int right){
if(left<right){
int p = Partition(array, left, right);
QuickSort(array, left, p-1);
QuickSort(array, p+1, right);
}
}
復雜度分析
最好空間復雜度為 O(log n)镜硕， 最壞的空間復雜度為 O(n)。
3.選擇排序
3.1簡單選擇排序
算法思想
簡單選擇排序算法是利用線性查找的方法從一個序列中找到最小的元素返干，即地 i 趟的排序操作為：通過 n-i 次關鍵字的比較兴枯，從 n-i+1 個元素中選出最小的元素，并和第 i-1 個元素交換矩欠。簡單選擇排序算法也稱為直接選擇排序算法财剖。
代碼實現(xiàn)
void SelectionSort(char*num,int n){
char tmp;
for(int i = 0;i<n-1;i++){
int min = i;
for(int j = i;j<n;j++){
if(num[min]>num[j]){
min = j;
}
}
if(min!=i){
tmp = num[i];
num[i] = num[min];
num[min] = tmp;
}
}
}
復雜度分析
簡單選擇排序算法需要進行 n-1 趟操作，而且第 i 趟選擇要進行 n-i 次比較癌淮，最多執(zhí)行 1 次數(shù)據(jù)交換躺坟，最少進行 0 次，因此簡單選擇排序算法的時間效率是 O(n^2) 该默。簡單選擇排序算法比較次數(shù)較多瞳氓，而移動次數(shù)較少策彤∷ㄐ洌空間開銷中，由于只需要使用一個臨時變量來記錄最小位置店诗，因此空間負責度為 O(1) 裹刮。簡單選擇排序算法是不穩(wěn)定的排序算法。
3.2堆排序
算法思想
以降序排序為例庞瘸。
- 將初始序列初始化為一個最大堆捧弃，初始化當前待排序列元素的個數(shù) n 。
- 將堆頂元素和當前最后一個元素交換，n = n-1;
- 調整堆結構
- 如果當前待排序列元素個數(shù) n>1 則重復步驟 2）违霞，3）嘴办。
代碼實現(xiàn)
void SiftDown(int *array,int i,int n){
int left = 2*i+1,right = 2*i+2,min = i;
if(left<n&&array[min]<array[left]){
min = left;
}
if(right<n&&array[min]<array[right]){
min = right;
}
if(min!=i){
int t = array[min];
array[min] = array[i];
array[i] = t;
SiftDown(array, min, n);
}
}
void BuildHeap(int *array,int n){
int p = n/2-1;
for(int i = p;i>=0;i--){
SiftDown(array, i, n);
}
}
void HeapSort(int *array,int n){
BuildHeap(array,n);
for(int i = n-1;i>0;i--){
int t = array[0];
array[0] = array[i];
array[i] = t;
SiftDown(array, 0, i);
}
}
復雜度分析
對于調整最大堆的操作 SiftDown 來說，最多執(zhí)行 O(log2n) 次數(shù)據(jù)元素的交換买鸽，初始化堆的時間復雜度為 O(n) 涧郊。堆排序中一共調用了 n-1 次 SiftDown 操作。以及一次初始化操作眼五，所以堆排序的時間復雜度為 O(log2n) 妆艘。排序過程中只需要，臨時變量來進行交換操作看幼，故空間開銷為 O(1) 批旺。堆排序算法是不穩(wěn)定的算法。當數(shù)據(jù)量較大的時候堆排序的效率體現(xiàn)得很明顯诵姜，在小數(shù)據(jù)集上汽煮，堆排序算法的優(yōu)勢并不明顯。
4.基數(shù)排序
算法思想
代碼實現(xiàn)
//MergeSort
//array是待歸并數(shù)組茅诱，
//其中對 array[start,mid] 和 array[mid+1,end]
//之間的數(shù)據(jù)進行合并
void Merge(int *array,int start,int mid,int end){
int len1 = mid-start+1;
int len2 = end-mid;
int i,j,k;
int *left = new int[len1];//臨時用數(shù)組來存放 array[start,mid]的數(shù)據(jù)
int *right = new int[len2];//臨時用數(shù)組來存放 array[mid+1,end]
for(i = 0;i<len1;i++){
left[i] = array[i+start];
}
for(i = 0;i<len2;i++){
right[i] = array[i+mid+1];
}
i = 0;j = 0;//執(zhí)行歸并
for(k = start;k<=end;k++){
if(i==len1 || j==len2){
break;
}
if(left[i]<=right[j]){
array[k] = left[i++];
}
else{
array[k] = right[j++];
}
}
while (i<len1) {
array[k++] = left[i++];
}
while (j<len2) {
array[k++] = right[j++];
}
delete [] left;
delete [] right;
}
void MergeSort(int *array,int start,int end){
if(start<end){
int mid = (start+end)/2;
MergeSort(array, start, mid);
MergeSort(array, mid+1, end);
Merge(array, start, mid, end);
}
}
復雜度分析
5.歸并排序
###### 算法思想
###### 代碼實現(xiàn)
//基數(shù)排序
int getMaxBit(int *array,int n){//得到元素序列中最大數(shù)的位數(shù)
int max = 1;
int k = 10;
for(int i = 0;i<n;i++){
while(array[i]>=k){
k*=10;
max++;
}
}
return max;
}
void RadixSort(int *array,int size)
{
int n;
int max = getMaxBit(array, size);
int maxNum = 1;
for(int i = 1;i<max;i++){
maxNum *=10;
}
for(int i=1;i<=maxNum;i=i*10)
{
int tmp[15][10]={0};//分配操作:建立一個15行逗物，10列的數(shù)組，每一列分別代表0~9位數(shù)瑟俭，15行代表能存放的總個數(shù)
for(int j=0;j<size;j++)
{
n=(array[j]/i)%10;
tmp[j][n]=array[j];
}
int k=0;//收集操作：將二維數(shù)組中的數(shù)據(jù)自左至右翎卓、自上至下收集到數(shù)組中
for(int p=0;p<10;p++)
for(int q=0;q<size;q++)
{
if(tmp[q][p]!=0)
array[k++]=tmp[q][p];
}
}
}
