iOS 算法-快排和希尔排序

前天写了关于 冒泡排序、插入排序和选择排序的实现，下面小编在本文中讲述下：快速排序和二分法排序的过程和具体实现吧。

快速排序

• 快排实现思路

快排的基本实现思路和原则：

（1）先从数列中取出一个数作为基准数。

（2）分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。

（3）再对左右区间重复第二步，直到各区间只有一个数。

• 快排实例讲述

下面以一个实例讲述：

把第一个数字 4 看做是 key 来作为分隔区域来进行比较。

（1）在 p[9] 和 4 比较后小于 4，就与 4 变换位置
（2）接着 p[1] 和 4 比较后大于 8，就和 4 变换位置
（3）一次类推下去，在第一次变换位置就实现下列的情况

如图：

• 快排实现代码

根据上面讲解，代码实现如下：

void quickSort (int *p, int l, int r) {
    if (l < r) {
        //设置最左边的第一数字作为 key 值
        int i = l, j = r, x = p[i];
        while (i < j) {
            //循环从左边进行与 key 比较
            while (i < j && p[j] >= x)
                j--;
            if (i < j)
                p[i++] = p[j];
            
            //循环从右边进行与 key 比较
            while (i < j && p[i] < x)
                i++;
            if (i < j)
                p[j--] = p[i];
        }
        
        //进行 key 的设置，然后调用递归实现 quick sort 排序
        p[i] = x;
        quickSort(p, l, i-1);
        quickSort(p, i+1, r);
    }
}

希尔排序

• 希尔排序实现思路

希尔排序基本思想是：先将整个待排元素序列分割成若干个子序列（由相隔某个“增量”的元素组成的）分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。

因为直接插入排序在元素基本有序的情况下（接近最好情况），效率是很高的，因此希尔排序在时间效率上比前两种方法有较大提高。

• 希尔排序实例讲述

下面以 数组：4, 8, 6, 65, 45, 988, 34, 12, 2, 3 位置：

第一次开始分组： 10/5 分为 5 组，如下图：

经过再次分组实现： 5/2 分为 2 组，如下图：

经过再次分组实现： 2/2 分为 1 组，如下图：

经过再次分组实现： 1/2 分为 0 组，如下图：

• 希尔排序代码实现如下：

void shellSort (int *p, int length) {
    int gap;
    for (gap = length/2; gap > 0; gap /= 2)
        for (int j = gap; j < length;  j++) {
            if (p[j] < p[j - gap]) {
                int temp = p[j];
                int k = j - gap;
                while (k >= 0 && p[k] > temp) {
                    p[k + gap] = p[k];
                    k -= gap;
                }
                p[k + gap] = temp;
            }
        }
}