内部排序
排序（sort）是计算机程序设计中一个重要的操作，它的功能是把一个数据元素的任意序列重新排序成为一个按关键字有序的序列。排序有七种最普遍的排序方法：
直接插入排序 冒泡排序 希尔排序 堆排序 并归排序 快速排序
下面就对这些排序一一介绍.
直接插入排序
直接插入排序是一种最简单的排序方法，它的基本操作是将一个记录插入已经排好的有序表中，从而得到一个新的，记录数增1的有序表，下面是直接插入排序的说明：
void InsertSort(int sort[],int length){
int i,j,temp;
for(i = 1;i < length; i++){
for(j = 0;j < i; j++){
if(sort[j] > sort[i]){
temp = sort[i];
sort[i] = sort[j];
sort[j] = temp;
}
}
}
}
传入参数数组首地址，以及数组长度，设置temp哨兵，用于交换，两层for循环保证插入的元素于已有的有序数组进行比较。 插入方式并不仅限于此，还有折半插入，类似于折半查找的原理，这里就不进行过多的赘述。
希尔排序
希尔排序又称为：缩小增量排序，它也是一种插入排序类的方法，但时间复杂度上有较大的改进，先将整个待排记录分割成为若干子序列分别进行直接插入排序，待整个序列中的“基本有序”时，再对全体记录进行一次直接插入排序，当然希尔排序的子序列的构成并不是简单的逐段分割，而是相隔某个“增量”的记录组成一个子序列。一般增量为一增量的一半，初始增量为数组长度的一半。下面是希尔排序的说明：
void Shellsort(int sort[],int length){
int i,k;
for(k = length/2;k > 0;k /= 2){
for(i = k;i < length;i++){ //从数组的第增量个元素开始
if(sort[i] < sort[i - k]){ //组内元素对比，插入排序
int temp = sort[i];
int j = i - k; //j：比较的组内元素
while (j >= 0 && sort[j] > temp){ //组内排序（直接插入排序）
sort[j + k] = sort[j];
j -= k;
}
sort[j + k] = temp;
}
}
}
}
快速排序
快速排序是对冒泡排序的一种改进，它的基本思想是，通过一趟排序将待排序记录分割成两个独立的部分，其中一部分记录关键字均比另一部分关键字小，则可分别对这两部分继续排序，达到整个序列有序。 一趟快速排序的具体做法是：设置两个指针low和hight分别指向待排序序列的开始和结尾，，记录下基准值baseval(待排序列的第一个记录)，然后先从high所指的位置向前搜索直到找到一个小于baseval的记录并互相交换，接着从low所指向的位置向后搜索直到找到一个大于baseval的记录并互相交换，重复以上步骤直到low等于hight，下面是快速排序的说明：
void QuickSort(int sort[],int start,int end){
if(start >= end)
return;
int i = start;
int j = end;
int baseval = sort[start];
while(i < j){
//从右往左找比基准数小的数
while(i < j && sort[j] >= baseval){
j--;
}
if(i < j){ //交换
sort[i] = sort[j];
i++; //减少一次寻找比基准数大的数
}
//从左往右找比基准数大的数
while(i < j && sort[i] < baseval){
i++;
}
if(i < j){ //交换
sort[j] = sort[i];
j--; //减少一次寻找比基准数小的数
}
}
//把基准数放到i的位置
sort[i] = baseval;
//递归
QuickSort(sort,start,i - 1); //快速排序基准数之前的
QuickSort(sort,i + 1,end); //快速排序基准数之后的
}
选择排序
选择排序的基本思想是：每一趟在n-i+1(i=1,2,…,n-1)个记录中选取关键字最小的记录作为有序序列中第i个记录。具体来说，假设长度为n的数组arr，要按照从小到大排序，那么先从n个数字中找到最小值min，如果最小值min的位置不在数组的最左端，则将最小值min于待排序序列首元素交换，接着在剩下的n-1个数字中找到最小值min，如果最小值min不等于待排序序列第二个元素，则交换这两个数字，依次类推，直到数组有序排列。算法的时间复杂度为O(n^2)。思路很简单，下面是选择排序的说明：
void SelectSort(int sort[],int length){
for (int i = 0; i < length; ++i) {
int index = i; //记录点
for (int j = i + 1; j < length; ++j) { //从有序序列之后开始
if(sort[j] < sort[index]){
index = j; //设置记录点为无序序列最小的元素
}
}
if(index == i)
continue;
else{
int temp; //设置哨兵
temp = sort[index];
sort[index] = sort[i];
sort[i] = temp;
}
}
}
归并排序
归并排序，归并的含义是将两个或两个以上的有序列表组合成一个新的有序表。它的实现方法很简单，假设初始序列含有n个记录，则可以看成是n个有序的子序列，每个子序列的长度为1，然后两两归并，得到n/2（表示不小于x的最小整数）个长度为2(或者是1)的有序子序列，再两两归并。如此重复，直到得到一个长度为n的有序序列为止。这种排序方法称为2-路归并排序。下面说明归并排序：
void MergingSort(int sort[], int start, int end, int *temp)
{
if (start >= end)
return;
int mid = (start + end) / 2;
MergingSort(sort, start, mid, temp);
MergingSort(sort, mid + 1, end, temp);
// 合并两个有序序列
int length = 0; // 表示辅助空间有多少个元素
int i_start = start;
int i_end = mid;
int j_start = mid + 1;
int j_end = end;
while (i_start <= i_end && j_start <= j_end)
{
if (sort[i_start] < sort[j_start]) //把两个有序序列元素添加到辅助序列中
{
temp[length] = sort[i_start];
length++;
i_start++;
}
else
{
temp[length] = sort[j_start];
length++;
j_start++;
}
}
//当一个序列为空，直接添加另一数列剩下的元素
while (i_start <= i_end)
{
temp[length] = sort[i_start];
i_start++;
length++;
}
while (j_start <= j_end)
{
temp[length] = sort[j_start];
length++;
j_start++;
}
// 把辅助空间的数据放到原空间
for (int i = 0; i < length; i++)
{
sort[start + i] = temp[i];
}
}
堆排序
可以将堆看做是一个完全二叉树。并且，每个结点的值都大于等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于等于其左右孩子结点的值，称为小顶堆。
堆排序(Heap Sort)是利用堆进行排序的方法。其基本思想为：将待排序列构造成一个大顶堆(或小顶堆)，整个序列的最大值(或最小值)就是堆顶的根结点，将根节点的值和堆数组的末尾元素交换，此时末尾元素就是最大值(或最小值)，然后将剩余的n-1个序列重新构造成一个堆，这样就会得到n个元素中的次大值(或次小值)，如此反复执行，最终得到一个有序序列。第一步初始化大顶堆，从第一个非叶子结点开始，第二步把最后一个元素与堆顶元素交换，第三步检查交换后是否满足大顶堆，不满足重新初始化，重复上述操作，直到序列所有元素都经过交换，下面说明堆排序：
void HeapAdjust(int sort[], int i, int length)
{
// 调整i位置的结点
// 先保存当前结点的下标
int max = i;
// 当前结点左右孩子结点的下标
int lchild = i * 2 + 1;
int rchild = i * 2 + 2;
if (lchild < length && sort[lchild] > sort[max])
{
max = lchild;
}
if (rchild < length && sort[rchild] > sort[max])
{
max = rchild;
}
// 若i处的值比其左右孩子结点的值小，就将其和最大值进行交换
if (max != i)
{
int temp;
temp = sort[i];
sort[i] = sort[max];
sort[max] = temp;
// 递归
HeapAdjust(sort, max, length);
}
}
// 堆排序
void HeapSort(int sort[], int length)
{
// 初始化堆
// length / 2 - 1是二叉树中最后一个非叶子结点的序号
for (int i = length / 2 - 1; i >= 0; i--)
{
HeapAdjust(sort, i, length);
}
// 交换堆顶元素和最后一个元素
for (int i = length - 1; i >= 0; i--)
{
int temp;
temp = sort[i];
sort[i] = sort[0];
sort[0] = temp;
HeapAdjust(sort, 0, i);
}
}
完整代码请见：排序
