1. 代码 /* * @Brief: 常见排序算法汇总 * @Author: * @Date: 2021-07-01 */ #include <iostream> #include <algorithm> #include <vector> #include <queue> using namespace std; void printArray(int *a, int len){ for(int i = 0; i < len; i++) cout << a[i] << " "; cout << endl << endl; } void bubbleSort(int *a, int len){ for(int i = 0; i < len - 1; i++){ for(int j = 0; j < len - i; j++){ if(a[j] > a[j+1]) swap(a[j], a[j+1]); } } } void selectSort(int *a, int len){ for(int i = 0; i < len; i++){ int mi = i; for(int j = i; j < len; j++){ if(a[j] < a[mi]) mi = j; } if(i != mi) swap(a[i], a[mi]); } } void insertionSort(int *a, int len){ for(int i = 0; i < len; i++){ int key = a[i]; int j = i; while(j >= 1 && a[j - 1] > key) a[j] = a[j-1], j--; a[j] = key; } } void shellSort(int *a, int len){ // cout << "原始数组" << endl; // printArray(a, len); for(int d = len / 2; d >= 1; d /= 2){ // 插入排序 for(int i = 0; i < len; i += d){ int key = a[i]; int j = i; while(j >= d && a[j-d] > key) a[j] = a[j-d], j -= d; a[j] = key; } // cout << "d = " << d << " 排序结果" << endl; // printArray(a, len); } } void quickSort(int *a, int len, int l, int r){ if(l >= r) return ; int x = a[l + (r - l) / 2]; int i = l - 1, j = r + 1; while(i < j){ while(a[++i] < x); while(a[--j] > x); if(i < j) swap(a[i], a[j]); } quickSort(a, len, l, j); quickSort(a, len, j + 1, r); } void mergeSort(int *a, int len, int l, int r){ if(l >= r) return ; int mid = l + (r - l) / 2; mergeSort(a, len, l, mid); mergeSort(a, len, mid + 1, r); int i = l, j = mid + 1, k = 0; int *tmp = new int[r - l + 1]; while(i <= mid && j <= r){ if(a[i] < a[j]) tmp[k++] = a[i++]; else tmp[k++] = a[j++]; } // 处理尾巴 while(i <= mid) tmp[k++] = a[i++]; while(j <= r) tmp[k++] = a[j++]; // 复制回原数组中 for(i = l, k = 0; i <= r; i++, k++) a[i] = tmp[k]; delete tmp; // 回收内存 } // 堆排序 namespace heapSort{ int *heap = nullptr; int ss = 0; // 堆的现有节点数 从下标是1的节点开始存 int n = 0; // 数组长度 void down(int u){ // 小顶堆 int t = u; if(u * 2 <= ss && heap[u * 2] < heap[t]) t = u * 2; if(u * 2 + 1 <= ss && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1; if(t != u){ swap(heap[t], heap[u]); down(t); } } void heapSort(int *a, int len){ heap = new int[len + 5]; n = len; for(int i = 0; i < len; i++) heap[++ss] = a[i]; for(int i = n / 2; i ; i--) down(i); for(int i = 0; i < len; i++){ a[i] = heap[1]; heap[1] = heap[ss--]; down(1); } delete heap; } }; int main(){ int a[10] = {8, 4, 2, 5, 7, 3, 1, 9, 0, 6}; int len = 10; //bubbleSort(a, len); //selectSort(a, len); //insertionSort(a, len); //quickSort(a, len, 0, len - 1); //mergeSort(a, len, 0, len - 1); //shellSort(a, len); //heapSort::heapSort(a, len); printArray(a, len); return 0; } 2. 稳定性 稳定排序算法:如果两数相等的话,排序以后先后位置是否会改变,如果不改变,就是稳定的。
...