1.时间复杂度总结
n2: 直接插入排序，冒泡排序，简单选择排序（这三种里面直接插入排序好一点）
nlogn: 快速排序，堆排序，归并排序
n: 基数排序
其他：n2
2.时间性能与初始序列无关：
口诀：“一堆乌龟选基友”
堆排序，归并排序，基本选择排序，基数排序
3.空间性能：
快速排序：logn
归并排序：n
基数排序：rd
其他：1
4.不稳定的有：
口诀：尔快选（你快选！！）希尔排序，快速排序，选择排序
两个选择排序都是不稳定的（简单选择排序/堆排序）
5.基于比较的排序算法最快只能是nlogn
6.全局有序的算法
一趟排序便可以确定一个元素的最终位置的算法：交换排序（冒泡排序，快速排序），选择排序（堆排序，简单选择排序）
表格总结：
类别
排序方法
最好时间
最坏时间
平均时间
空间复杂度
稳定性
序列特征
适用于
插入排序
直接插入排序
n(顺序)
n2（逆序）
n2
1
稳定
有序序列+待排序元素+无序序列
基本有序/n越小越好
折半插入排序
稳定
有序序列+待排序元素+无序序列
希尔排序
与d相关
n2
n1.3
1
不稳定
缩小增量，组内直接插入排序
顺序存储
交换排序
冒泡排序
n(顺序)
n2逆序
n2
1
稳定
无序序列+最大值/最小值+无序序列
快速排序
无序
有序n2
逆序
nlogn
平均：Logn
最坏：n
不稳定
较小无序序列+基准值+较大有序序列
非自然排序，越乱越好
分治
选择排序
简单选择排序
N2
N2
N2
1
不稳定
有序序列+待排序元素+无序序列
堆排序
nlogn
nlogn
Nlogn
建堆：n
调整：logn
1
不稳定
无序序列+最大值/最小值+无序序列
越多越好
归并排序
/
nlogn
nlogn
nlogn
n
稳定
短有序序列+短有序序列+短…
分治
基数排序
/
r+n
d(r+n)
d(r+n)
r
稳定
分配+收集
关键字有较小的取值范围
全部算法实现：（单独对各个算法的分析和实现可以看笔者的其他博客）
// WangDao_08_paixu.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。 // #include "pch.h" #include <iostream> #include<vector> #include<queue> using namespace std; void insertSort(vector<int> a) { int j,i; for (i = 2; i < a.size(); i++) {//a[0]是哨兵，a[1]默认为已排序，从a[2]开始排序 if (a[i] < a[i - 1]) {//如果待插入元素比有序序列中的最后一个元素小才需要比较和移动元素，否则不动 a[0] = a[i];//将待排序元素存放在哨兵的位置 for (j = i - 1; a[j] > a[0]; j--) a[j + 1] = a[j]; a[j + 1] = a[0];//将哨兵中暂存的元素访问插入位置 } } for (i = 1; i < a.size(); i++)cout << a[i] << " "; } void binarySort(vector<int> num) { int low, high, mid; for (int i = 2; i < num.size(); i++) { low = 1; high = i - 1; num[0] = num[i]; while (low<=high) { mid = (low + high) / 2; if (num[mid] < num[0])low = mid + 1;//插入位置在后半部分 else high = mid - 1; } for (int j = i - 1; j >= high + 1; j--)num[j + 1] = num[j]; num[high + 1] = num[0]; } for (int i = 1; i < num.size(); i++)cout << num[i] << " "; } void shellSort(vector<int> num) { int i, j; for (int d = (num.size()-1)/2; d >= 1; d = d / 2) { //直接插入排序的间隔是1 for (i = d + 1; i < num.size(); i++) { if (num[i]<num[i-d]) { num[0] = num[i];//待插入元素存入num[0]中 for (j = i - d; j>0&&(num[j] > num[0]); j = j - d) num[j + d] = num[j]; num[j + d] = num[0]; } } } for (int k = 1; k < num.size(); k++)cout << num[k] << " "; } void bubbleSort(vector<int> num) { bool flag; int temp; for (int i = 1; i < num.size()-1; i++) {//n-1轮（我的程序中元素是从第一个位置开始存储的所以有点不一样，总之只要是n轮循环就好） flag = true; for (int j =num.size()-1; j>i; j--) {//从后往前能够防止数组越界 if (num[j] < num[j-1]) { temp = num[j-1]; num[j-1] = num[j]; num[j] = temp; flag = false; } } if (flag) break; } for (int i = 1; i < num.size(); i++)cout << num[i] << " "; } int partition(vector<int> &a, int low, int high) { int pivot = a[low];//其实可以不用pivot,直接用a[0]就好了，但是为了理解“基准”的意思，还是用pivot while (low < high) { while (low < high&&a[high] >= pivot)--high;//注意这里是等于 a[low] = a[high]; while (low < high&&a[low] <= pivot)++low; a[high] = a[low]; } a[low] = pivot; return low; } void quickSort(vector<int> &a, int low, int high) { if (low < high) { int pivotpos = partition(a, low, high); quickSort(a, low, pivotpos - 1); quickSort(a, pivotpos + 1, high); } } void SelectSort(vector<int> a) { int k, temp; for (int i = 1; i < a.size() - 1; i++) { k = i; for (int j = i + 1; j < a.size(); j++) if (a[j] < a[k]) k = j; if (k!=i) { temp = a[i]; a[i] = a[k]; a[k] = temp; } } for (int i = 1; i < a.size(); i++)cout << a[i] << " "; } void adjustHeap(vector<int> &a, int k, int n) { a[0] = a[k]; for (int i = 2 * k; i <=n; i = i * 2) { if (i<n&&a[i] < a[i + 1])i++;//注意这里的判断条件顺序一定不能反 if (a[0] >=a[i])break; else { a[k] = a[i]; k=i; } } a[k] = a[0]; } void bulidMaxheap(vector<int> &a,int n) { for (int i=n/2; i > 0; i--)adjustHeap(a, i,n); } void heapSort(vector<int> a,int n ) { int temp; bulidMaxheap(a,n);//建堆 for (int i = n; i>1; i--) {//n-1轮调整就好了 temp = a[1]; a[1] = a[i]; a[i] = temp; adjustHeap(a, 1,i-1); } for (int i = 1; i <= n; i++)cout << a[i] << " "; } vector<int> b(20); void merge(vector<int> &a,int low, int mid, int high) { //合并low~mid;mid+1~high b.assign(a.begin(), a.end()); mid = (low + high) / 2; int i = low,k = low, j = mid + 1; while (i<=mid&&j<=high) { if (b[i] < b[j]) { a[k] = b[i]; k++; i++; } else { a[k] = b[j]; k++; j++; } } while (i <= mid) { a[k] = b[i]; i++; k++; } while (j<=high) { a[k] = b[j]; j++; k++; } } void mergeSort(vector<int> &a, int low, int high) { if (low < high) { int mid = (low + high) / 2; mergeSort(a,low, mid); mergeSort(a,mid + 1, high); merge(a, low,mid,high); } } void collect(vector<int> &a, vector<queue<int> > &tong) { int k = 0; for (int i = 0; i < 10; i++) { while (!tong[i].empty()) { a[k] = tong[i].front(); tong[i].pop(); k++; } } } void basicSort(vector<int> a) { vector<queue<int> > tong(10);//十个桶子 int temp; /*分配个位数*/ for (int i = 0; i < a.size(); i++) { temp = a[i] % 10; tong[temp].push(a[i]); } /*收集个位数*/ collect(a, tong); /*分配十位数*/ for (int i = 0; i < a.size(); i++) { temp = (a[i] % 100-a[i])/10; tong[temp].push(a[i]); } /*收集十位数*/ collect(a, tong); /*输出*/ for (int i = 0; i < a.size(); i++)cout << a[i] << " "; } void Sort() { int n; cout << "请输入元素个数："; cin >> n; vector<int> num(n+1); for (int i = 1; i < n + 1; i++)cin >> num[i]; cout << "直接插入排序："; insertSort(num); cout << endl; cout << "折半插入排序："; binarySort(num); cout << endl; cout << " 希尔排序："; shellSort(num); cout << endl; cout << " 冒泡排序："; bubbleSort(num); cout << endl; vector<int> num1; num1.assign(num.begin(), num.end()); cout << " 快速排序："; quickSort(num1,1,num1.size()-1); for (int i = 1; i < num1.size(); i++)cout << num1[i] << " "; cout << endl; cout << "简单选择排序："; SelectSort(num); vector<int> num2; num2.assign(num.begin(), num.end()); cout << endl; cout << " 堆排序："; heapSort(num2,num2.size()-1); cout << endl; cout << " 归并排序："; mergeSort(num,1,num.size() - 1); for (int i = 1; i < num.size(); i++)cout << num[i] << " "; cout << endl; vector<int> a; a.assign(num.begin() + 1, num.end()); cout << " 基数排序："; basicSort(a); } int main() { Sort(); }
