漫画：什么是快速排序？

Dear 丶 2023-07-11 15:28 24阅读 0赞

> 快速排序是从冒泡排序演变而来的算法，但是比冒泡排序要高效得多，所以叫做快速排序

> 最好先弄清楚荷兰国旗问题，这样比较好理解

# 快速排序采用了分治法 #

> 思想：从一组中选出一个数来，将小于这个数的放在左边，大于这个数的放在右边。这个样每次选出一个数来，经过N次以后每个数就是有序的

同冒泡排序一样，快速排序也属于交换排序，通过元素之间的比较和交换位置来达到排序的目的。

不同的是，冒泡排序是在每一轮只把一个元素冒泡的数列的一端，而快速排序**在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列的一边，比它小的元素移动到数列的另一边，从而把数列拆解成了两个部分**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]  
这种思路就叫做分治法。

每次把数列分成两部分，究竟有什么好处呢？

假如给定8个元素的数列，一般情况下冒泡排序需要比较8轮，每轮把一个元素移动到数列一端，时间复杂度是O（n^2）。

而快速排序的流程是什么样子呢？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]  
如图所示，在分治法的思想下，原数列在每一轮被拆分成两部分，每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。

这样一共需要多少轮呢？平均情况下需要logn轮，因此快速排序算法的平均时间复杂度是 O（nlogn）。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]

# 元素的移动 #

选定了基准元素以后，我们要做的就是把其他元素当中小于基准元素的都移动到基准元素一边，大于基准元素的都移动到基准元素另一边。

具体如何实现呢？有两种方法：

*  挖坑法
 *  指针交换法

## 挖坑法 ##

给定原始数列如下，要求从小到大排序  
![在这里插入图片描述][20200310133225371.png]  
首先，我们选定基准元素Pivot，并且记住这个位置index，这个位置相当于一个"坑"。并且设置两个指针left和right，指向数列的最左和最右两个元素；  
![在这里插入图片描述][20200310161928793.png]  
接下来，从right指针开始，把指针指向的元素和基准元素做比较。如果比privot大，则right指针向左移动；如果比privot小，把right所指向的元素填入坑中。

在当前数列中，1<4，所以把1填入基准元素所在位置，也就是坑的位置。这时候，元素1本来的位置成了新的坑。同时，left向左移一位。  
![在这里插入图片描述][20200310162145283.png]  
此时，left左边绿色的区域代表着小于基准元素的区域。

接下来，我们切换到left指针进行比较。如果left指向的元素小于pivot，则left指针向右移动；如果元素大于pivot，则把left指向的元素填入坑中。

在当前数列中，7>4，所以把7填入index的位置。这时候元素7本来的位置成为了新的坑。同时，right向左移动一位。  
![在这里插入图片描述][20200310162410729.png]  
此时，right右边橙色的区域代表着大于基准元素的区域。

下面按照刚才的思路继续排序：

8>4，元素位置不变，right左移  
![在这里插入图片描述][20200310162427632.png]  
2<4，用2来填坑，left右移，切换到left。  
![在这里插入图片描述][20200310162443847.png]  
6>4，用6来填坑，right左移，切换到right。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]  
3<4，用3来填坑，left右移，切换到left。

package com.company;
    
    public class Test_stack {
        
        public static  int  Helan(int[] array, int left, int right){
        
            int pivot = array[left]; // 初始坑
            while (left < right){
        
                while (left < right && array[right] > pivot){
         //找到右边第一个比基准元素小的元素
                    right--;  // 如果当前正在比较的元素小于等于基准元素，就跳出循环，right就是右边第一个比基准元素小[等于]的索引
                }
                if (left == right) break;   // 如果时因为left == right而跳出循环，那就直接返回
                array[left] = array[right];  // 将元素放入坑中， right成为新的坑
                while (left < right && array[left] <= pivot){
         // 找到左边第一个比基准元素大的元素
                    left++;   // 如果当前正在比较的元素大于基准元素，就跳出循环，left就是左边第一个大于基准元素的索引。
                }
                if (left == right) break;   // 如果时因为left == right而跳出循环，那就直接返回
                array[right] = array[left];  // 将元素放入坑中， left成为新的坑
            }
            // 跳出循环时，一定时因为left = right
            array[right] = pivot;
    
            return right;
        }
    
        public static  void quickSort(int[] array, int left, int right){
        
         	if (arr == null || arr.length < 2 ){
        
                return;
            }
    
    
            if (left  < right){
        
                int mid = Helan(array, left, right);
                quickSort(array, left, mid - 1);
                quickSort(array, mid + 1, right);
            }
    
        }
    
        public static void main(String[] args) {
        
            int[] arrry = {
        13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10, 11, 13, 13, 13};
    
            quickSort(arrry, 0, arrry.length - 1);
            for (int i: arrry){
        
                System.out.print(i + "\t");
            }
        }
    }

## 指针交换法 ##

[https://blog.csdn.net/zhizhengguan/article/details/104755681][https_blog.csdn.net_zhizhengguan_article_details_104755681]

package com.company;
    
    public class Test_stack {
        
        public static int[] Helan(int[]array, int start, int end){
        
            int less = start - 1;  // 小于
            int more = end + 1;
            int pivot = array[start];  // 取第一个元素为基准元素
            int curr = start; // 当前正在遍历元素的下标
    
    
            // 注意：比较的是基准元素和当前元素
            // p 为基准元素, 我选择了第一个元素
            // c 为当前元素， 从开始元素到结束元素
            while (curr < more){
        
                if(array[curr] < pivot) {
        
                    swap(array, ++less, curr++);
                } else if (array[curr] > pivot) {
        
                    swap(array, --more, curr);
                } else {
        
                    curr++;
                }
            }
    
            return new int[] {
         less + 1, more - 1 };  // 返回等于pivot的边界索引。 中间就是等于pivot的数
        }
    
        public static void swap(int[] arr, int i, int j) {
        
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        public static void quickSort(int []arr, int start, int end){
        
            if (arr == null || arr.length < 2 ){
        
                return;
            }
    
            if (start >= end){
        
                return;
            }
    
            int[] mids = Helan(arr, start, end);
            quickSort(arr, start, mids[0] - 1);
            quickSort(arr, mids[1] + 1, end);
    
        }
    
    
        public static void main(String[] args) {
        
            int[] arrry = {
        13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10, 11, 13, 13, 13};
    
    
            quickSort(arrry, 0, arrry.length - 1);
            for (int i: arrry){
        
                System.out.print(i + "\t");
            }
        }
    }

https://www.jianshu.com/p/a68f72278f8f  
https://www.sohu.com/a/246785807\_684445

## 非递归实现 ##

绝大多数用递归来实现的问题，都可以用栈的方式来代替

因为我们代码中一层一层的方法调用，本身就是一个函数栈。每次进入一个新方法，就相当于入栈；每次当有方法返回，就相当于出栈。

所以，我们可以把原本的递归实现转换成一个栈实现，在栈当中存储每一次方法调用的参数  
![在这里插入图片描述][20200316161945216.png]

package com.company;
    
    import java.util.HashMap;
    import java.util.Map;
    import java.util.Stack;
    
    public class Test_stack {
        
        public static int[] Helan(int[]array, int start, int end){
        
            int less = start - 1;  // 小于
            int more = end + 1;
            int pivot = array[start];  // 取第一个元素为基准元素
            int curr = start; // 当前正在遍历元素的下标
    
    
            // 注意：比较的是基准元素和当前元素
            // p 为基准元素, 我选择了第一个元素
            // c 为当前元素， 从开始元素到结束元素
            while (curr < more){
        
                if(array[curr] < pivot) {
        
                    swap(array, ++less, curr++);
                } else if (array[curr] > pivot) {
        
                    swap(array, --more, curr);
                } else {
        
                    curr++;
                }
            }
    
            return new int[] {
         less + 1, more - 1 };  // 返回等于pivot的边界索引。 中间就是等于pivot的数
        }
    
        public static void swap(int[] arr, int i, int j) {
        
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        public static void quickSort(int []arr, int startIndex, int endIndex){
        
            if (arr == null || arr.length < 2 ){
        
                return;
            }
    
            Stack<Map<String, Integer>> stack = new Stack<Map<String, Integer>>();
            Map rootP = new HashMap();
            rootP.put("start", startIndex);
            rootP.put("end", endIndex);
            stack.push(rootP);
    
            while (!stack.isEmpty()){
         // 栈为空时结束循环
                Map<String, Integer> pindex = stack.pop();
                int start = pindex.get("start");
                int end = pindex.get("end");
                int[] p =  Helan(arr, start, end);
    
                if (start < p[0] - 1){
        
                    Map leftP = new HashMap();
                    leftP.put("start", startIndex);
                    leftP.put("end", p[0] - 1);
                    stack.push(leftP);
                }
    
                if (p[1] + 1 < end){
        
                    Map rightP = new HashMap();
                    rightP.put("start", p[1] + 1);
                    rightP.put("end", end);
                    stack.push(rightP);
                }
    
            }
    
        }
    
    
        public static void main(String[] args) {
        
            int[] arrry = {
        13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10, 11, 13, 13, 13};
    
    
            quickSort(arrry, 0, arrry.length - 1);
            for (int i: arrry){
        
                System.out.print(i + "\t");
            }
        }
    }

与刚刚递归实现的相比，代码的变动仅仅在qucikSort方法当前。该方法中引入了一个存储Map类型元素的栈，用于存储每一次交换时的起始小标和结束下标

每一次循环，都会让栈顶元素出栈，进行排序，并且按照基准元素的位置分成左右两部分，左右两部分再分别入栈。当栈为空时，说明排序已经完毕，退出循环

# 基准元素的选择 #

基准元素，用于在分治过程中以此为中心，把其他元素移动到基准元素的左右两边。

那么基准元素如何选择呢？

最简单的方式是选择数列的第一个元素：  
![在这里插入图片描述][20200306164155716.png]  
这种选择在绝大多数情况是没有问题的。但是，假如有一个原本逆序的数列，期望排序成顺序数列，那么会出现什么情况呢？  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]  
我们该怎么避免这种情况发生呢？

其实很简单，我们可以不选择数列的第一个元素，而是**随机选择一个元素作为基准元素。**  
![在这里插入图片描述][20200306170204290.png]  
这样一来，即使在数列完全逆序的情况下，也可以有效地将数列分成两部分。

当然，即使是随机选择基准元素，每一次也有极小的几率选到数列的最大值或最小值，同样会影响到分治的效果。

所以，**快速排序的平均时间复杂度是 O（nlogn），最坏情况下的时间复杂度是 O（n^2）。**

## 随机快排算法 ##

package com.company;
    
    
    import java.util.Random;
    
    public class Test_stack {
        
        public static void swap(int[] arr, int i, int j) {
        
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
    
        public static void quickSort(int []arr, int startIndex, int endIndex){
        
            if (arr == null || arr.length < 2 ){
        
                return;
            }
    
            if ( startIndex >= endIndex){
        
                return;
            }
    
    
            int random =  new Random().nextInt((endIndex - startIndex) + 1) + startIndex; //在序列中随机选取一个元素
            swap(arr, random, startIndex); // 和基准元素交换，这样基准元素就是随机的了
    
            int [] indexs = Helan(arr, startIndex, endIndex); // 返回的是相等的边界，边界索引里面[包括边界元素]不需要在进行比较了
            quickSort(arr, startIndex, indexs[0] - 1);
            quickSort(arr, indexs[1] + 1, endIndex);
        }
    
        public static int [] Helan(int []arr, int start, int end){
          //返回和基准元素相等的边界索引
            int less = start - 1;  // 小于基准元素的边界索引，
            int more = end + 1;
            int pivot = arr[start];
            int curr = start;  // 当前正在循环的元素
    
            while (curr < more){
        
                if (arr[curr] < pivot){
         // 当前元素小于基准元素
                    swap(arr, curr++, ++less);
                }else if (arr[curr] > pivot){
        
                    swap(arr, curr, --more);
                }else{
        
                    curr++;
                }
            }
            return new int[]{
        less + 1, more - 1};
        }
    
        public static void main(String[] args) {
        
            int[] arrry = {
        13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10, 11, 13, 13, 13};
    
    
            quickSort(arrry, 0, arrry.length - 1);
            for (int i: arrry){
        
                System.out.print(i + "\t");
            }
        }
    }

# golang实现 #

package main
    
    import (
    	"fmt"
    	"math/rand"
    	"time"
    )
    
    func QuickSort(arr[] int)[]int{
        
    	length := len(arr)
    	if length <= 1{
        
    		return arr
    	}else{
        
    		base := arr[0] // 第一个作为基准
    		low := make([]int, 0) //存储比我小的
    		mid := make([]int, 0) //存储与我相等
    		high := make([]int, 0) //存储比我大的
    
    		for i := 0; i < length ; i++ {
        
    			if arr[i] < base {
        
    				low = append(low, arr[i])
    			}else if arr[i] == base {
        
    				mid = append(mid, arr[i])
    			}else{
        
    				high = append(high, arr[i])
    			}
    		}
    
    		low, high = QuickSort(low), QuickSort(high)
    		return append(append(low, mid...), high...)
    	}
    }
    
    func QuickSortRandom(arr[] int)[]int{
        
    	length := len(arr)
    	if length <= 1{
        
    		return arr
    	}else{
        
    		rand.Seed(time.Now().UnixNano())
    		base := arr[rand.Intn(length)] // 随机基准
    		low := make([]int, 0)
    		mid := make([]int, 0)
    		high := make([]int, 0)
    
    		for i := 0; i < length ; i++ {
        
    			if arr[i] < base {
        
    				low = append(low, arr[i])
    			}else if arr[i] == base {
        
    				mid = append(mid, arr[i])
    			}else{
        
    				high = append(high, arr[i])
    			}
    		}
    
    		low, high = QuickSort(low), QuickSort(high)
    		return append(append(low, mid...), high...)
    	}
    }
    
    func main() {
        
        arr := []int{
        13,14,94,33,82,25,59,94,65,23,45,27,73,25,39,10, 11, 13, 13, 13}
    	fmt.Println(QuickSortRandom(arr))
    	fmt.Println(arr)
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200306163830217.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200306163855252.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200306164113529.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200310133225371.png]: https://img-blog.csdnimg.cn/20200310133225371.png
[20200310161928793.png]: https://img-blog.csdnimg.cn/20200310161928793.png
[20200310162145283.png]: https://img-blog.csdnimg.cn/20200310162145283.png
[20200310162410729.png]: https://img-blog.csdnimg.cn/20200310162410729.png
[20200310162427632.png]: https://img-blog.csdnimg.cn/20200310162427632.png
[20200310162443847.png]: https://img-blog.csdnimg.cn/20200310162443847.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200310162457858.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[https_blog.csdn.net_zhizhengguan_article_details_104755681]: https://blog.csdn.net/zhizhengguan/article/details/104755681
[20200316161945216.png]: https://img-blog.csdnimg.cn/20200316161945216.png
[20200306164155716.png]: https://img-blog.csdnimg.cn/20200306164155716.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/2020030616435665.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20200306170133867.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg==,size_16,color_FFFFFF,t_70
[20200306170204290.png]: https://img-blog.csdnimg.cn/20200306170204290.png