总结下学过的排序算法，方便以后用到。
1.插入排序——将一个记录插入到已排序好的有序表中，从而得到一个新，记录数增1的有序表。
void insertSort(int a[],int len)
{
for(int i = ;i < len;i ++)
{
int j = i;
int x = a[j]; //要插入的数
while(j > && x < a[j - ]) //将大的数推上去，空出个位置
{
a[j] = a[j - ];
j--;
}
a[j] = x; //插入
}
}
2.冒泡排序——不断地比较相邻2个数的大小，大的就推到后面，最后把最大值推到了最后，依次类推。
void swap(int &a,int &b)
{
int tmp = a;
a = b;
b = tmp;
}void bubbleSort(int a[],int len)
{
for(int i = len - ;i > ;i --)
for(int j = ;j < i;j ++)
if(a[j] > a[j + ])
swap(a[j],a[j + ]);
}
3.选择排序——第一次选出数组中最小的数与第一个数交换位置，第二次选出第二小的与第二个数交换位置，以此类推。
//swap函数见上。
void selectSort(int a[],int len)
{
for(int i = ;i < len - ;i ++)
{
int min = a[i];
int minPos = i;
for(int j = i + ;j < len;j ++)
{
if(a[j] < min)
{
min = a[j];
minPos = j;
}
}
if(minPos != i)
swap(a[i],a[minPos]);
}
}
4.归并排序——将一个序列分成2个长度相等的子序列，分别排序，然后再将它们合并成一个有序的序列。（合并的过程比较麻烦，这里利用一个辅助数组来将排好序的子序列先复制过去，然后再归并回原数组）
void mergeSortHelp(int a[],int tmp[],int left,int right)
{
if(left == right)
return;
int mid = (left + right) / ;
mergeSortHelp(a,tmp,left,mid);
mergeSortHelp(a,tmp,mid + ,right);
for(int i = left;i <= right;i ++)
tmp[i] = a[i];
int i = left;
int j = mid + ;
int k = left;
while(k <= right)
{
if(j > right)
a[k++] = tmp[i++];
else if(i > mid)
a[k++] = tmp[j++];
else if(tmp[i] < tmp[j])
a[k++] = tmp[i++];
else a[k++] = tmp[j++];
}
}void mergeSort(int a[],int len)
{
int *tmp = new int[len];
mergeSortHelp(a,tmp,,len - );
delete []tmp;
}
5.快速排序——选择数组中的一个数作为轴值（这里选择第一个数），将小于轴值的数放到左边，大的放到右边，轴值放中间，这样只需要各自递归快排左右两边数组，完成排序。
//swap函数见上上上
int partition(int a[],int left,int right)
{
int pivotPos = left; //记录轴值位置
int pivot = a[left]; //取最左边的值作为轴值
left ++; //避开轴值
while(left < right) //从左右两边各自扫描数组，左边遇到比轴值大的就停下，右边遇到比轴值小的就停下，交换。继续。。。
{
while(a[left] < pivot && left < right)
left++;
while(a[right] > pivot && left < right)
right--;
swap(a[left],a[right]);
}
if(a[right] < a[pivotPos])
{
swap(a[right],a[pivotPos]);
return right;
}else
{
swap(a[right - ],a[pivotPos]);
return right - ;
}
}void quickSortHelp(int a[],int left,int right)
{
if(left >= right)
return; int k = partition(a,left,right); //通过partition将数组按比轴值大小分别放到轴值左右两边，返回最后轴值的位置k。 quickSortHelp(a,left,k - );
quickSortHelp(a,k + ,right);
}
void quickSort(int a[],int len)
{
quickSortHelp(a,0,len – 1);
}
6.堆排序（夜深下次再写）
