前言
这篇文章将会介绍常见的排序算法（使用 C++ 实现）
正文
1、冒泡排序
将数组分为有序区（左边）和无序区（右边），在初始化时有序区为空，无序区包含数组所有元素
每次从无序区的最后一个元素开始，一直向前冒泡到无序区的第一个位置，使其变成有序
template<typename E> void swap(E A[], int i, int j) { E temp = A[i]; A[i] = A[j]; A[j] = temp; } template<typename E> void bubbleSort(E A[], int n) { for (int i = 0; i < n - 1; i++) { for (int j = n - 1; j > i; j--) { if (A[j] < A[j - 1]) { swap(A, j, j - 1); } } } }
2、选择排序
将数组分为有序区（左边）和无序区（右边），在初始化时有序区为空，无序区包含数组所有元素
每次从无序区中选择一个合适的元素，并将其交换到无序区的第一个位置，使其变成有序
template<typename E> void swap(E A[], int i, int j) { E temp = A[i]; A[i] = A[j]; A[j] = temp; } template<typename E> void selectionSort(E A[], int n) { for (int i = 0; i < n - 1; i++) { int minIdx = i; for (int j = i; j <= n - 1; j++) { if (A[j] < A[minIdx]) minIdx = j; } swap(A, i, minIdx); } }
3、插入排序
将数组分为有序区（左边）和无序区（右边），在初始化时有序区包含数组的第一个元素，无序区包含其余的元素
每次将无序区中的第一个元素，一直向前交换到有序区中的合适位置，使其变成有序
template<typename E> void swap(E A[], int i, int j) { E temp = A[i]; A[i] = A[j]; A[j] = temp; } template<typename E> void insertionSort(E A[], int n) { for (int i = 1; i < n; i++) { for (int j = i; j > 0; j--) { if (A[j] < A[j - 1]) { swap(A, j, j - 1); } } } }
4、归并排序
递归进行，每次将数组一分为二，然后对两个数组分别排序后，合并两个数组
template<typename E> void mergeSort(E A[], E T[], int l, int r) { if (l == r) return; int m = (l + r) / 2; mergeSort<E>(A, T, l, m); mergeSort<E>(A, T, m + 1, r); // merge for (int k = l; k <= r; k++) T[k] = A[k]; int i = l, j = m + 1; for (int c = l; c <= r; c++) { if (i > m) A[c] = T[j++]; else if (j > r) A[c] = T[i++]; else if (T[i] < T[j]) A[c] = T[i++]; else A[c] = T[j++]; } }
优化：临时数组后半部分反向插入，这样可以不用检测边界情况
template<typename E> void mergeSort(E A[], E T[], int l, int r) { if (l == r) return; int m = (l + r) / 2; mergeSort<E>(A, T, l, m); mergeSort<E>(A, T, m + 1, r); // merge for (int k = l; k <= m; k++) T[k] = A[k]; for (int k = 1; k <= r - m; k++) T[r - k + 1] = A[k + m]; int i = l, j = r; for (int c = l; c <= r; c++) { if (T[i] < T[j]) A[c] = T[i++]; else A[c] = T[j--]; } }
5、快速排序
递归进行，每次在数组中选择一个基准，根据基准将数组一分为二，然后对两个数组分别排序后，拼接两个数组
template<typename E> void swap(E A[], int i, int j) { E temp = A[i]; A[i] = A[j]; A[j] = temp; } template<typename E> void quickSort(E A[], int l, int r) { if (r <= l) return; // find pivot int pivotIndex = (l + r) / 2; E pivot = A[pivotIndex]; // put pivot at last swap(A, pivotIndex, r); // partition int i = l - 1; int j = r; do { while (A[++i] < pivot) {} while (i < j && pivot < A[--j]) {} swap(A, i, j); } while (i < j); // put pivot in place swap(A, r, i); // recursive quickSort(A, l, i - 1); quickSort(A, i + 1, r); }
优化：使用栈替代递归
template<typename E> void swap(E A[], int i, int j) { E temp = A[i]; A[i] = A[j]; A[j] = temp; } template<typename E> void quickSort(E A[], int l, int r) { int stack[200]; int top = -1; stack[++top] = l; stack[++top] = r; while (top > 0) { // pop the stack r = stack[top--]; l = stack[top--]; // find pivot int pivotIndex = (l + r) / 2; E pivot = A[pivotIndex]; // put pivot at last swap(A, pivotIndex, r); // partition int i = l - 1; int j = r; do { while (A[++i] < pivot) {} while (i < j && pivot < A[--j]) {} swap(A, i, j); } while (i < j); // undo the last swap swap(A, i, j); // put pivot in place swap(A, r, i); // load up stack if (i - 1 > l) { stack[++top] = l; stack[++top] = i - 1; } if (r > i + 1) { stack[++top] = i + 1; stack[++top] = r; } } }
6、测试
测试程序
#include <iostream> #include <time.h> using namespace std; int main() { const int num = 1000; const int minVal = 0; const int maxVal = 1000; int* arr = new int[num]; for (int i = 0; i < num; i++) arr[i] = rand() % (maxVal - minVal + 1) + minVal; int* a4b = new int[num]; int* a4s = new int[num]; int* a4i = new int[num]; int* a4m = new int[num]; int* a4q = new int[num]; int* t = new int[num]; for (int i = 0; i < num; i++) a4b[i] = arr[i]; for (int i = 0; i < num; i++) a4s[i] = arr[i]; for (int i = 0; i < num; i++) a4i[i] = arr[i]; for (int i = 0; i < num; i++) a4m[i] = arr[i]; for (int i = 0; i < num; i++) a4q[i] = arr[i]; clock_t start, end; start = clock(); bubbleSort(a4b, num); end = clock(); cout << "bubbleSort: " << (double)(end-start)/CLOCKS_PER_SEC << endl; start = clock(); selectionSort(a4s, num); end = clock(); cout << "selectionSort: " << (double)(end-start)/CLOCKS_PER_SEC << endl; start = clock(); insertionSort(a4i, num); end = clock(); cout << "insertionSort: " << (double)(end-start)/CLOCKS_PER_SEC << endl; start = clock(); mergeSort(a4m, t, 0, num - 1); end = clock(); cout << "mergeSort: " << (double)(end-start)/CLOCKS_PER_SEC << endl; start = clock(); quickSort(a4q, 0, num - 1); end = clock(); cout << "quickSort: " << (double)(end-start)/CLOCKS_PER_SEC << endl; return 0; }
测试结果
| 数据规模 | 1000 | 10000 | 100000 | 1000000 | 10000000 | 100000000 |
| bubble sort | 0.003 s | 0.355 s | 41.414 s | / | / | / |
| selection sort | 0.001 s | 0.123 s | 12.151 s | / | / | / |
| insertion sort | 0.002 s | 0.224 s | 22.881 s | / | / | |
| merge sort | 0 s | 0.002 s | 0.021 s | 0.212 s | 2.285 s | |
| quick sort | 0 s | 0.002 s | 0.017 s | 0.175 s | 1.826 s |
文章知识点与官方知识档案匹配，可进一步学习相关知识
