选择排序
#include <stdio.h> /* * 选择排序 * 稳定性：不稳定 * 时间复杂度：O(N^2) **/ void select_sort(int a[], int l, int r) { for (int m_v, m_idx, t, i = l; i < r; ++i) { m_v = a[i]; m_idx = i; for (int j = i + 1; j < r; ++j) { if (m_v > a[j]) { m_v = a[j]; m_idx = j; } } t = a[i]; a[i] = a[m_idx]; a[m_idx] = t; } } int main(void) { int a[100]; int n; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); select_sort(a, 0, n); for (int i = 0; i < n; ++i) printf("%d ", a[i]); return 0; }
冒泡排序
#include <stdio.h> /* * 冒泡排序 * 稳定性：稳定 * 时间复杂度：O(N^2) **/ void bubble_sort(int a[], int l, int r) { for (int i = l; i < r; ++i) { for (int j = l; j < r - i - 1; ++j) { if (a[j] > a[j + 1]) { int tmp = a[j]; a[j] = a[j + 1]; a[j + 1] = tmp; } } } } int main(void) { int a[100]; int n; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); bubble_sort(a, 0, n); for (int i = 0; i < n; ++i) printf("%d ", a[i]); return 0; }
插入排序
#include <stdio.h> /* * 插入排序 * 稳定性：稳定 * 时间复杂度： O(N^2) **/ void insert_sort(int a[], int l, int r) { for (int tmp, j, i = l + 1; i < r; ++i) { tmp = a[i], j = i - 1; while (j >= l && tmp < a[j]) a[j+1] = a[j--]; a[j+1] = tmp; } } int main(void) { int a[100]; int n; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); insert_sort(a, 0, n); for (int i = 0; i < n; ++i) printf("%d ", a[i]); return 0; }
希尔排序
#include <stdio.h> /* * 希尔排序 * 稳定性：不稳定 * 时间复杂度：O(N*logN) **/ void shell_insert_sort(int a[], int l, int r, int d) { for (int tmp, j, i = l + d; i < r; ++i) { tmp = a[i], j = i - d; while (j >= l && tmp < a[j]) { a[j + d] = a[j]; j -= d; } a[j + d] = tmp; } } void shell_sort(int a[], int l, int r) { int d = (r - l) / 2; while (d >= 1) { shell_insert_sort(a, l, r, d); d /= 2; } } int main(void) { int a[100]; int n; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); shell_sort(a, 0, n); for (int i = 0; i < n; ++i) printf("%d ", a[i]); return 0; }
归并排序
/* * 归并排序 * 稳定性：稳定 * 时间复杂度：O(N*logN) **/ void merge(int a[], int n, int b[], int m, int t[]) { int i, j, k; i = j = k = 0; while (i < n && j < m) { if (a[i] < b[j]) t[k++] = a[i++]; else t[k++] = b[j++]; } while (i < n) t[k++] = a[i++]; while (j < m) t[k++] = b[j++]; } void my_merge_sort(int a[], int l, int r, int t[]) { int mid = (l + r) >> 1; int n = r - l; int i; if (l + 1 < r) { my_merge_sort(a, l, mid, t); my_merge_sort(a, mid, r, t); merge(a+l, mid-l, a+mid, r-mid, t); for (i = 0; i < n; ++i) a[i + l] = t[i]; } } void merge_sort(int a[], int l, int r) { int *t = (int *)malloc((r-l) * sizeof (int)); my_merge_sort(a, l, r, t); free(t); }
堆排序
#include <stdio.h> /* * 堆排序 * 稳定性：不稳定 * 时间复杂度：O(N*logN) **/ // big top pile void heap_adjust(int a[], int fa, int n) { int cd = fa * 2 + 1; while (cd < n) { if (cd + 1 < n && a[cd] < a[cd + 1]) cd++; if (a[fa] >= a[cd]) break; int tmp = a[fa]; a[fa] = a[cd]; fa = cd; cd = fa * 2 + 1; a[fa] = tmp; } } void build_heap(int a[], int n) { // ignore leap node for (int i = (n - 1) / 2; i >= 0; --i) { heap_adjust(a, i, n); } } void heap_sort(int a[], int l, int r) { build_heap(a + l, r - l); for (int tmp, i = r - 1; i > l; --i) { tmp = a[i]; a[i] = a[0]; a[0] = tmp; heap_adjust(a + l, 0, i); } } int main(void) { int a[100]; int n; scanf("%d", &n); for (int i = 0; i < n; ++i) scanf("%d", &a[i]); heap_sort(a, 0, n); for (int i = 0; i < n; ++i) printf("%d ", a[i]); return 0; }
快速排序
/* * 快速排序 * 稳定性：不稳定 * 时间复杂度：O(N*logN) **/ void quick_sort(int a[], int l, int r) { if (l + 1 >= r) return ; int low = l, high = r; int key = a[l]; while (low < high) { while (low < high && a[--high] >= key); a[low] = a[high]; while (low < high && a[++low] < key); a[high] = a[low]; } a[low] = key; quick_sort(a, l, low); quick_sort(a, low+1, r); }
基数排序
/* * 基数排序 * 稳定性：稳定 * 时间复杂度：O(d(n+radix)) [d个关键码，关键码的取值范围为radix] **/ int tmp[100000000]; void radix_sort(int arr[], int beg, int ed) { static int a[9] = {1, 10, 100, 1000, 10000, 100000, 1000000}; int cnt[10]; // 0~9十个数字 int digit = 0; // 最大位数 for (int i = beg; i < ed; ++i) while (arr[i] / a[digit + 1] > 0) digit++; // 从低位到高位依次排序 for (int idx = 0; idx <= digit; ++idx) { for (int i = 0; i < 10; ++i) cnt[i] = 0; // 桶计数清零 for (int i = beg; i < ed; ++i) cnt[ arr[i]/a[idx]%10 ]++; // 统计每个数字出现的次数 // 前缀和 统计每个数字前面的数字个数 这样就可以知道每个数字应该排在第几位了 for (int i = 1; i < 10; ++i) cnt[i] += cnt[i - 1]; for (int i = ed - 1; i >= beg; --i) tmp[ --cnt[arr[i]/a[idx]%10] ] = arr[i]; for (int i = beg, j = 0; i < ed; ++i, ++j) arr[i] = tmp[j]; } }
测试性能
int a[100000000]; double test(void(*fun)(int*, int, int), int range) { for (int i = 0; i < range; ++i) a[i] = rand(); clock_t start = clock(); fun(a, 0, range); clock_t finish = clock(); //for (int i = 0; i < range; ++i) printf("%d ", a[i]); return ((double)finish - start) / CLOCKS_PER_SEC; } int main() { srand((unsigned)time(NULL)); printf(" 数据范围 堆排序 归并排序 希尔排序 快速排序 插入排序 冒泡排序 选择排序 基数排序 "); for (int range = 100; range <= 100000; range *= 10) { printf("%9d %8.3f %8.3f %8.3f %8.3f %8.3f %8.3f %8.3f ", range, test(heap_sort, range), test(merge_sort, range), test(shell_sort, range), test(quick_sort, range), test(insert_sort, range), test(bubble_sort, range), test(select_sort, range), test(radix_sort, range)); } for (int range = 1000000; range <= 10000000; range *= 10) { printf("%9d %8.3f %8.3f %8.3f %8.3f %8.3f ", range, test(heap_sort, range), test(merge_sort, range), test(shell_sort, range), test(quick_sort, range), test(radix_sort, range)); } return 0; }