这里讲的排序默认为内排序。

参考书籍：数据结构(C语言版)秦玉平马靖善主编冯佳昕周连秋副主编清华大学出版社按照排序过程中依据的原则不同划分为：（1）插入排序包括直接插入排序，折半插入排序，2_路插入排序，shell排序（2）交换排序包括简单交换排序，冒泡排序，快速排序（3）选择排序包括简单选择排序，*树形选择排序，*堆排序（4）归并排序（5）计数排序包括*计数排序，基数排序*上面打星号的代码没有添加*下面代码修改自/%D0%E3%B2%C5%CC%AB%CA%D8/blog/item/5ad1f372177b21 158701b093.html主要修改了快速排序的错误，添加了折半插入排序和2_路插入排序，而且按照以上(1)~(5)重新改写了程序的结构。

代码如下：排序头文件：sort.h#ifndef __SORT_H__#define __SORT_H__/******************************************************************** ****//* 排序头文件 *//******************************************************************** ****//******************************************************************** ****//* 头文件包含 */#include "insertSort.h"#include "exchangeSort.h"#include "selectSort.h"#include "mergeSort.h"#include "countSort.h"/************************************************************************/#endif（1）插入排序：insertSort.h#ifndef __INSERTSORT_H__#define __INSERTSORT_H__/******************************************************************** ****//*常用头文件包含*/#include <vector>using namespace std;/******************************************************************** ****//******************************************************************** ****//*插入排序的思想插入排序属于插入方法的排序算法，它的想法是从第一个元素开始，创建有序序列，把未排序序列依次插入到有序序列中，以此类推*//******************************************************************** ****//*函数实现，按从小到大排序*/template <class T>void insertSort(vector<T>& v){/*直接插入排序*/for (unsigned int i = 1; i < v.size(); i++){T tmp = v[i];int j = i - 1;while (j >= 0 && v[j] > tmp){v[j+1] = v[j];j--;}v[j+1] = tmp;}}template <class T>void biInsertSort(vector<T>& v){/*折半插入排序*/for (unsigned int i = 1; i < v.size(); i++) {T tmp = v[i];int low = 0;int high = i - 1;while (low <= high){int mid = (low + high) / 2;if (tmp > v[mid]){low = mid + 1;}else{high = mid - 1;}}int j = i - 1;while (j >= 0 && v[j] > tmp){v[j+1] = v[j];j--;}v[j+1] = tmp;}}template <class T>void binInsertSort(vector<T>& v){/*2_路查找排序*/vector<T> vecTmp(v);int first,final,low,high,mid,k,j;unsigned int i,siz;siz = v.size();first = final = 0;for (i = 1; i < siz; i++){T tmp = v[i];if (tmp >= vecTmp[0]){low = 0;high = final;while (low <= high){mid = (low + high) / 2;if (v[i] > vecTmp[mid]){low = mid + 1;}else{high = mid - 1;}}for (j = final; j >= low; j--) {vecTmp[j+1] = vecTmp[j];}vecTmp[low] = tmp;final++;}else{if (first == 0){first = siz - 1;vecTmp[siz-1] = tmp;}else{low = first;high = siz - 1;while (low <= high){mid = (low + high) / 2;if (tmp > vecTmp[mid]){low = mid + 1;}else{high = mid - 1;}}for (j = first; j <= high; j++){vecTmp[j-1] = vecTmp[j];}vecTmp[high] = tmp;first--;}}}for (i = 0,j = first; j < siz; i++,j++){v[i] = vecTmp[j];}for (k = 0; k <= final; k++){v[i++] = vecTmp[k];}}/******************************************************************** ****//* 希尔排序 *//*希尔排序的思想希尔排序属于插入方法的排序算法，可以说是插入排序算法的改进版本，它的想法是把数据分组，在分组内进行插入排序，以此类推，分组的大小跟数据量有关系，D. E. Knuth建议数据量很大时按3*n+1分组，例如100的数据时，可以取1，4，13，40。

*/template <class T>void shellSort(vector<T>& v){for (unsigned int count = (unsigned int)v.size()/2; count > 0; count /= 2){for(unsigned int group = 0; group < count; group++){for (unsigned int i = group; i < v.size(); i += count){T tmp = v[i];int j = i - count;while (j >=0 && v[j] > tmp){v[j+count] = v[j];j -= count;}v[j+count] = tmp;}}}}/******************************************************************** ****//******************************************************************** ****/#endif（2）交换排序：exchangeSort.h#ifndef __EXCHANGESORT_H__#define __EXCHANGESORT_H__/******************************************************************** ****//*常用头文件包含*/#include <algorithm>/*要用template<class Type> void swap(Type& _Left,Type& _Right);*/#include <vector>#include <math.h>using namespace std;/******************************************************************** ****//******************************************************************** ****//*交换排序的思想交换排序属于比较法的排序算法，它的想法是扫描整个数据，从第0个元素开始，跟以后的元素逐个比较，按照排序规则(从小到大或者从大到小)交换顺序，比较完第a后再去比较第a+1个元素，以此类推*//*函数实现，按从小到大排序*/template <class T>void exchageSort(vector<T>& v){for (unsigned int i = 0; i < v.size()-1; i++){for (unsigned int j = i + 1; j < v.size(); j++){if (v[i]>v[j]){swap(v[i],v[j]);}}}}/******************************************************************** ****//*冒泡排序的思想冒泡排序属于比较法的排序算法，它的想法是比较相邻的两个数据，按照排序规则(从小到大或者从大到小)交换顺序，再去比较下一组相邻元素，以此类推*//******************************************************************** ****//*函数实现，按从小到大排序*/template <class T>void bubbleSort(vector<T>& v){bool flag = true;for (unsigned int i = 0; (i < v.size()-1) && (flag); i++){flag = false;for (unsigned int j = 0; j < v.size() - i - 1; j++){if (v[j]>v[j+1]){swap(v[j],v[j+1]);flag = true;}}}}/******************************************************************** ****//******************************************************************** ****//*快速排序的思想快速排序的想法是尽可能的减少每次排序的数据量以提高效率，那么对于任意从数据中取出的数据，可以按照大小把比它小的放在它的左边，比它大的放在它的右边，那么这个数的位置就确定了，再在它的左右两边分别按此排序，这就是快速排序。