插入排序，冒泡排序和选择排序是基本的排序方法，平均情况下时间复杂度是O(n2)。
插入排序对于规模很小的元素序列（n<=25）很有效，最好情况下只需要n-1次比较，不需要交换操作。在平均情况和最差情况下，比较和交换都是O(n2)的。
改进的冒泡排序在最好情况下只需要一次冒泡过程，n-1次比较。
选择排序的比较操作与初始排列无关，比较次数总是O(n2)，最好情况下，不移动，最差情况移动不超过3(n-1)次。
三种基本排序方法只需要一个辅助元素，主要用于元素个数n<10K的情况。
归并排序的一个特性是性能与输入元素序列无关，时间复杂度总是O(nlgn)。主要缺点是直接执行需要O(n)的附加内存空间。另一个优势是稳定排序算法。
堆排序是一种高效的内部排序算法，平均情况时间复杂度为O(nlgn)，没有什么最坏情况会导致堆排序的运行明显变慢，基本不需要额外空间。但是堆排序不太可能提供比快速排序更好的平均性能，不稳定算法。
快速排序是最通用的高效内部排序算法，平均情况时间复杂度为O(nlgn)，所需要的额外内存是O(lgn)。不稳定算法，在元素序列有序是会退化，时间复杂度增加到O(n2)，空间复杂度增加到O(n)。可以用找三个元素中位数来避免。
希尔排序的时间复杂度介于基本排序算法和高效算法之间，代码简单，不需要什么额外内存，不稳定算法。对于中等规模(n<=1000)，希尔排序是一种很好的选择。
计数排序的时间复杂度为O(k+n)，当k=O(n)时，为O(n)。计数排序的下界优于O(nlgn)，因为它不是一个比较排序算法，计数排序是用来输入元素的实际值来确定它们在数组中的位置。计数排序的一个重要性质就是他是稳定的，它经常用作基数排序算法的一个子过程。
基数排序的运行时间为O(n)，这看上去要比快速排序的平均情况时间O(nlgn)更好一些。然而，在这两个时间中，隐含在O几号中的常数因子是不同的。对于要处理的n个关键字，尽管基数排序执行的遍数可能比快速排序要少，但每一遍所需的时间都要长得多。哪一个排序算法更好取决于底层机器的实现特性(例如，快速排序通常可以比基数排序更为有效地利用硬件缓存)，同时还取决于输入的数据。此外，利用计数排序作为中间稳定排序的技术排序不是原地排序，而很多O(nlgn)时间的比较排序算法则可以做到原地排序。当内存比较宝贵时，快速排序这样的原地排序更为可取。
1、冒泡排序
//-------------冒泡排序begin-----------------template <class T>void babbleSort(T a[], int n){for (int i = 0; i < n; i++) {for (int j = n - 1; j > i; j--) {if (a[j] < a[j - 1]) { T tmp = a[j]; a[j] = a[j - 1]; a[j - 1] = tmp; } } }}//-------------冒泡排序end-----------------2、插入排序
//-------------插入排序begin-----------------template <class T>void insertSort(T a[], int n){for (int i = 1; i < n; i++) { T elem = a[i];int j = 0;for (j = i; j > 0; j--) {if (a[j - 1] < elem) {break; } a[j] = a[j - 1]; } a[j] = elem; }}//-------------插入排序end-----------------3、选择排序
//-------------插入排序begin-----------------template <class T>void insertSort(T a[], int n){for (int i = 1; i < n; i++) { T elem = a[i];int j = 0;for (j = i; j > 0; j--) {if (a[j - 1] < elem) {break; } a[j] = a[j - 1]; } a[j] = elem; }}//-------------插入排序end-----------------4、归并排序
//-------------递归归并排序begin-----------------template<class T>void merge(T a[], int beg, int mid, int end){ T *tmp = new T[end - beg + 1];int beg1 = beg;int end1 = mid;int beg2 = mid + 1;int end2 = end;int k = 0;while(beg1 <= end1 && beg2 <= end2) {if (a[beg1] <= a[beg2]) { tmp[k++] = a[beg1++]; }else { tmp[k++] = a[beg2++]; } }while (beg2 <= end2) { tmp[k++] = a[beg2++]; }while (beg1 <= end1) { tmp[k++] = a[beg1++]; } memcpy(a + beg, tmp, (end - beg + 1) * sizeof(T)); delete []tmp;}template<class T>void mergeSort(T a[], int beg, int end){int mid = int((beg + end)/2);if (beg < end) { mergeSort(a, beg, mid); mergeSort(a, mid + 1, end); merge(a, beg, mid, end); }}//-------------递归归并排序end----------------- //-------------非递归归并排序begin-----------------template <class T>void merge(T src[], T dst[], int beg, int mid, int end){int beg1 = beg;int end1 = mid;int beg2 = mid + 1;int end2 = end;int k = beg;while(beg1 <= end1 && beg2 <= end2)//选择两个序列中较小的 {if (src[beg1] <= src[beg2]) { dst[k++] = src[beg1++]; }else { dst[k++] = src[beg2++]; } }while (beg2 <= end2)//复制两序列中剩余部分 { dst[k++] = src[beg2++]; }while (beg1 <= end1) { dst[k++] = src[beg1++]; }}template <class T>void merge_pass(T src[], T dst[], int step, int len){int i = 0;//按照step划分子序列进行归并，step=2时 src划分为[X1 X2][X3 X4]...... for (i = 0; i <= len - 2 * step; i += 2 * step) { merge(src, dst, i, i + step - 1, i + 2 * step - 1); }//最后剩余不足两个子序列，但是足够一个子序列，进行归并 if (i + step < len) { merge(src, dst, i, i + step - 1, len - 1); }//将剩余的复制到尾部 else {for (int j = i; j < len; j++) { dst[j] = src[j]; } }}template <class T>void mergeSortUnrecursive(T a[], int len){int step = 1; T *tmp = new T[len];while (step < len) {//交替使用a和tmp，进行偶数次归并保证最后将结果放在a中 merge_pass(a, tmp, step, len); step *= 2; merge_pass(tmp, a, step, len); step *= 2; }}//-------------非递归归并排序end-----------------5、堆排序
//-------------堆排序begin-----------------template <class T>void maxHeapify(T a[], int i, int size){//左子女 int left = 2 * i + 1; T tmp = a[i];while (left <= size) {//存在右子女并且大于左子女 if (left < size && a[left] < a[left+1]) left++;//子女不大于当前值 if (tmp >= a[left])break;else {//子女向上移动 a[i] = a[left]; i = left; left = 2 * i + 1; } }//最开始的结点值保存到最终位置 a[i] = tmp;}template <class T>void heapSort(T a[], int size){//建立最大堆 for (int i = size/2 - 1; i>=0; i--) maxHeapify(a, i, size);//交换第一个和最后一个，然后调整为最大堆 for (int i = size - 1; i > 0; i--) { T tmp = a[0]; a[0] = a[i]; a[i] = tmp; maxHeapify(a, 0, i - 1); }}//-------------堆排序end-----------------6、快速排序
//-------------快速排序(原始)begin-----------------template <class T>int partition(T a[], int low, int high){int pos = low; T posElem = a[low];for (int i = low + 1; i <= high; i++) {//小于基准元素的交换到左侧 if (a[i] < posElem) { pos++;if (pos != i) { T tmp = a[i]; a[i] = a[pos]; a[pos] = tmp; } } } a[low] = a[pos]; a[pos] = posElem;return pos;}template <class T>void quickSort(T a[], int low, int high){if (low < high) {int pos = partition(a, low, high); quickSort(a, low, pos - 1); quickSort(a, pos + 1, high); }}//-------------快速排序(原始)end-----------------研究表明，序列长度为5到25是，采用直接插入排序比快速排序至少快10%，当排序序列小于某规模时直接使用插入排序
//-------------快速排序(小规模插入排序)begin-----------------template <class T>void quickSort_insert(T a[], int low, int high){//小于一个规模直接使用插入排序 if (high - low <= 80) { insertSort(a, low, high); }else {int pos = partition(a, low, high); quickSort_insert(a, low, pos - 1); quickSort_insert(a, pos + 1, high); }}//-------------快速排序(小规模插入排序)end-----------------取基准对象是采用在序列左端low，右端high和中点位置mid=(low+high)/2中去中间值，并且交换到high位置。这样可以避免出现退化的情况。
研究表明，将三个元素的中间元素法和小规模终止两个改进措施结合起来，可以讲递归实现的快速排序效率提高20%到25%。
//-------------快速排序(小规模停止后插入排序+三者取中)begin-----------------template <class T>T &median3(T a[], int low, int high){int mid = (low + high)/2;int k = low;//三者选最小为k if (a[mid] < a[k]) k = mid;if (a[high] < a[k]) k = high;//最小值交换到low if (k != low) { T tmp = a[k]; a[k] = a[low]; a[low] = tmp; }//mid为中间值，交换到high if (mid != high && a[mid] < a[high]) { T tmp = a[mid]; a[mid] = a[high]; a[high] = tmp; }return a[high];}template <class T>int partition_median3(T a[], int low, int high){int pos = low;//去三者中值 T posElem = median3(a, low, high);for (int i = low; i < high; i++) {if (a[i] < posElem) { pos++;if (pos != i) { T tmp = a[i]; a[i] = a[pos]; a[pos] = tmp; } } } a[high] = a[pos]; a[pos] = posElem;return pos;}template <class T>void quickSortHybrid(T a[], int low, int high){//小于某规模停止 if (high - low <=200)return;int pos = partition_median3(a, low, high); quickSort(a, low, pos - 1); quickSort(a, pos + 1, high);}template <class T>void quickSort_insertHybrid(T a[], int low, int high){ quickSort(a, low, high);//对基本有序的序列进行插入排序 insertSort(a, low, high);}//-------------快速排序(小规模停止后插入排序+三者取中)end-----------------当待排序元素序列有大量重复排序码是，快速排序算法的效率将会降到非常之低，三路划分的中间部分为与基准元素等值的。
//-------------快速排序(三路划分)begin-----------------template <class T>void quickSort3Partition(T a[], int low, int high){if (low >= high)return ; T posElem = a[high];int i = low - 1, j = high, p = low - 1, q = high;int k = 0;while (true) {while (a[++i] < posElem && i < j);while (a[--j] > posElem && i < j);if (i >= j)break; swap(a[i], a[j]);if (a[i] == posElem) swap(a[i], a[++p]);if (a[j] == posElem) swap(a[j], a[--q]); }if (a[i] > a[high]) { swap(a[i], a[high]); k = high - 1; }else k = high - 1;//j--; i++;while (k >= q) swap(a[k--], a[i++]);for (k = low; k <= p;) swap(a[k++], a[j--]);for (int m = low ; m<=high; m++) { cout << a[m] << " "; }cout <<"i=" << i << "j=" <<j << "p=" << p << "q=" << q << "k=" << k; cout <<endl; quickSort3Partition(a, low, j); quickSort3Partition(a, i, high);}//-------------快速排序(三路划分)end-----------------一般书上的快速排序法都是用递归实现的，递归是编译器自动用栈来实现的。当递归层次比较深时，需要占用比较大的进程栈空间，还有进程栈溢出的危险。很多时候将递归转化为非递归算法，更省时间和空间。其实原理很简单，即自己用栈来模拟递归的过程。每次从栈顶取出一部分做划分后，都把新的两部分的起始位置分别入栈。
//-------------快速排序(非递归)begin-----------------template <class T>void quickSortUnrecursive(T a[], int size){int s = int(4 * log((double)size)/log(2.0));int *stack = new int[s];int top = 0; T tmp;int low, high, pivot, i, j;//首先把整个数组入栈 stack[top++] = size - 1; stack[top++] = 0;while(top != 0) {//取出栈顶元素，进行划分 low = stack[--top]; high = stack[--top]; pivot = high;//保证i之前的元素的不大于轴 i = low;//j从前往后滑动 for (j = low; j < high; j++) {//如果碰到某个元素不大于轴，则与a[i]交换 if (a[j] <= a[pivot]) { tmp = a[i]; a[i] = a[j]; a[j] = tmp; i++; } }//i为分界点，交换a[i]和轴 if (i != pivot) { tmp = a[i]; a[i] = a[pivot]; a[pivot] = tmp; }//判断小于轴的部分元素如果多于一个的话, 则入栈 if (i - low > 1) { stack[top++] = i - 1; stack[top++] = low; }//判断大于轴的部分元素如果多于一个的话, 则入栈 if (high - i > 1) { stack[top++] = high; stack[top++] = i + 1; } } delete []stack;}//-------------快速排序(非递归)end-----------------7、希尔排序
//-------------希尔排序begin-----------------template <class T>void shellSort(T a[], int low, int high){int gap = high - low + 1; T tmp;do {//求下一增量 gap = gap / 3 + 1;//各子序列交替处理 for (int i = low + gap; i <= high; i++) {//逆序，插入排序 if (a[i] < a[i - gap]) { tmp = a[i];int j = i - gap;//找到插入位置 do { a[j + gap] = a[j]; j = j - gap; } while (j > low && tmp < a[j]);//插入元素 a[j + gap] = tmp; } } } while (gap > 1);}//-------------希尔排序end-----------------8、计数排序
//-------------计数排序begin-----------------template <class T>void countSort(T a[], int size, int k){ k++;int *b = new int[size];int *c = new int[k]; memset(c, 0, k * sizeof(int));//c[i]包含等于a[i]的元素个数 for (int i = 0; i < size; i++) { c[a[i]]++; }//c[i]包含小于或等于i的元素个数 for (int i = 1; i < k; i++) { c[i] += c[i - 1]; }//c[a[i]]即为a[i]的最终位置 for (int i = size - 1; i >= 0; i--) { b[c[a[i]] - 1] = a[i]; c[a[i]]--; } memcpy(a, b, size * sizeof(T)); delete []b; delete []c;}//-------------计数排序end-----------------9、基数排序
//-------------基数排序begin-----------------int maxbit(int a[], int n){int d = 1;int radix = 10;for (int i = 0; i < n; i++) {if (a[i] > radix) { radix *= 10; d++; } }return d;}void radixSort(int a[], int size){int d = maxbit(a, size);int *tmp = new int[size];//计数器 int *count = new int[10];int radix = 10;int k = 0;//进行d次排序 for (int i = 0; i < d; i++) {//每次分配前清空计数器 memset(count, 0, 10 * sizeof(int));for (int j = 0; j < size; j++) {//统计每个桶中的记录数 k = (a[j] / radix) % 10; count[k]++; }//将tmp中的位置依次分配给每个桶 for (int j = 1; j < 10; j++) { count[j] += count[j - 1]; }//将所有桶中记录依次收集到tmp中 for (int j = size - 1; j >= 0; j--) { k = (a[j] / radix) % 10; count[k]--; tmp[count[k]] = a[j]; }//将临时数组的内容复制到data中 memcpy(a, tmp, size * sizeof(int)); radix *= 10; } delete []tmp; delete []count;}//-------------基数排序end-----------------转载于:https://www.cnblogs.com/yysblog/archive/2011/11/30/2269229.html
