-
排序算法
鎖定
- 中文名
- 排序算法
- 外文名
- Sorting algorithm
- 分 類
- 計算機算法
- 應用語言
- c＋＋等
- 優 點
- 節省時間，簡化計算
排序算法內容簡介
所謂排序算法，即通過特定的算法因式將一組或多組數據按照既定模式進行重新排序。這種新序列遵循着一定的規則，體現出一定的規律，因此，經處理後的數據便於篩選和計算，大大提高了計算效率。對於排序，我們首先要求其具有一定的穩定性，即當兩個相同的元素同時出現於某個序列之中，則經過一定的排序算法之後，兩者在排序前後的相對位置不發生變化。換言之，即便是兩個完全相同的元素，它們在排序過程中也是各有區別的，不允許混淆不清。
[1]
排序算法分類
排序就是把集合中的元素按照一定的次序排序在一起。一般來説有升序排列和降序排列2種排序，在算法中有8中基本排序：
(1)冒泡排序；
(2)選擇排序；
(3)插入排序；
(4)希爾排序；
(5)歸併排序；
(6)快速排序；
(7)基數排序；
(8)堆排序；
(9)計數排序；
(10)桶排序。
排序算法評價標準
穩定性是一個特別重要的評估標準。穩定的算法在排序的過程中不會改變元素彼此的位置的相對次序，反之不穩定的排序算法經常會改變這個次序，這是我們不願意看到的。我們在使用排序算法或者選擇排序算法時，更希望這個次序不會改變，更加穩定，所以排序算法的穩定性，是一個特別重要的參數衡量指標依據。就如同空間複雜度和時間複雜度一樣，有時候甚至比時間複雜度、空間複雜度更重要一些。所以往往評價一個排序算法的好壞往往可以從下邊幾個方面入手：
（1）時間複雜度：即從序列的初始狀態到經過排序算法的變換移位等操作變到最終排序好的結果狀態的過程所花費的時間度量。
（2）空間複雜度：就是從序列的初始狀態經過排序移位變換的過程一直到最終的狀態所花費的空間開銷。
（3）使用場景：排序算法有很多，不同種類的排序算法適合不同種類的情景，可能有時候需要節省空間對時間要求沒那麼多，反之，有時候則是希望多考慮一些時間，對空間要求沒那麼高，總之一般都會必須從某一方面做出抉擇。
（4）穩定性：穩定性是不管考慮時間和空間必須要考慮的問題，往往也是非常重要的影響選擇的因素。
[2]
排序算法常見排序算法
排序算法插入排序
插入排序算法是基於某序列已經有序排列的情況下，通過一次插入一個元素的方式按照原有排序方式增加元素。這種比較是從該有序序列的最末端開始執行，即要插入序列中的元素最先和有序序列中最大的元素比較，若其大於該最大元素，則可直接插入最大元素的後面即可，否則再向前一位比較查找直至找到應該插入的位置為止。插入排序的基本思想是，每次將1個待排序的記錄按其關鍵字大小插入到前面已經排好序的子序列中，尋找最適當的位置，直至全部記錄插入完畢。執行過程中，若遇到和插入元素相等的位置，則將要插人的元素放在該相等元素的後面，因此插入該元素後並未改變原序列的前後順序。我們認為插入排序也是一種穩定的排序方法。插入排序分直接插入排序、折半插入排序和希爾排序3類。
[1]
排序算法冒泡排序
冒泡排序算法是把較小的元素往前調或者把較大的元素往後調。這種方法主要是通過對相鄰兩個元素進行大小的比較，根據比較結果和算法規則對該二元素的位置進行交換，這樣逐個依次進行比較和交換，就能達到排序目的。冒泡排序的基本思想是，首先將第1個和第2個記錄的關鍵字比較大小，如果是逆序的，就將這兩個記錄進行交換，再對第2個和第3個記錄的關鍵字進行比較，依次類推，重複進行上述計算，直至完成第(n一1)個和第n個記錄的關鍵字之間的比較，此後，再按照上述過程進行第2次、第3次排序，直至整個序列有序為止。排序過程中要特別注意的是，當相鄰兩個元素大小一致時，這一步操作就不需要交換位置，因此也説明冒泡排序是一種嚴格的穩定排序算法，它不改變序列中相同元素之間的相對位置關係。
[1]
排序算法選擇排序
選擇排序算法的基本思路是為每一個位置選擇當前最小的元素。選擇排序的基本思想是，基於直接選擇排序和堆排序這兩種基本的簡單排序方法。首先從第1個位置開始對全部元素進行選擇，選出全部元素中最小的給該位置，再對第2個位置進行選擇，在剩餘元素中選擇最小的給該位置即可；以此類推，重複進行“最小元素”的選擇，直至完成第(n-1)個位置的元素選擇，則第n個位置就只剩唯一的最大元素，此時不需再進行選擇。使用這種排序時，要注意其中一個不同於冒泡法的細節。舉例説明：序列58539．我們知道第一遍選擇第1個元素“5”會和元素“3”交換，那麼原序列中的兩個相同元素“5”之間的前後相對順序就發生了改變。因此，我們説選擇排序不是穩定的排序算法，它在計算過程中會破壞穩定性。
[1]
排序算法快速排序
快速排序的基本思想是:通過一趟排序算法把所需要排序的序列的元素分割成兩大塊，其中，一部分的元素都要小於或等於另外一部分的序列元素，然後仍根據該種方法對劃分後的這兩塊序列的元素分別再次實行快速排序算法，排序實現的整個過程可以是遞歸的來進行調用，最終能夠實現將所需排序的無序序列元素變為一個有序的序列。
[3]
排序算法歸併排序
歸併排序算法就是把序列遞歸劃分成為一個個短序列，以其中只有1個元素的直接序列或者只有2個元素的序列作為短序列的遞歸出口，再將全部有序的短序列按照一定的規則進行排序為長序列。歸併排序融合了分治策略，即將含有n個記錄的初始序列中的每個記錄均視為長度為1的子序列，再將這n個子序列兩兩合併得到n/2個長度為2(當凡為奇數時會出現長度為l的情況)的有序子序列；將上述步驟重複操作，直至得到1個長度為n的有序長序列。需要注意的是，在進行元素比較和交換時，若兩個元素大小相等則不必刻意交換位置，因此該算法不會破壞序列的穩定性，即歸併排序也是穩定的排序算法。
[1]
排序算法C 語言代碼實現
排序算法冒泡排序
#include <stdio.h>
#include <stdlib.h>
int main() {
int a[]= {12,4,132,55,46,232,789,1,0,98,523,666};//隨機數組
int n = sizeof(a)/sizeof(a[0]);//獲取數組大小
int i,j,k;
//比較相鄰的兩個數據，如果第二個數小，就交換位置。從後向前兩兩比較，一直到比較最前兩個數據。
for(i = 1; i < n; i ++) {
for(j = 0; j < n-1; j ++) {
if(a[j] > a[j+1]) {//從小到大排序
k = a[j];
a[j] = a[j+1];
a[j+1] = k;
}
}
}
for(i = 0; i < n; i ++)//輸出排序後的結果
printf("%d ",a[i]);
return 0;
}
//運行結果如下：
//0 1 4 12 46 55 98 132 232 523 666 789
排序算法選擇排序
#include <stdio.h>
#include <stdlib.h>
int main() {
int a[]= {12,4,132,55,46,232,789,1,0,98,523,666};//隨機數組
int n = sizeof(a)/sizeof(a[0]);//獲取數組大小
int i,j,k;
//第一次遍歷n-1個數，找到最小的數值與第一個元素交換
//第二次遍歷n-2個數，找到最小的數值與第二個元素交換
// 以此類推
//第n-1次遍歷，找到最小的數值與第n-1個元素交換，排序完成。
for(i = 0; i < n-1; i ++) {
for(j = i+1; j < n; j ++) {
if(a[i] > a[j]) {//從小到大排序
k = a[i];
a[i] = a[j];
a[j] = k;
}
}
}
for(i = 0; i < n; i ++)//輸出排序後的結果
printf("%d ",a[i]);
return 0;
}
//運行結果如下：
//0 1 4 12 46 55 98 132 232 523 666 789
排序算法插入排序
#include <stdio.h>
#include <stdlib.h>
int main() {
int a[]= {12,4,132,55,46,232,789,1,0,98,523,666};//隨機數組
int n = sizeof(a)/sizeof(a[0]);//獲取數組大小
int i,j,k;
//在要排序的一組數中，假定前n-1個數已經排好序，現將第n個數插到前面的有序數列中，
//使得這n個數也是排好順序的。如此反覆循環，直到全部排好順序。
for(i = 0; i < n-1; i ++) {
for(j = i+1; j > 0; j --)
if(a[j] < a[j-1]) {
k = a[j-1];
a[j-1] = a[j];
a[j] = k;
} else
break;
}
for(i = 0; i < n; i ++)//輸出排序後的結果
printf("%d ",a[i]);
return 0;
}
//運行結果如下：
//0 1 4 12 46 55 98 132 232 523 666 789
排序算法快速排序
#include <stdio.h>
#include <stdlib.h>
//先從數列中取出一個數作為key值
//將比這個數小的數全部放在它的左邊，大於或等於它的數全部放在它的右邊
//對左右兩個小數列重複第二步，直至各區間只有1個數。
void quickSort(int a[],int l,int r) {
if(l>=r)
return;
int i = l;
int j = r;
int key = a[l];//選擇第一個數為key
while(i<j) {
while(i<j && a[j]>=key)//從右向左找第一個小於key的值
j--;
if(i<j) {
a[i] = a[j];
i++;
}
while(i<j && a[i]<key)//從左向右找第一個大於key的值
i++;
if(i<j) {
a[j] = a[i];
j--;
}
}
a[i] = key;
quickSort(a, l, i-1);//繼續排左部分，遞歸調用
quickSort(a, i+1, r);//繼續排右部分，遞歸調用
}
int main() {
int a[]= {12,4,132,55,46,232,789,1,0,98,523,666};//隨機數組
int i,n = sizeof(a)/sizeof(a[0]);//獲取數組大小
quickSort(a,0,n-1);//快速排序函數入口
for(i = 0; i < n; i ++)//輸出排序後的結果
printf("%d ",a[i]);
return 0;
}
//運行結果如下：
//0 1 4 12 46 55 98 132 232 523 666 789
排序算法堆排序
#include <stdio.h>
#include <stdlib.h>
int arr[]= {12,4,132,55,46,232,789,1,0,98,523,666};//隨機數組
int n = sizeof(arr)/sizeof(arr[0]);//獲取數組大小
void adjustHeap(int i, int lef) {
int temp=arr[i];
for(int k=i*2+1; k<lef; k=k*2+1) { //從i結點的左子結點開始，也就是2i+1處開始
if(k+1<lef&&arr[k]<arr[k+1]) {
k++;
}
if(arr[k]>temp) { //如果子節點大於父節點，將子節點值賦給父節點（不用進行交換）
arr[i]=arr[k];
i=k;
} else {
break;
}
}
arr[i]=temp;//將temp值放到最終的位置
}
void swap(int a, int b) {
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
void heapsort() {
// 1、構建大頂堆
for(int i = n/2-1; i>=0; i--) {
//從第一個非葉子節點從下至上，從右至左調整結構
adjustHeap(i,n);
}
//2、調整堆結構+交換堆頂元素與末尾元素
for(int j=n-1; j>0; j--) {
swap(0,j);//將堆頂元素與末尾元素進行交換
adjustHeap(0, j);//重新對堆進行調整
}
}
int main() {
int i;
heapsort();
for(i = 0; i < n; i ++)
printf("%d ",arr[i]);
return 0;
}
//運行結果如下：
//0 1 4 12 46 55 98 132 232 523 666 789
