1.冒泡排序
这个写法是先把小的数字排出来然后再排出来大的数字
代码：
#includeusing namespace std;const int maxn = 1e5 + 10;int n;int num[maxn];void BubbleSort(int L, int R) { for(int i = L; i <= R; i ++) { int flag = 0; for(int j = R; j > i; j --) { if(num[j] < num[j - 1]) { swap(num[j], num[j - 1]); flag = 1; } } if(!flag) break; }}int main() { scanf("%d", &n); for(int i = 0; i < n; i ++) scanf("%d", &num[i]); BubbleSort(0, n - 1); for(int i = 0; i < n; i ++) { printf("%d", num[i]); printf("%s", i != n - 1 ? " " : "\n"); } return 0;}
2.插入排序
从前向后依次把每一个 $num[i]$ 插入到正确的位置
代码：
#includeusing namespace std;const int maxn = 1e5 + 10;int n;int num[maxn];void InsertSort(int L, int R) { for(int i = L; i <= R; i ++) { for(int j = i; j > L; j --) { if(num[j] < num[j - 1]) swap(num[j], num[j - 1]); else break; } }}int main() { scanf("%d", &n); for(int i = 0; i < n; i ++) scanf("%d", &num[i]); InsertSort(0, n - 1); for(int i = 0; i < n; i ++) { printf("%d", num[i]); printf("%s", i != n - 1 ? " " : "\n"); } return 0;}
3.选择排序
每次在上一次排好剩下的元素李选最小的排出来
代码：
#includeusing namespace std;const int maxn = 1e5 + 10;int n;int num[maxn];void SelectSort(int L, int R) { for(int i = L; i < R; i ++) { int minn = num[i]; int temp = i; for(int j = i + 1; j <= R; j ++) { if(num[j] < minn) { minn = num[j]; temp = j; } } swap(num[i], num[temp]); }}int main() { scanf("%d", &n); for(int i = 0; i < n; i ++) scanf("%d", &num[i]); SelectSort(0, n - 1); for(int i = 0; i < n; i ++) { printf("%d", num[i]); printf("%s", i != n - 1 ? " " : "\n"); } return 0;}
4.归并排序
中间分两段 两端分别拍好之后再合并
代码：
#includeusing namespace std;const int maxn = 1e5 + 10;int N;int a[maxn], b[maxn];void MergeSort(int L, int R) { if(L == R) return ; int mid = (R - L) / 2 + L; MergeSort(L, mid); MergeSort(mid + 1, R); int p1 = L, p2 = mid + 1, k = 0; while(p1 <= mid || p2 <= R) { if(p1 <= mid && p2 > R) b[k ++] = a[p1 ++]; else if(p1 > mid && p2 <= R) b[k ++] = a[p2 ++]; else { if(a[p1] < a[p2]) b[k ++] = a[p1 ++]; else b[k ++] = a[p2 ++]; } } for(int i = L; i <= R; i ++) a[i] = b[i - L];}int main() { scanf("%d", &N); for(int i = 0; i < N; i ++) scanf("%d", &a[i]); MergeSort(0, N - 1); for(int i = 0; i < N; i ++) { printf("%d", a[i]); printf("%s", i != N - 1 ? " " : "\n"); } return 0;}
5.堆排序
用 Insert 函数把数组放到一个最小堆里面 然后用 Get 函数不断得到最小值
#includeusing namespace std;const int maxn = 1e5 + 10;int T, N;int a[maxn];class Heap{private: int heap_[maxn]; int sz_;public: Heap() { sz_ = 0; } void Insert(int x) { sz_ ++; heap_[sz_] = x; int id = sz_; while(id > 1) { if(heap_[id] < heap_[id / 2]) { swap(heap_[id], heap_[id / 2]); id /= 2; } else break; } } int Get() { int res = heap_[1]; heap_[1] = heap_[sz_]; sz_ --; int id = 1; while(id <= sz_) { if(id * 2 > sz_) break; int minn = heap_[id * 2]; if(id * 2 + 1 <= sz_ && heap_[id * 2 + 1] < heap_[id * 2]) minn = heap_[id * 2 + 1]; if(heap_[id] < minn) break; int to; if(minn == heap_[id * 2]) to = id * 2; else to = id * 2 + 1; swap(heap_[id], heap_[to]); id = to; } return res; }};void HeapSort(int L, int R) { Heap heap; for(int i = L; i <= R; i ++) heap.Insert(a[i]); for(int i = L; i <= R; i ++) a[i] = heap.Get();}int main() { scanf("%d", &T); while(T --) { scanf("%d", &N); for(int i = 1; i <= N; i ++) scanf("%d", &a[i]); HeapSort(1, N); for(int i = 1; i <= N; i ++) { printf("%d", a[i]); printf("%s", i != N ? " " : "\n"); } } return 0;}