快速排序的简单达成

发布时间：2021-11-19 11:50:41 所属栏目：PHP教程来源：互联网

导读：算法这一块是我的弱项。就以快速排序这样简单的算法，大二学完以后，就没有回顾过了。因为C中有qsort()接口，而C++中也有sort()接口。前一阵子想巩固一下基础知识，回顾了这一著名算法。因为大学学过，所以大致知道它的一个过程也就是一个递归。设给定一序

　算法这一块是我的弱项。就以快速排序这样简单的算法，大二学完以后，就没有回顾过了。因为C中有qsort()接口，而C++中也有sort()接口。前一阵子想巩固一下基础知识，回顾了这一著名算法。

　　因为大学学过，所以大致知道它的一个过程——也就是一个递归。设给定一序列arr[0...N]，首先通过arr[0]将arr[0...N]一分为二（我比较懒，不画图了，大家将就看哈），如下：

　　__前半部分，特点：这半部分序列中元素<arr[0]__ arr[0] __后半部分，特点：这半部分序列元素>= arr[0]_　(1)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　      ↑

　　　　　　　　　　　　　　　　　　　　　pilot所在位置(是不是叫pilot的？我忘了，^_^)

　　接下来，就是递归排序前半部分和后半部分，递归终止条件就是待排序的序列长度<=1。这个过程是不是很简单？那怎么找arr[0]所在位置，换句话说，怎么把原来的序列一分为二，满足(1)给定的条件？其实，这个问题我一开始也想了好久，第一版代码写出来运行结果还是不对的，经过调试才最后运行正确。

　　这里必然要对序列进行遍历，并且遍历过程中要保持一定的要求——就是所谓的循环不变式（《算法导论》一开始就介绍这个概念了）。我们这里要满足的要求（或学术化一点叫循环不变式）可以这么描述：遍历过程中，假设现在循环变量值为i，我们要保证：

　　　　　　　　　　arr'[0]...arr'[pilot-1] < arr'[pilot] <= arr'[pilot+1]...arr'[i]　　　　　　(2)

我们这里符号用的是arr'（上撇号），这里arr'[pilot]存放的是arr[0]，采用不同符号以表示与原始序列不同了。

问题：怎么在遍历过程中，保持(2)成立？？？

　　其实，想到也不难，可能要花点心思。首先把arr[0]保存下来，放在变量pilot_value中，初始的情形如下：

　　　　　　　　____ arr[1] arr[2]...arr[N]

　　　　　　　　 ↑　　　↑

　　　　　　　　pilot　　i

因为arr[0]保存下来了，所以pilot所指的位置可以认为是没有意义了，所以我在画了一条线——表示这可以看做是空的。遍历从i=1开始，遍历的目的是把所有小于pilot_value的值放到pilot所指位置的左边（如上：初始的时候，pilot左边是没有元素）。现在我们假设循环变量到i+1了，表明前面i个元素满足(2)式要求了，现在就是移动arr[i+1]到合适位置，如下：

　　　　　　　　arr'[0]...arr'[pilot-1] < ___ <= arr'[pilot+1]...arr'[i] arr[i+1]　　　　　　　　　　　　　　　　(3)

　　　　　　　　　　　　　　　　　　　　　↑

　　　　　　　　　　　　　　　　　　　　pilot

很简单，就是比较pilot_value和arr[i+1]，两种情况咯：

　　　　　（1）若 pilot_value <= arr[i+1]，不需要做任何操作；

　　　　　（2）若pilot_value > arr[i+1]，此时：直接将pilot位置上放置arr[i]吗？那就试试看，如果这么做，就会出现如下情况：

　　　　　　　　　　　　　　arr'[0]...arr'[pilot-1] arr[i] arr'[pilot+1]...arr'[i] _____　　　　　　　　　　　　　　(4)

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　↑

　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　新的pilot

这时，pilot应该＋1，即箭头指向的位置。我们知道pilot指向的位置在遍历完成后，是要存放arr[0]（即：pilot_value）的，而此时pilot指向的是一个有意义的位置。注意(4)中最后一个位置存放的是arr[i+1]，这个位置现在存放这个值还有意义吗？显然没意义了！这时只要把arr’[pilot+1]和下划线所在位置的值换一下就好了，这样新的pilot所指向的位置就可以认为没意义了——可以看做是空的了。最后结果如下：

　　　　　　　　　　　　arr'[0]...arr'[pilot-1] arr[i] _____ arr'[pilot+2]...arr'[i]arr'[pilot+1]　　　　　　　　(5)

　　　　　　　　　　　　　　　　　　　　　　　　　　　↑

　　　　　　　　　　　　　　　　　　　　　　　　　新的pilot

其实现在新的pilot所指向的位置存放的值时arr[i]。(5)式显然是保持(2)式要求的。遍历完整个序列，得到最后的pilot，然后把pilot_value放到这个位置上，就可以了。最后查找pilot并整理序列以满足(2)式要求的函数实现如下（采用模板）：

template <typename Type>
int find_pilot(Type arr[], int iLen) {
    int my_pilot = 0;
    int pilot_value = arr[0];

    for (int i = 1; i != iLen; ++i) {
        if (pilot_value > arr[i]) {
            // pilot位置上放上arr[i]
            arr[my_pilot] = arr[i];

            // pilot自增
            my_pilot++;

            // pilot和arr[i]交换，以保证pilot指向的值无意义。
            std::swap(arr[i], arr[my_pilot]);
        }
    }

    arr[my_pilot] = pilot_value;
    return my_pilot;
}

快速排序就是先通过上述函数将原始序列按pilot分为两个子序列，然后针对两个子序列分别递归调用，代码如下：

template <typename Type>
void quick_sort(Type arr[], int iLen) {
    if (iLen <= 1) {
        return;
    }

    int pilot = find_pilot(arr, iLen);
    quick_sort(arr, pilot);
    quick_sort(arr + pilot + 1, iLen - pilot - 1);
}

最后，我们测试代码如下：

int main() {
    std::cout << "= = = = = 快速排序算法 = = = = =" << std::endl;
    std::cout << "排序前的数组：";

    int iTestArray[10] = { 0 };
    srand((unsigned int)time(NULL));
    for (int i = 0; i != 10; ++i) {
        iTestArray[i] = rand() % 100;
        std::cout << iTestArray[i] << " ";
    }
    std::cout << std::endl;

    quick_sort(iTestArray, 10);

    std::cout << "排序后的数组：";
    for (int i = 0; i != 10; ++i) {
        std::cout << iTestArray[i] << " ";
    }
    std::cout << std::endl;

    return 0;
}

（编辑：云计算网_泰州站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

php批量命名文件技巧	php读取文件内容几种正
php中读取大文件实现方	php打开远程文件的方法