1.十大排序算法
本次用下面的例題詳解這十種排序算法
題目描述
將讀入的?N?個數從小到大排序后輸出。
輸入格式
第一行為一個正整數?N。
第二行包含?N?個空格隔開的正整數?ai?，為你需要進行排序的數。
輸出格式
將給定的?N?個數從小到大輸出，數之間空格隔開，行末換行且無空格。
輸入輸出樣例
輸入
5 4 2 4 5 1輸出?
1 2 4 4 5說明/提示
對于?20%?的數據，有?1≤N≤103；
對于?100%?的數據，有?1≤N≤105，1≤ai?≤109。
1.選擇排序
效率極低，有O(n2)，但優點在于實現簡單，邏輯符合日常思維
#include<iostream>
using namespace std;
int main()
{int n;long long int t = 0;cin >> n;long long int a[10000];for (int i = 0; i < n; i++){cin >> a[i];}int min = 0;for (int i = 0; i < n; i++){min = i;//重置最小值坐標for (int j = i; j < n; j++){if (a[j] < a[min]){min = j;}}t = a[min];a[min] = a[i];a[i] = t;}for (int i = 0; i < n; i++){cout << a[i] << " ";}cout << endl;
}2.冒泡排序
冒泡排序在最壞的情況下時間復雜度也是O(n2)，但如果是在原數列有序的情況下，能夠減少時間復雜度
#include<iostream>
#include<algorithm>
using namespace std;
int a[100005],n;
void selection_sort()
{for (int i = 0; i < n-1; i++){bool swaped = true;for (int j = 0; j < n-i-1; j++){if (a[j] > a[j + 1]){swap(a[j], a[j + 1]);swaped = false;}}if (swaped){break;}}
}
int main()
{cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}selection_sort();for (int i = 0; i < n; i++){cout << a[i] <<" ";}cout << endl;
}3.插入排序
和冒泡排序一樣依靠原數組部分有序來減少時間復雜度，最壞情況下還是O(n2)。
錯誤示例，意外寫成了冒泡排序，通過 swap頻繁交換元素，插入排序是不斷比較然后一次性插入
#include<iostream>
using namespace std;
int a[100005], n;
void insertion_sort()
{for (int i = 1; i < n; i++)//之所以初值是1，因為要和他的前一位比較，防止溢出{int key = a[i];int j = i - 1;while (j >= 0 && key < a[j]){swap(a[j+1], a[j]);j--;}}
}
int main()
{cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}insertion_sort();for (int i = 0; i < n; i++){cout<< a[i]<<" ";}cout << endl;
}正確做法
#include<iostream>
using namespace std;
int a[100005], n;
void insertion_sort()
{for (int i = 1; i < n; i++)//之所以初值是1，因為要和他的前一位比較，防止溢出{int key = a[i];int j = i - 1;while (j >= 0 && key < a[j]){a[j + 1] = a[j];j--;}a[j + 1] = key;}
}
int main()
{cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}insertion_sort();for (int i = 0; i < n; i++){cout<< a[i]<<" ";}cout << endl;
}4.希爾排序
希爾排序是插入排序的改良版，既然插入排序依賴原數組的原本就有序的狀態來減少時間復雜度，那么可以用”猜“的方式來減少最糟的無序狀態
例如這個圖中，假如索引為0和2的狀態無序，在普通的插入排序下就需要比較兩次，插入一次。如果直接交換的話會節省后續很多時間復雜度。之所以不直接去猜第一位和最后一位，是因為雖然這樣一個的空間跨度大，但是這是犧牲其他組別的空間跨度來實現的，所以都差不多了，反而風險更高。
