常見(jiàn)排序算法分類(lèi)
本文將通過(guò)動(dòng)態(tài)演示+代碼的形式系統(tǒng)地總結(jié)十大經(jīng)典排序算法。
排序算法
算法分類(lèi) —— 十種常見(jiàn)排序算法可以分為兩大類(lèi)：
- 比較類(lèi)排序：通過(guò)比較來(lái)決定元素間的相對(duì)次序，由于其時(shí)間復(fù)雜度不能突破O(nlogn)，因此也稱(chēng)為非線(xiàn)性時(shí)間比較類(lèi)排序。
- 非比較類(lèi)排序：不通過(guò)比較來(lái)決定元素間的相對(duì)次序，它可以突破基于比較排序的時(shí)間下界，以線(xiàn)性時(shí)間運(yùn)行，因此也稱(chēng)為線(xiàn)性時(shí)間非比較類(lèi)排序。
算法復(fù)雜度
| 排序算法 | 平均時(shí)間復(fù)雜度 | 最差時(shí)間復(fù)雜度 | 空間復(fù)雜度 | 數(shù)據(jù)對(duì)象穩(wěn)定性 |
|---|---|---|---|---|
| 冒泡排序 | O(n2) | O(n2) | O(1) | 穩(wěn)定 |
| 選擇排序 | O(n2) | O(n2) | O(1) | 數(shù)組不穩(wěn)定、鏈表穩(wěn)定 |
| 插入排序 | O(n2) | O(n2) | O(1) | 穩(wěn)定 |
| 快速排序 | O(n*log2n) | O(n2) | O(log2n) | 不穩(wěn)定 |
| 堆排序 | O(n*log2n) | O(n*log2n) | O(1) | 不穩(wěn)定 |
| 歸并排序 | O(n*log2n) | O(n*log2n) | O(n) | 穩(wěn)定 |
| 希爾排序 | O(n*log2n) | O(n2) | O(1) | 不穩(wěn)定 |
| 計(jì)數(shù)排序 | O(n+m) | O(n+m) | O(n+m) | 穩(wěn)定 |
| 桶排序 | O(n) | O(n) | O(m) | 穩(wěn)定 |
| 基數(shù)排序 | O(k*n) | O(n2) | 穩(wěn)定 |
1. 冒泡排序
算法思想：
- （1）比較相鄰的元素。如果第一個(gè)比第二個(gè)大，就交換它們兩個(gè)；
- （2）對(duì)每一對(duì)相鄰元素作同樣的工作，從開(kāi)始第一對(duì)到結(jié)尾的最后一對(duì)，這樣在最后的元素應(yīng)該會(huì)是最大的數(shù)；
- （3）針對(duì)所有的元素重復(fù)以上的步驟，除了最后一個(gè)；
- （4）重復(fù)步驟1~3，直到排序完成。
代碼：
void bubbleSort(int a[], int n)
{
for(int i =0 ; i< n-1; ++i)
{
for(int j = 0; j < n-i-1; ++j)
{
if(a[j] > a[j+1])
{
int tmp = a[j] ; //交換
a[j] = a[j+1] ;
a[j+1] = tmp;
}
}
}
}
2. 選擇排序
算法思想：
- （1）在未排序序列中找到最小（大）元素，存放到排序序列的起始位置；
- （2）從剩余未排序元素中繼續(xù)尋找最小（大）元素，然后放到已排序序列的末；
- （3）以此類(lèi)推，直到所有元素均排序完畢；
代碼：
void selectionSort(int arr[], int n) {
int minIndex, temp;
for (int i = 0; i < n - 1; i++) {
minIndex = i;
for (var j = i + 1; j < n; j++) {
if (arr[j] < arr[minIndex]) { // 尋找最小的數(shù)
minIndex = j; // 將最小數(shù)的索引保存
}
}
temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
for (int k = 0; i < n; i++) {
printf("%d ", arr[k]);
}
}
3. 插入排序
算法思想：
- （1）從第一個(gè)元素開(kāi)始，該元素可以認(rèn)為已經(jīng)被排序；
- （2）取出下一個(gè)元素，在已經(jīng)排序的元素序列中從后向前掃描；
- （3）如果該元素（已排序）大于新元素，將該元素移到下一位置；
- （4）重復(fù)步驟3，直到找到已排序的元素小于或者等于新元素的位置；
- （5）將新元素插入到該位置后；
- （6）重復(fù)步驟2~5。
代碼：
void print(int a[], int n ,int i){
cout< ":";
for(int j= 0; j< 8; j++){
cout< " ";
}
cout<
算法分析：插入排序在實(shí)現(xiàn)上，通常采用in-place排序（即只需用到O(1)的額外空間的排序），因而在從后向前掃描過(guò)程中，需要反復(fù)把已排序元素逐步向后挪位，為最新元素提供插入空間。
4. 快速排序
快速排序的基本思想是通過(guò)一趟排序?qū)⒋庞涗浄指舫瑟?dú)立的兩部分，其中一部分記錄的關(guān)鍵字均比另一部分的關(guān)鍵字小，則可分別對(duì)這兩部分記錄繼續(xù)進(jìn)行排序，以達(dá)到整個(gè)序列有序。
算法思想：
- （1）選取第一個(gè)數(shù)為基準(zhǔn)
- （2）將比基準(zhǔn)小的數(shù)交換到前面，比基準(zhǔn)大的數(shù)交換到后面
- （3）遞歸地（recursive）把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序
代碼：
void QuickSort(vector< int >& v, int low, int high) {
if (low >= high) // 結(jié)束標(biāo)志
return;
int first = low; // 低位下標(biāo)
int last = high; // 高位下標(biāo)
int key = v[first]; // 設(shè)第一個(gè)為基準(zhǔn)
while (first < last)
{
// 將比第一個(gè)小的移到前面
while (first < last && v[last] >= key)
last--;
if (first < last)
v[first++] = v[last];
// 將比第一個(gè)大的移到后面
while (first < last && v[first] <= key)
first++;
if (first < last)
v[last--] = v[first];
}
//
v[first] = key;
// 前半遞歸
QuickSort(v, low, first - 1);
// 后半遞歸
QuickSort(v, first + 1, high);
}
5. 堆排序
堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿(mǎn)足堆積的性質(zhì)：即子節(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。
算法思想：
- （1）將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)序區(qū)；
- （2）將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無(wú)序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿(mǎn)足R[1,2…n-1]<=R[n]；
- （3）由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無(wú)序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無(wú)序區(qū)最后一個(gè)元素交換，得到新的無(wú)序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過(guò)程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過(guò)程完成。
代碼：
#include
#include
using namespace std;
// 堆排序：（最大堆，有序區(qū)）。從堆頂把根卸出來(lái)放在有序區(qū)之前，再恢復(fù)堆。
void max_heapify(int arr[], int start, int end) {
//建立父節(jié)點(diǎn)指標(biāo)和子節(jié)點(diǎn)指標(biāo)
int dad = start;
int son = dad * 2 + 1;
while (son <= end) { //若子節(jié)點(diǎn)在范圍內(nèi)才做比較
if (son + 1 <= end && arr[son] < arr[son + 1]) //先比較兩個(gè)子節(jié)點(diǎn)指標(biāo)，選擇最大的
son++;
if (arr[dad] > arr[son]) //如果父節(jié)點(diǎn)大于子節(jié)點(diǎn)代表調(diào)整完成，直接跳出函數(shù)
return;
else { //否則交換父子內(nèi)容再繼續(xù)子節(jié)點(diǎn)與孫節(jié)點(diǎn)比較
swap(arr[dad], arr[son]);
dad = son;
son = dad * 2 + 1;
}
}
}
void heap_sort(int arr[], int len) {
//初始化，i從最后一個(gè)父節(jié)點(diǎn)開(kāi)始調(diào)整
for (int i = len / 2 - 1; i >= 0; i--)
max_heapify(arr, i, len - 1);
//先將第一個(gè)元素和已經(jīng)排好的元素前一位做交換，再?gòu)男抡{(diào)整(剛調(diào)整的元素之前的元素)，直到排序完成
for (int i = len - 1; i > 0; i--) {
swap(arr[0], arr[i]);
max_heapify(arr, 0, i - 1);
}
}
int main() {
int arr[] = { 3, 5, 3, 0, 8, 6, 1, 5, 8, 6, 2, 4, 9, 4, 7, 0, 1, 8, 9, 7, 3, 1, 2, 5, 9, 7, 4, 0, 2, 6 };
int len = (int) sizeof(arr) / sizeof(*arr);
heap_sort(arr, len);
for (int i = 0; i < len; i++)
cout < < arr[i] < < ' ';
cout < < endl;
return 0;
}