续说排序

接着上一篇文章常用的排序，继续说排序，剩下的还有直接插入排序，直接选择排序和堆排序，默认排序顺序仍是递增排序。废话不多说了，开始进入正题。

插入排序其实分为：直接插入排序，二分插入排序（或折半插入排序），希尔排序，其基本思想就是：每次将一个待排序的记录，按其关键字的大小插入到前面已经排好序的子表中的适当位置，直到全部记录插入完成为止。在这里只介绍直接插入排序。

直接插入排序

直接先来代码好了。

void InsertSort(RecType R[],int n)
{
    int i,j;
    RecType tmp;
    for (int i = 1; i < n; i++)
    {
        tmp = R[i];
        j = i - 1;
        while(j >= 0 && tmp.key < R[j].key)
        {
            R[j+1] = R[j];
            j--;
        }
        R[j+1] = tmp;
    }
}

此排序的操作过程为：假设有一序列为（6，3，7，5，1，4，2，9），刚开始时i = 1，j = 0，有序区暂时只有R[0]一个记录。从6起，从右向左查找，3小于6，将6右移一个位置，j-- 后while条件不满足了，结束while循环，将3插入R[0]的位置，此时序列变为（3，6，7，5，1，4，2，9），第一趟排序结束。接下来第二趟排序，i = 2，待插入的记录为R[2] = 7，从6开始从右向左查找。7大于6，while条件不满足，所以7的位置不变。此时序列变为（3，6，7，5，1，4，2，9），第三趟排序...以此类推，直到所有记录都有序为止。

初始序列：6 3 7 5 1 4 2

i = 1： <b><u>3</u></b> 6 7 5 1 4 2 9
i = 2： 3 6 <b> <u>7</u></b> 5 1 4 2 9
i = 3： 3 <b><u>5</u></b> 6 7 1 4 2 9
i = 4： <b><u>1</u></b> 3 5 6 7 4 2 9
i = 5： 1 3 <b> <u>4</u></b> 5 6 7 2 9
i = 6： 1 <b><u>2</u></b> 3 4 5 6 7 9
i = 7： 1 2 3 4 5 6 7 <b> <u>9</u></b>

选择排序的基本思想是：每一趟排序是从待排序的记录中选出关键字最小的记录，顺序放在已排好序的记录序列的末尾，直到全部记录排序完毕。常用的选择排序方法有直接选择排序（或简单选择排序）以及 堆排序。

直接选择排序

void selectSort(RecType R[],int n)
{
    int i,j,k;
    RecType tmp;
    for (int i = 0; i < n - 1; i++)
    {
        k = i;
        for (int j = i + 1; j < n; j++)
            if (R[j].key < R[k].key)
                k = j;
        if (k != i)
        {
            tmp = R[i];
            R[i] = R[k];
            R[k] = tmp;
        }
    }
}               

此排序的操作过程为：还是以序列为（6，3，7，5，1，4，2，9）的例子来说吧。刚开始时 i = 0，假设i = 0这个位置对应的关键字是最小的，从i+1开始，在6后面的序列中找到最小的那个记录，用 k 记下第一趟排序后目前找到的最小的关键字所在的位置，判断 k 是否等于 i，不相等，说明最小值的位置发生了变化，需要交换下R[i] 和 R[k]，此时序列为（1，3，7，5，6，4，2，9）。接着第二趟排序开始...以此类推，经过n - 1趟排序后，整个序列递增有序。

初始序列：6 3 7 5 1 4 2 ，排序过程如下所示：

selectionSort.png

堆排序

待续 O(∩_∩)O