嗯...畢竟經(jīng)濟基礎(chǔ)決定上層建筑
首先來看哪些排序是穩(wěn)定的
stable sort:插入排序，冒泡排序倍踪，歸并排序，計數(shù)排序索昂，基數(shù)排序建车，桶排序
unstable sort:選擇排序，快速排序椒惨，堆排序
1.插入排序
最壞時間復雜度：
void Insert_Sort(int A[]) {
for (int i = 1; i < N; ++i) {
int j = i - 1;
while (j >= 0 && A[j] > A[i]) {
swap(A[i], A[j]);
}
}
}
2.冒泡排序
最壞時間復雜度：
void Bubble_Sort(int A[]) {
for (int i = 0; i < N; ++i)
for (int j = N - 1; j > i; --j) {
if (A[i] > A[j])
swap(A[i], A[j]);
}
}
3.選擇排序
最壞時間復雜度：
思路是每次找一個最小值
void Selection_Sort(int A[]) {
for (int i = 0; i < N - 1; ++i) {
int min = i;
for (int j = i + 1; j < N; ++j) {
if (A[min] > A[j])
min = j;
}
swap(A[min], A[i]);
}
}
