排序算法

　　终于狠下心来要好好学习下算法了，买了经典名作：算法导论，另外在网易公开课上收看MIT 的 Intorduction to Algorithms，为了正握的更透彻，也为了方便以后复习，把掌握的内容记录下来。

　　本期的内容为排序算法（sort algorithms）。

插入排序（Insertion Sort）

　　插入排序正如名字一样好理解。假设需要排序的数组为 array[0...n-1]，从数组的第二个数开始，向后进行遍历，每拿到一个数，把这个数插到它前面已经排好序的数组中的适当的位置。这里有一些问题需要说明：

怎样保证前面的数组是有序的？

　　从第二个数开始操作，因为它的前面只有一个数，肯定是有序的，插入第二个数后能保证前两个数是有序的。插入第三个数时，前两个数是有序的，把第三个数插入到适当的位置后，保证前三个数是有序的。依次类推，每次插入时，都能保证前面的数是有序的。这个过程的关键是从第二个数开始插入。

插入适当的位置，也就是保证插入后依然是有序的，那么操作过程是怎样的呢？

　　这里用个例子来说明。array[5] = {3, 2, 4, 6 1}

　　　　　　　0　　1　　2　　3　　4

　　begin: 3　　2　 4 6　　1

　　step1: 2　　3　　4　　6　　1

　　step2:　 2　　3　　4　　6　　1

　　step3:　 2　　3　　4　　6　　1

　　step4:　 1　　2　　3　　4　　6

　　橙色的为已经排好序的，绿色的为还未排序的，蓝色加粗的是将要进行插入的数字。从图中可以看到，每次插入时（按升序），假设为array[i]，令 j 从 i - 1到0为顺序，直到找出比array[i]小的数。在这个过程中，array[j] = array[j-1]，右移数组里的数。找到数之后，将array[i]放在相应的位置。话说的有点混乱，直接上代码。

void insertionSort(int array[], int n)
{
    for (int i = 1; i < n; i++)
    {
        int temp = array[i];
        int j = i-1;
        while (j >= 0 && array[j] > temp)
        {
            array[j+1] = array[j];
            j--;
        }
        array[j+1] = temp;
    }
}

插入排序是比较慢的排序方法，复杂度为Ο(n²).

归并排序（Merge Sort)

归并排序采用分治的思想，分治的思想一般都可以使用递归的方法，归并排序也可以采用递归的方法。

归并排序思路为：

将待排序的数组首先分成最小的数组，也就是每个数组只有一个数
只有一个数的数组是排好序的，然后将排好序的这两个数组进行合并，变成具有两个数的已排好序的数组。
两个数的排好序的数组再进行合并，最终完成真个数组的排序。

可以写成伪代码为：

　　Merge Sort : array[0....n-1]

If n = 1, done
递归排序 array[1...(n/2)] 和 array[(n/2)+1, n]
合并array[1...(n/2)] 和 array[(n/2)+1, n]

这样看来，这个算法也比较简单了，第三步的合并方法是什么样的呢？其实也不难，不过需要另开辟空间，来存储两个一排好序的数组进行合并后的结果之后再转存到数组A中。依然上代码：

void merge(int array[], int begin, int mid, int last)
{
    int left = begin, right = mid + 1;
    int *arrayTemp = (int*)malloc(sizeof(int)*(last-begin+1));//存放结果的临时数组
    int i = 0;
    while (1)
    {
        if (left > mid)//如果左半部分数组全都复制完，将右半部分数组的复制
        {
            while(right<=last)
            {
                arrayTemp[i++]=array[right++];
            }
            break;
        }
        if (right > last)//如果右半部分数组复制完，将左半部分数组复制
        {
            while(left<=mid)
            {
                arrayTemp[i++]=array[left++];
            }
            break;
        }
        if (array[left] < array[right])
        {
            arrayTemp[i++] = array[left++];
        }
        else
        {
            arrayTemp[i++] = array[right++];
        }
    }

    for (i = 0; i < (last - begin + 1); i++)//将临时数组中的数写会到原数组
    {
        array[begin+i] = arrayTemp[i];
    }
}

void mergeSort(int array[], int begin, int last)//调用这个函数,begin和last均为下标
{
    if (begin < last)
    {
        mergeSort(array, begin, (begin+last)/2);
        mergeSort(array, (begin+last)/2 + 1, last);
        merge(array, begin, (begin+last)/2, last);
    }
}

归并排序的时间复杂度为Ο(n*log₂n).

作者：viczzx 出处：http://www.cnblogs.com/zixuan-zhang 欢迎转载，也请保留这段声明。谢谢！