理解快速排序算法的排序过程

水深无声 2022-06-01 11:26 340阅读 0赞

## 1，快速排序算法大概 ##

（1）*快速排序（quick sort）也叫分区排序，是目前应用最广泛的排序算法。在标准C++类库中排序程序被称为qsort，因为快速排序是其实现中最基本的算法。*  
（2）*排序算法的优点：好的快速排序算法在大多数计算机上运行得都比其他排序算法快，而且快速排序算法在空间上只使用一个小的辅助栈，其内部的循环也很小，另外快速排序算法也很容易实现，可以处理多种不同的输入数据，许多情况下它所消耗的资源也比其他排序算法小。*  
（3）*快速排序的注意点：快速排序是一种不稳定的排序方法，即对于排序码相同的元素，排序后可能会颠倒次序。*

## 2，快速排序的实现过程 ##

（1）**整体思路：**  
*其基本思想是任取待排序元素序列中的某个元素（例如取第一个元素）作为基准，按照该元素的排序码大小，将整个元素序列划分为左右两个子序列：左侧子序列中的排序码都小于基准元素的排序码，右侧子序列中所有元素的排序码都大于或等于基准元素的排序码。基准元素则排在两个子序列中间（这也是该元素最终应安放的位置）。然后分别对这两个子序列重复实行上述方法（递归过程），直到所有元素都排在相应位置上为止。*

（2）**思路中的隐含意思**  
通过思路可以知道，快速排序也叫分区排序的原因。快排的目的就是用一个基准数据对整个待排序的数列“分区”，左区都小于基准，右区都大于基准。那么这就会隐含着一个问题，我们只要达到分区的目的就可以，而不在乎过程；而想把一个数列分出上述符合要求的数列，其过程肯定不唯一，这也就意味着快速排序算法的实现方式不唯一。下面是摘自网友的三种实现方式：

**1>方式一：**设置两个“哨兵”从序列的两端同时寻找小于基准值和大于基准值得元素，然后交换，最终实现按基准值分区的目的。  
原文链接：[http://bbs.ahalei.com/forum.phpmod=viewthread&tid=4419&page=1\#pid37543][http_bbs.ahalei.com_forum.phpmod_viewthread_tid_4419_page_1_pid37543]

**2>方式二：**也是从两端进行，但是不像方式一那样同时进行，而是先在右端找到小于基准值得与基准值交换，然后再从左端找到大于基准值的元素填补刚才右端的那个位置，最终也是实现了按基准值分区的目的。  
原文链接：  
[http://blog.csdn.net/morewindows/article/details/6684558][http_blog.csdn.net_morewindows_article_details_6684558]

**3>方式三：从一端进行，最终也是为了实现分区的目的。因为这里我主要是实现此方式，所以下面会有详细的介绍。**

（3）**方式三的具体实现过程**  
这里结合具体的例子认识其过程，如下面一个无序数列：  
![数据序列][SouthEast]

1>首先选择21（也就是第一个元素）作为基准元素，我们的目的是把大于21的元素都挪到整个序列的右半部分，把小于21的元素都挪到整个序列的左半部分。  
按照方式3，也就是从一端进行的方式，应该怎么做呢？

2>可以先忽略21这个基准值，我们从第二个元素开始和21比较，优先找小于21的元素，把找到的小于21的元素和第二个位置交换，然后继续寻找小于21的元素，找到后再与第3个元素交换，这样遍历到数列的末尾后小于21的元素就会集中在前半部分，具体图解如下：  
![这里写图片描述][SouthEast 1]

3>经过一个循环的交换，最终左边除基准值外，其他元素都小于基准值了，最后我把基准值调整到中间去，也就是和最后那个小于基准值的元素的位置交换，图解如下：  
![这里写图片描述][SouthEast 2]  
这样，经过最后一步调整，实现了第一轮分区，之后再用分治的思想，递归调用这一过程，对子区做相同的处理，直到无法进一步分区为止（也就是子区长度为1）。

4>从图解中可以看出，原来是25 25\*的顺序，最终变成了25\* 25的顺序，也就是说，相同的关键码，在排序中可能不会保持原来的顺序，这也就体现了快速排序算法的不稳定性。

## 3，快速排序算法的C++实现 ##

下面是快排的C++语言实现，主要是两个函数，一个负责每一轮的分区，一个负责递归这一过程，结合上面的图解应该不难理解：

vector<int> numbers;
    
    //函数功能，以首元素vector[low]作为基准对vector[low]——vector[high]之间的元素分区
    //函数参数，元素序列左端点，元素序列右端点
    int partition(const int low, const int high) {
        int pivotPosition = low;
        int pivot = numbers[low];       
        for (int cnt = low + 1; cnt <= high; ++cnt) {   
            if (numbers[cnt] < pivot) {
                pivotPosition++;    
                if (pivotPosition != cnt) { //避免自己与自己交换
                    swap(numbers[pivotPosition], numbers[cnt]);
                }
            }
        }
        numbers[low] = numbers[pivotPosition];
        numbers[pivotPosition] = pivot;
    
        return pivotPosition;   //返回端点位置，供之后递归使用
    }
    
    //函数功能，快速排序算法对data的data[left]——data[right]区间排序
    //函数参数，序列左端位置，序列右端位置
    void quick_sort(const int left, const int right) {
        if (left < right) { //保证元素长度序列大于1
            int pivotPositon = partition(left, right);
            quick_sort(left, pivotPositon - 1); //对左侧序列做同样处理
            quick_sort(pivotPositon + 1, right);    //对右侧序列做同样处理
        }
    }

上面只是给出了算法实现的两个函数，通过调用第二个函数，即可实现快速排序。

## 4，排序性能测试：快排 VS 冒泡 ##

1>快速排序到底有多快速？当然可以分析其时间及空间复杂度来确定此算法的优劣。这里我们试着把他与我们熟知的冒泡排序做一个程序测试，以认识快排的性能！

2>测试思路：随机产生1000个1——1000之间的随机数，分别记录快排和冒泡排序执行过程的时间，然后输出并做一个比较。

**3>新增函数：简单的冒泡排序函数和随机数生成函数。**  
冒泡排序函数：

//函数功能，冒泡排序算法对指定序列升序排序
    //函数参数，NULL
    void bubble_sort() {
        bool check = true;
        while (check) {
            check = false;
            for (auto cnt = numbers.begin(); (cnt + 1) != numbers.end(); ++cnt) {
                if (*cnt > *(cnt + 1)) {
                    swap(*cnt, *(cnt + 1));
                    check = true;
                }
            }
        }
    }

随机数生成函数：

//函数功能，随机产生amount个start——end内的随机数并存入指定容器
    //函数参数，随机数范围起点，随机数范围终点，随机数生成数量
    void produceRandomNumbers(const int start, const int end, const int amount) {
        srand((unsigned)time(NULL));
        for (int cnt = 1; cnt <= amount; ++cnt) {
            numbers.push_back(start + (rand() % (end - start)));
        }
    }

主测试函数：

int main()
    {
        time_t c_start, c_end;
        produceRandomNumbers(1, 1000, 1000);
    
        快速排序测试
        //c_start = clock();
        //quick_sort(0, 999);
        //c_end = clock();
    
        //冒泡排序测试
        c_start = clock();
        bubble_sort();
        c_end = clock();
    
        cout << "排序使用时间是：" << difftime(c_end, c_start) << "ms" << endl;
    
        for (auto cnt = numbers.cbegin(); cnt != numbers.cend(); ++cnt) {
            cout << *cnt << " ";
        }
    
        system("pause");
        return 0;
    }

测试结果：  
冒泡排序：大约是2s  
![这里写图片描述][SouthEast 3]

快速排序：2毫秒  
![这里写图片描述][SouthEast 4]  
千倍的速度差距！

## 5，整个程序源码 ##

下载链接：  
链接：[https://pan.baidu.com/s/1hundcBa][https_pan.baidu.com_s_1hundcBa] 密码：md5y

## 6，写在最后 ##

快速排序还有许改进，C++标准库中的qsort就是一个例子，通过与其他算法的结合，可以使快速排序的性能更佳。之后也会再进一步探究梳理。也希望大家可以一块交流，指出不当之处。

参考资料：《数据结构》殷人昆/相关博文

[http_bbs.ahalei.com_forum.phpmod_viewthread_tid_4419_page_1_pid37543]: http://bbs.ahalei.com/forum.phpmod=viewthread&tid=4419&page=1#pid37543
[http_blog.csdn.net_morewindows_article_details_6684558]: http://blog.csdn.net/morewindows/article/details/6684558
[SouthEast]: /images/20220601/3e5cff99f1d947088c9d85fc508ad3f7.png
[SouthEast 1]: /images/20220601/87b718c05a0341909c0f8cc4c2ee8899.png
[SouthEast 2]: /images/20220601/9d15ab7741404bb4bd5f9cce5c7ac15a.png
[SouthEast 3]: /images/20220601/973ba0628c9f44f296cee9e17ade61c7.png
[SouthEast 4]: /images/20220601/07104f2d86074ee7bd1fb7019dcac113.png
[https_pan.baidu.com_s_1hundcBa]: https://pan.baidu.com/s/1hundcBa