赞
踩
下标 | 1 | 2 | 3 | 4 | 5 | 最小值 |
---|---|---|---|---|---|---|
原始 | 4 | 3 | 5 | 2 | 1 | / |
第一次 | 1 | 3 | 5 | 2 | 4 | 1 |
第二次 | 1 | 2 | 5 | 3 | 4 | 2 |
第三次 | 1 | 2 | 3 | 5 | 4 | 3 |
第四次 | 1 | 2 | 3 | 4 | 5 | 4 |
完成 | 1 | 2 | 3 | 4 | 5 | / |
选择排序
从待排序的区间中找到最小元素的位置,并将该元素与该区间的第一个元素交换位置。这样通过 n − 1 n-1 n−1 次选择未排序部分的最小元素,将其放在正确位置从而达到对整个序列进行排序的效果。
for (i = 1 ~ n-1) # 轮数
int minp = i; # 设擂主(位置)
for (j = i+1 ~ n) # 打擂台
if (a[j] < a[minp])
minp = j;
end if
end for
swap(a[i], a[minp]);
end for
#include <iostream> using namespace std; int n; int a[1005]; void selectionSort(int a[], int n) { for (int i = 1; i <= n-1; i++) { int minp = i; // 设擂主所在的下标 for (int j = i+1; j <= n; j++) // 打擂台 { if (a[j] < a[minp]) { minp = j; } } swap(a[i], a[minp]); } } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } selectionSort(a, n); for (int i = 1; i <= n; i++) { cout << a[i] << " "; } return 0; }
代码分析:
我们以7 2 5 8 1为例。
i | a[] | minp | j | a[] | 操作 |
---|---|---|---|---|---|
- | 7 2 5 8 1 | - | - | 7 2 5 8 1 | - |
1 | 7 2 5 8 1 | 5 | 2 | 1 2 5 8 7 | 交换 7 和 1 |
2 | 1 2 5 8 7 | 2 | 3 | 1 2 5 8 7 | 无需交换 |
3 | 1 2 5 8 7 | 3 | 4 | 1 2 5 8 7 | 交换 5 和 3 |
4 | 1 2 5 8 7 | - | - | 1 2 5 8 7 | 无需交换 |
#include <iostream> using namespace std; int n, k; int a[100005]; void selectionSort(int a[], int n, int k) { for (int i = 1; i <= k; i++) { int maxp = i; // 设擂主所在的下标 for (int j = i+1; j <= n; j++) // 打擂台 { if (a[j] > a[maxp]) { maxp = j; } } swap(a[i], a[minp]); } } int main() { cin >> n >> k; for (int i = 1; i <= n; i++) { cin >> a[i]; } selectionSort(a, n, k); cout << a[k]; return 0; }
int x, pos = n+1;
# * x: 待插入的元素
# * pos: 比较的下标
for (j = n ~ 1)
if x < a[j]
a[j+1] = a[j];
pos--;
else
break;
end if
end for
a[pos] = x;
#include <iostream> using namespace std; int n, x, pos; int a[10005]; void insertionSort(int a[], int n, int x) { pos = n + 1; for (int i = n; i >= 1; i--) { if (x < a[i]) { a[i+1] = a[i]; pos = i; } else { break; } } a[pos] = x; } int main() { cin >> n >> x; for (int i = 1; i <= n; i++) { cin >> a[i]; } insertionSort(a, n, x); for (int i = 1; i <= n; i++) { cout << a[i] << " "; } return 0; }
插入排序
将待排序元素依次插到已排序序列中的恰当位置,最终形成有序序列的方法。
for (i = 2 ~ n)
int x = a[i], pos = i;
for (j = i-1 ~ 1)
if (x < a[j])
a[j+1] = a[j]
pos--;
else
break
end if
end for
a[pos] = x;
end for
#include <iostream> using namespace std; int n, x, pos; int a[100005]; void insertionSort(int a[], int n) { for (int i = 2; i <= n; i++) { x = a[i]; pos = i; for (int j = i-1; j >= 1; j--) { if (x < a[j]) { a[j+1] = a[j]; } else { break; } } a[pos] = x; } } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } // ... return 0; }
#include <iostream> using namespace std; int n, x, pos; int a[1005], b[1005]; void insetionSort(int a[], int n) { for (int i = 2; i <= n; i++) { x = a[i]; pos = i; for (int j = i-1; j >= 1; j--) { if (x < a[j]) { a[j+1] = a[j]; pos = j; } else { break; } } a[pos] = x; } } int main() { cin >> n; for (int i = 1; i <= n; i++) { cin >> a[i]; } for (int i = 1; i <= n-1; i++) { b[i] = abs(a[i+1] - a[i]) } insertionSort(b, n-1); for (int i = 1; i <= n-1; i++) { if (b[i] != i) { cout << "Not jolly"; return 0; } } cout << "Jolly"; return 0; }
排序算法 | 时间复杂度 | 空间复杂度 | 稳定性 |
---|---|---|---|
冒泡排序 | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 稳定 |
选择排序 | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 不稳定 |
插入排序 | O ( n 2 ) O(n^2) O(n2) | O ( 1 ) O(1) O(1) | 稳定 |
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。