1.时间复杂度总结

n2:       直接插入排序，冒泡排序，简单选择排序（这三种里面直接插入排序好一点）

nlogn:  快速排序，堆排序，归并排序

n:          基数排序

其他：n2

2.时间性能与初始序列无关：

口诀：“一堆乌龟选基友”

堆排序，归并排序，选择排序，基数排序

3.空间性能：

快速排序：logn

归并排序：n

基数排序：rd

其他：1

4.不稳定的有：

口诀：尔快选（你快选！！）希尔排序，快速排序，选择排序

两个选择排序都是不稳定的（简单选择排序/堆排序）

5.基于比较的排序算法最快只能是nlogn

表格总结：

全部算法实现：（单独对各个算法的分析和实现可以看笔者的其他博客）

// 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) {//直接插入排序的间隔是1for (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]就好了，但是为了理解“基准”的意思，还是用pivotwhile (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~highb.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)/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();
}