《恋上数据结构与算法》排序（六）：快速排序

悠悠 2023-01-01 15:58 117阅读 0赞

> 参考 :
> 
>  *  [https://blog.csdn.net/weixin\_43734095/article/details/105156039][https_blog.csdn.net_weixin_43734095_article_details_105156039]
>  *  [https://morris131.blog.csdn.net/article/details/107444604][https_morris131.blog.csdn.net_article_details_107444604]
>  *  [https://juejin.cn/post/6844904095250120718][https_juejin.cn_post_6844904095250120718]

# 一、经典十大排序算法 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]

# 快速排序 #

*  快速排序（Quick Sort）是对冒泡排序的一种改进，采用的是分治策略（一般与递归结合使用），以减少排序过程中的比较次数。

## 算法步骤 ##

1.  从数组中选择一个`轴点元素（pivot）`, 假设每次都选择 **索引为0的元素为轴点元素**。
2.  利用`pivot`将数组分割成`2个子数组`，**将小于pivot的元素放在pivot前面（左侧），将大于pivot的元素放在pivot后面（右侧），等于pivot的元素放哪边都可以。**
3.  递归对子序列进行前面两步操作，直到不能再分割（子序列中只剩下1个元素）。

**`快速排序的本质：逐渐将每一个元素都转换成轴点元素。`**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]

## 轴点构造 ##

对于序列 \{ 6a, 8a, 8b, 2, 6b, 4, 9, 5, 7 \} **构造轴点**：

*  首先将 0 位置的元素备份，作为**轴点元素**；

![在这里插入图片描述][20200328102810491.png]

*  最终目标是构造出**以轴点元素为中心的序列**：
    
     *  左半边是**小于轴点元素**的**序列**；
     *  右半边是**大于轴点元素**的**序列**；

如下图：

![在这里插入图片描述][2020032810343665.png]

那么如何构造呢？  
begin 为序列首位置，

*  从右往左扫描，寻找比轴点元素小的元素；  
    **找到以后**，放到 begin 位置，begin++，然后**反向寻找**；
 *  从左往右扫描，寻找比轴点元素大的元素；  
    **找到以后**，放到 end 位置，end–，然后**反向寻找**;
 *  当 begin == end，说明左右都扫描完了，此时**将一开始备份的轴点元素放到中间**。

这个过程有点迷惑性，需要先从右往左找，找到以后再从左往右，不断循环这个过程，直到**把所有比轴点元素小的元素放到左半部分**，**把所有比轴点元素大的元素放到右半部分**，才算完成这个轴点的构造。

比如:

*  将`6`作为轴点，备份一份。

![img][]

*  从`右边（end）`开始扫描数组。
 *  扫描`7`，大于`6a`，执行`end--`即可。

![img][img 1]

*  扫描`5`，小于`6a`，用`5`覆盖`6a`的位置，`begin++`。

![img][img 2]

*  下一步，从`左边（begin）`继续扫描。
 *  扫描`8a`，大于`6a`，用`8a`覆盖`5`的位置，`end--`。

![img][img 3]

*  下一步，从`右边（end）`继续扫描
 *  扫描`9`，大于`6a`，执行`end--`，不做其他操作。

![img][img 4]

*  扫描`4`，小于`6a`，用`4`覆盖`8a`的位置，`begin++`。

![img][img 5]

*  扫描`8b`，大于`6a`，用`8b`覆盖`4`的位置，`end--`。

![img][img 6]

*  扫描`6b`，等于`6a`，用`6b`覆盖`8b`的位置，`begin++`。

![img][img 7]

*  扫描`2`，小于`6a`，`begin++`。

![img][img 8]

*  当发现`begin`和`end`重叠，则轴点构造完成。将备份的`6a`，覆盖`6b`的位置。

![img][img 9]

## 构造轴点-代码实现 ##

代码中如何实现**从左往右扫描**和**从右往左扫描**的交替呢？请看代码

/** * 构造出[begin, end)范围的轴点元素 * * @param begin * @param end * @return 轴点元素的最终位置 */
        private int pivotIndex(int begin, int end) { 
            // 随机选择一个元素跟begin位置进行交换，为了降低最好时间复杂度
            swap(begin, begin + (int)(Math.random() * (end - begin)));
    
            // 备份begin位置的元素
            T pivot = array[begin];
            // end指向最后一个元素, 之前end索引指向的是arr.length
            end--;
    
            while (begin < end) { 
                while (begin < end) { 
                    if (cmp(array[end], pivot) > 0) {    // 右边元素 > 轴点元素
                        end--;
                    } else {     // 右边元素 <= 轴点元素
                        array[begin++] = array[end];
                        break;
                    }
                }
                while (begin < end) { 
                    if (cmp(array[begin], pivot) < 0) {  // 左边元素< 轴点元素
                        begin++;
                    } else {     // 左边元素 >= 轴点元素
                        array[end--] = array[begin];
                        break;
                    }
                }
            }
    
            // 将轴点元素放入最终的位置
            array[begin] = pivot;
            // 返回轴点元素的位置
            return begin; // begin==end
        }
    }

## 构造轴点-优化 ##

在`轴点左右元素数量比较均匀`的情况下，同时也是**最好情况**：

*  T(n) = 2 ∗ T(n/2) + O(n) = O(nlogn)

如果`轴点左右元素数量极度不均匀`，**最坏情况**：

*  T(n) = T(n − 1) + O(n) = O(n2)

为了降低最坏情况的出现概率，一般采取的做法是：

*  **`随机选择轴点元素`**  
    可以在备份轴点元素前，将 begin 位置的元素与序列中的随机元素交换一下。

// 为了降低最坏情况(O(n^2)的时间复杂度)的出现概率，随机选择一个元素跟begin位置进行交换
    swap(begin, begin + (int)Math.random()*(end - begin));
    
    // 备份begin位置的元素
    T pivot = array[begin];
    .....

## 与轴点相等的元素 ##

*  如果序列中的所有元素都与轴点元素相等，**利用上面的算法实现**，轴点元素可以将序列分割成 2 个均匀的子序列  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70]

**思考：把上面的代码中，cmp 位置的判断分别改为 ≤、≥ 会起到什么效果？**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]

后果：

*  轴点元素分割出来的子序列极度不均匀
 *  导致出现最坏时间复杂度 O(n2)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 1]

# 快速排序完整代码 #

/** * Description: 实现快速排序 * * @author guizy * @date 2021/1/3 20:04 */
    @SuppressWarnings("all")
    public class QuickSort<T extends Comparable<T>> extends Sort<T> { 
    
        @Override
        protected void sort() { 
            sort(0, array.length);
        }
    
        /** * 对[begin, end)范围的元素进行快速排序 * end - begin 就是元素个数, 因为元素范围为 0 - arr.length * * @param begin * @param end */
        private void sort(int begin, int end) { 
            // 至少要有两个元素, 才能进行快排
            if (end - begin < 2) return;
    
            // 确定轴点位置
            int mid = pivotIndex(begin, end);
            // 对子序列进行快速排序
            sort(begin, mid);
            sort(mid + 1, end);
        }
    
        /** * 构造出[begin, end)范围的轴点元素 * * @param begin * @param end * @return 轴点元素的最终位置 */
        private int pivotIndex(int begin, int end) { 
            // 为了降低最坏情况(O(n^2)的时间复杂度)的出现概率，随机选择一个元素跟begin位置进行交换
            swap(begin, begin + (int)(Math.random() * (end - begin)));
    
            // 备份begin位置的元素
            T pivot = array[begin];
            // end指向最后一个元素, 之前end索引指向的是arr.length
            end--;
    
            while (begin < end) { 
                while (begin < end) { 
                    if (cmp(array[end], pivot) > 0) {    // 右边元素 > 轴点元素
                        end--;
                    } else {     // 右边元素 <= 轴点元素
                        array[begin++] = array[end];
                        break;
                    }
                }
                while (begin < end) { 
                    if (cmp(array[begin], pivot) < 0) {  // 左边元素< 轴点元素
                        begin++;
                    } else {     // 左边元素 >= 轴点元素
                        array[end--] = array[begin];
                        break;
                    }
                }
            }
    
            // 将轴点元素放入最终的位置
            array[begin] = pivot;
            // 返回轴点元素的位置
            return begin; // begin==end
        }
    }

public class QuickSort{ 
    	public static void main(String[] args) { 
    		int[] array = { 5, 3, 2, 0, 6, 9, 4};
    		sort(0, array.length, array);
    		for (int i = 0; i < array.length; i++) { 
    			System.out.print(array[i] + "_");
    		}
    	}
    
    	private static void sort(int begin, int end, int[] array) { 
    		if (end - begin < 2) return; // 必须要大于两个元素, 才能进行快排
    		// 确定轴点的位置
    		int mid = pivotIndex(begin, end, array);
    		sort(begin, mid, array);
    		sort(mid + 1, end, array);
    	}
    
    	
    	private static int pivotIndex(int begin, int end, int[] array) { 
    
    		// 为了降低最坏情况(O(n^2)的时间复杂度)的出现概率，随机选择一个元素跟begin位置进行交换
            swap(begin, begin + (int) (Math.random() * (end - begin)), array);
    
    		// 默认将第一个元素作为轴点元素, 备份
    		int pivot = array[begin];
    		end--; // end执行数组的最后一个元素
    
    		while(begin < end) { 
    
    			// 从右往左扫描
    			while(begin < end) { 
    				if (pivot < array[end]) { 	// 右边元素 > 轴点元素
    					end--;
    				} else { 	// 右边元素 <= 轴点元素
    					array[begin++] = array[end];
    					// 改变方向, 从左往右扫描
    					break;
    				}
    			}
    
    			// 从左往右扫描
    			while(begin < end) { 
    				if (pivot > array[begin]) { 	// 左边元素 < 轴点元素
    					begin++;
    				} else { 	// 左边元素 >= 轴点元素
    					array[end--] = array[begin];
    					// 改变方向, 从右往左扫描
    					break;
    				}	
    			}
    		}
    
    		// 将当初备份轴点元素, 放入轴点的位置
            array[begin] = pivot;
    
            // 返回轴点元素的位置
            return begin; // begin==end
    	}
    
    	private static void swap(int v1, int v2, int[] array) { 
    		int temp = array[v1];
    		array[v1] = array[v2];
    		array[v2] = temp;
    	}
    }

生成 10000000 个取值在\[1, 10000000\] 的随机数进行排序：

【QuickSort】
    稳定性：false 	耗时：6.92s(6920ms) 	比较：2.90亿	 交换：638.57万
    ------------------------------------------------------------------
    【MergeSort】
    稳定性：true 	耗时：12.933s(12933ms) 	比较：2.20亿	 交换：0
    ------------------------------------------------------------------
    【HeapSort】
    稳定性：false 	耗时：16.169s(16169ms) 	比较：4.35亿	 交换：1000.00万
    ------------------------------------------------------------------

# 复杂度与稳定性 #

**快速排序的复杂度与稳定性**：

*  最好、平均时间复杂度：`O(nlogn)`
 *  最坏时间复杂度：`O(n^2)`
 *  由于**递归**调用的缘故，空间复杂度：O(logn)
 *  属于 **`不稳定排序`**

[https_blog.csdn.net_weixin_43734095_article_details_105156039]: https://blog.csdn.net/weixin_43734095/article/details/105156039
[https_morris131.blog.csdn.net_article_details_107444604]: https://morris131.blog.csdn.net/article/details/107444604
[https_juejin.cn_post_6844904095250120718]: https://juejin.cn/post/6844904095250120718
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70]: /images/20221120/df7b576685d0438d8831f38fb6a7fee4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 1]: /images/20221120/379c0c70ac74452bad6090a1b5a25e8e.png
[20200328102810491.png]: /images/20221120/e0a9e350a69744d3bc3302586fae2f45.png
[2020032810343665.png]: /images/20221120/b265a734f1b145d2afff86ee885330d9.png
[img]: /images/20221120/9786c25fc57c4ae6bef1b245b8f1a737.png
[img 1]: /images/20221120/df91bcd33a104c11a2ece93971f07a56.png
[img 2]: /images/20221120/12ed6103ab7849d69832249e2a423c47.png
[img 3]: /images/20221120/108c2e14556f42b1a78fc131e021e02a.png
[img 4]: /images/20221120/f3a32466d2734f75b203167d8248d225.png
[img 5]: /images/20221120/99f3c9e56f274228ac26746ee948ec50.png
[img 6]: /images/20221120/1fac7e0e62024d5a8758c1d7bf2aad48.png
[img 7]: /images/20221120/d733553536134cd488cc0c1d9e73e52f.png
[img 8]: /images/20221120/745f2a8f109246a09965addf72b41ce6.png
[img 9]: /images/20221120/17bb6d5fa82a4e4da8aa4e421415015c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70]: /images/20221120/61c7141d5e2043ec991d486a07dda227.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM3OTg5OTgw_size_16_color_FFFFFF_t_70 2]: /images/20221120/bd78f881d1f54aef9ad2c8b6b1fc6842.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MzczNDA5NQ_size_16_color_FFFFFF_t_70 1]: /images/20221120/3991ff585ef5494dafc851c48e3bb7ec.png