排序算法第四讲 --- 快速排序(Python、C++、C)

川长思鸟来 2023-02-23 08:27 138阅读 0赞

**排序算法系列目录**

[排序算法第一讲 — 冒泡排序(Python、C++、C)][_ _Python_C_C]  
  [排序算法第二讲 — 选择排序(Python、C++、C)][_ _Python_C_C 1]  
  [排序算法第三讲 — 插入排序(Python、C++、C)][_ _Python_C_C 2]  
  [排序算法第四讲 — 快速排序(Python、C++、C)][_ _Python_C_C 3]  
  [排序算法第五讲 — 希尔排序(Python、C++、C)][_ _Python_C_C 4]  
  [排序算法第六讲 — 归并排序(Python、C++、C)][_ _Python_C_C 5]

--------------------

**题目描述：**

给你一个整数数组 nums，请你将该数组采用快速排序方式进行升序排列。  
![quickSort.gif][]

**输入示例：** `[1,8,6,2,5,4,9,3,7]`  
**输出示例：** `[1,2,3,4,5,6,7,8,9]`

--------------------

**解题思路:**

快速排序使用分治法来把一个串（list）分为两个子串（sub-lists）。具体算法描述如下：

*  从数列中挑出一个元素，称为 “基准”（pivot）；
 *  重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
 *  递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

**栗子描述：**

来源于：[快速排序][Link 1]

假设我们现在对 `"6 1 2 7 9 3 4 5 10 8"` 这个10个数进行排序。首先在这个序列中随便找一个数作为基准数。为了方便，就让第一个数6作为基准数吧。接下来，需要将这个序列中所有比基准数大的数放在6的右边，比基准数小的数放在6的左边，类似`3 1 2 5 4 6 9 7 10 8`  
这种排列。那要如何做到呢？

方法：  
  分别从初始序列`"6 1 2 7 9 3 4 5 10 8"`两端开始" 探测 "。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量  i i i 和  j j j，分别指向序列最左边和最右边。刚开始的时候让 i i i指向序列的最左边(即 i = 1 i=1 i=1)，指向数字6。让哨兵 j j j指向序列的最右边(即  j = 10 j=10 j=10)，指向数字8。

首先 j j j开始出动。因为此处设置的基准数是最左边的数，所以需要让 j j j先出动，这一点非常重要（请自己想一想为什么）。 j j j一步一步地向左挪动（即 j − − j-- j−−），直到找到一个小于6的数停下来。接下来 i i i再一步一步向右挪动（即 i + + i++ i\+\+），直到找到一个数大于6的数停下来。最后 j j j停在了数字5面前， i i i 停在了数字7面前。

现在交换 i i i和 j j j所指向的元素的值。交换之后的序列为`6 1 2 5 9 3 4 7 10 8`

到此，第一次交换结束。接下来开始 j j j继续向左挪动。他发现了4（比基准数6要小，满足要求）之后停了下来。 i i i也继续向右挪动的，他发现了9（比基准数6要大，满足要求）之后停了下来。此时再次进行交换，交换之后的序列为`6 1 2 5 4 3 9 7 10 8`

第二次交换结束，“探测"继续。 j j j 继续向左挪动，他发现了3（比基准数6要小，满足要求）之后又停了下来。 i i i 继续向右移动，糟啦！此时  i i i 和  j j j 相遇了， i i i 和  j j j 都走到3面前。说明此时” 探测 "结束。我们将基准数6和3进行交换。交换之后的序列为`3 1 2 5 4 6 9 7 10 8`

到此第一轮“探测”真正结束。此时以基准数6为分界点，6左边的数都小于等于6，6右边的数都大于等于6。回顾一下刚才的过程，其实 j j j的使命就是要找小于基准数的数，而 i i i的使命就是要找大于基准数的数，直到  i i i 和  j j j 碰头为止。

OK，解释完毕。现在基准数6已经归位，它正好处在序列的第6位。此时我们已经将原来的序列，以6为分界点拆分成了两个序列，左边的序列是`“3 1 2 5 4”`，右边的序列是`“9 7 10 8”`。接下来还需要分别处理这两个序列。因为6左边和右边的序列目前都还是很混乱的。不过不要紧，我们已经掌握了方法，接下来只要模拟刚才的方法分别处理6左边和右边的序列即可。现在先来处理6左边的序列现吧。

如果你模拟的没有错，调整完毕之后的序列的顺序应该是`2 1 3 5 4`

最终得到正确的排序结果：`1 2 3 4 5 6 7 8 9 10`

--------------------

**代码：**

Python写法：

class Solution(object):
        def solution(self,  nums):
            if len(nums) < 2:
                return nums
            else:
                tmp = nums[0]
                less = [num for num in nums[1:] if num <= tmp]
                big = [num for num in nums[1:] if num > tmp]
                return self.solution(less) + [tmp] + self.solution(big)

C++写法：

#include<iostream>
    using namespace std;
    
    int a[100],n;  //定义全局变量
    
    void quicksort(int left, int right) {
        
    	int i, j, t, temp;
    	if(left > right)
    		return;
        temp = a[left];  //temp中存的就是基准数
        i = left;
        j = right;
        while(i != j) {
          //顺序很重要，要先从右边开始找
        	while(a[j] >= temp && i < j)
        		j--;
        	while(a[i] <= temp && i < j) //再找右边的
        		i++;       
        	if(i < j)    //交换两个数在数组中的位置
        	{
        
        		t = a[i];
        		a[i] = a[j];
        		a[j] = t;
        	}
        }
        //最终将基准数归位
        a[left] = a[i];
        a[i] = temp;
        quicksort(left, i-1);  //继续处理左边的，这里是一个递归的过程
        quicksort(i+1, right); //继续处理右边的 ，这里是一个递归的过程
    }
    int main() {
        
    	int i;
        
    	cin >> n;                //读入数据
    
    	for(i = 1; i <= n; i++)
    		cin >> a[i];
    
        quicksort(1, n);         //快速排序调用
        
    	
        for(i = 1; i <= n; i++)  //输出排序后的结果
        	cout << a[i] <<" ";
    
        cout << "\n";
        return 0;
    }

C语言：

#include <stdio.h>
    
    int a[100],n;  //定义全局变量
    
    void quicksort(int left, int right) {
        
    	int i, j, t, temp;
    	if(left > right)
    		return;
        temp = a[left];  //temp中存的就是基准数
        i = left;
        j = right;
        while(i != j) {
          //顺序很重要，要先从右边开始找
        	while(a[j] >= temp && i < j)
        		j--;
        	while(a[i] <= temp && i < j) //再找右边的
        		i++;       
        	if(i < j)    //交换两个数在数组中的位置
        	{
        
        		t = a[i];
        		a[i] = a[j];
        		a[j] = t;
        	}
        }
        //最终将基准数归位
        a[left] = a[i];
        a[i] = temp;
        quicksort(left, i-1);  //继续处理左边的，这里是一个递归的过程
        quicksort(i+1, right); //继续处理右边的 ，这里是一个递归的过程
    }
    int main() {
        
    	int i;
        //读入数据
    	scanf("%d", &n);
    
    	for(i = 1; i <= n; i++)
    		scanf("%d", &a[i]);
        quicksort(1, n);   //快速排序调用
        
    	//输出排序后的结果
        for(i = 1; i <= n; i++)
        	printf("%d ", a[i]);
    
        printf("\n");
        return 0;
    }

--------------------

**题目来源：**

[http://lab.csdn.net/\#/question/38?tagId=16][http_lab.csdn.net_question_38_tagId_16]

[_ _Python_C_C]: https://blog.csdn.net/weixin_43283397/article/details/107119915
[_ _Python_C_C 1]: https://blog.csdn.net/weixin_43283397/article/details/107139196
[_ _Python_C_C 2]: https://blog.csdn.net/weixin_43283397/article/details/107146712
[_ _Python_C_C 3]: https://blog.csdn.net/weixin_43283397/article/details/107160931
[_ _Python_C_C 4]: https://blog.csdn.net/weixin_43283397/article/details/107242305
[_ _Python_C_C 5]: https://blog.csdn.net/weixin_43283397/article/details/107246548
[quickSort.gif]: https://www.runoob.com/wp-content/uploads/2019/03/quickSort.gif
[Link 1]: https://blog.csdn.net/adusts/article/details/80882649?ops_request_misc=&request_id=&biz_id=102&utm_term=%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F&utm_medium=distribute.pc_search_result.none-task-blog-2~all~sobaiduweb~default-0-80882649
[http_lab.csdn.net_question_38_tagId_16]: http://lab.csdn.net/#/question/38?tagId=16