一.基本概念
1.稳定排序与不稳定排序:
对于A,B两个键值相等的对象，且在排序前，A在B之前，如果排序后A肯定还在B之前，则为稳定排序，如果B可能在A之前，为不稳定排序。
2.内排序和外排序：
内排序是指在排序期间数据对象全部存放在内存的排序
外排序是指在排序期间数据对象太多，不能同时存放在内存，必须依照排序过程的要求，不断在内外存之间移动的排序。
二.各种排序算法的实现
1.插入排序
基本思想：插入第i个对象时前i-1个对象已经排好了，将第i个对象插入前i-1个对象的合适地方，使得前i个对象有序。是稳定排序，比较次数和移动次数复杂度都为O(n^2)
void insertSort(int* disorder, int size){ int temp = 0,i = 0; for(int j = 1; j < size; j++){ temp=disorder[j]; i = j; while(i > 0 && temp < disorder[i-1]){ disorder[i] = disorder[i-1]; i--; } disorder[i] = temp; }}
2.希尔排序
基本思想：将数列以gap作为间隔分成子序列，分别对子序列进行插入排序，再逐步缩小间隔进行插入排序。shell提出gap取floor(n/2),gap=floor(gap/2).这是一种不稳定的排序。
void shellSort(int* disorder, int size){ int gap = size / 2; int temp = 0, i = 0; while(gap > 0){ for(int g = 0; g < gap; g++){ for(int j = g + gap; j < size;){ temp = disorder[j]; i = j; while(i>gap-1 && temp
3.起泡排序
基本思想：依次比较key(n)和key(n-1),直到key(2)和key(1)，这样会使最小的对象被起泡到第一个，依次进行起泡，完成排序。是稳定排序，比较次数和移动次数复杂度都为O(n^2)
void bubbleSort(int* disorder, int size){ int temp=0,modified=0; for(int j=1;j j-1;i--){ if(disorder[i]
4.快速排序
基本思想：任取一个对象作为基准，按照关键码的大小，将排序队列分为左右两个子序列，小于该对象的都放在左序列，大于该对象的都放在右序列，然后分别对两个子序列重复上述方法，直到所有对象有序排列。是不稳定排序，比较次数和移动次数复杂度都为O(n*logn)
void quickSort1(int* disorder, int start, int end){ if(start>=end){ return; } int middle=disorder[start]; int temp=0; int pivotpos=start+1,i=start+1; for(;i<=end;i++){ if(disorder[i]
5.选择排序
基本思想：每一趟在后面n-i个待排序对象中选出关键码最小的对象，作为有序对象集的第i个对象。不稳定的排序，比较次数为O(n^2),移动次数为O(n)
void selectSort(int* disorder, int size){ int temp=0,small; for(int j=0;j j-1;i--){ if(disorder[i]
6.锦标赛排序
基本思想：利用胜者树来进行选择排序。稳定的排序，比较次数为O(n*logn).
锦标赛排序虽然节省时间，但是对空间有较大浪费，不推荐
7.堆排序
基本思想：利用最大堆，将得到的最大元素依次调整到最后。不稳定的排序，时间复杂度为O(n*logn).
void filterDown(int* disorder, int pos, int size){ int temp = disorder[pos]; int iPos = pos; int iChildPos; while(2*iPos+1 < size){ iChildPos = 2*iPos+1; if(iChildPos+1 disorder[iChildPos]){ iChildPos++; } if(temp =0; i--){ filterDown(disorder, i, size); } int temp; for(int i=size-1; i>0; i--){ temp = disorder[i]; disorder[i] = disorder[0]; disorder[0] = temp; filterDown(disorder, 0, i); }}
8.归并排序
基本思想：先两两排序，再逐步进行归并。稳定的排序，时间复杂度为O(n*logn).
void merge(int* source,int*dest, int gap, int size){ int pos1,pos2,end1,end2,destpos=0; for(int i=0;i size?size:i+gap; pos2=i+gap; end2=i+2*gap>size?size:i+2*gap; while(pos1
9.基数排序
基本思想：利用分配和收集的方法进行排序，比如已知数字不超过100，可以按照十位数先进行分配，再分别进行排序后将数字收集起来。
三.排序结果的检验
对于排序算法，可以用下列的方法来生成一系列的随机数进行排序，并用isSorted函数来检验是否正确的排序了。
bool isSorted(int* disorder, int size){ for(int i=0;i disorder[i+1]) return false; } return true;}int _tmain(int argc, _TCHAR* argv[]){ const int size=200; const int maxnum = 10000; int* disorder=new int[size]; srand((unsigned) time(NULL)); for(int i=0;i