# Quick Sort Demo **Repository Path**: mrfu/quick-sort-demo ## Basic Information - **Project Name**: Quick Sort Demo - **Description**: 快速排序 - **Primary Language**: Java - **License**: Apache-2.0 - **Default Branch**: master - **Homepage**: None - **GVP Project**: No ## Statistics - **Stars**: 0 - **Forks**: 0 - **Created**: 2021-07-22 - **Last Updated**: 2021-07-28 ## Categories & Tags **Categories**: Uncategorized **Tags**: None ## README # Quick Sort Demo #### 介绍 **快速排序**
也是一种交换排序，通过元素之间的比较和交换位置来达到排序的目的
#### 思路 **分治法：** 在每一轮挑选一个基准元素，并让其他比它大的元素移动到数列的一边，比它小的元素移动到数列的另一边，从而把数列拆分成两部分。每一部分在下一轮又分别被拆分成两部分，直到不可再分为止。
每一轮的比较和交换，需要把数组的全部元素都遍历一遍，时间复杂度为 **O(n²)**
假如有 n 个元素，那么平均情况下需要 **logn** 轮，因此快速排序算法总体的平均时间复杂度时 **O(nlogn)** ，最坏的情况下为 **O(n²)** 。 #### 基准元素（pivot）在分治过程中，以基准元素为中心，把其他元素移动到它的左右两侧。可以随机选择一个元素作为基准元素，并且让基准元素和数列的首项交换位置。 #### 元素的交换 **1. 双边循环法**
**2. 单边循环法** #### 双边循环法首先，选定基准元素 pivot，并设置两个指针 left 和 right，分别执行数列的最左和最右两个元素。
接下来进行第 1 次循环：
从 right 指针开始，让指针所指的元素与基准元素相比较，
如果大于或者等于 pivot，则指针 right 向左移动;
如果小于 pivot 的值，则 right 指针停止移动，切换到 left 指针;
轮到 left 指针移动，让指针所指的元素与基准元素相比较，
如果小于或者等于 pivot，则 left 指针右移;
如果大于 pivot，则 left 指针停止移动。
此时，比较 left 与 right，如果 left 小于 right，这交换这两个位置上的元素
接下来进行第 2 次循环：
重新切换到 right 指针开始左移，按照这个思路继续下去，知道 left 指针与 right 指针重合，这一轮才宣告结束，
此时基准元素在排序后的位置，就是 left 与 right 指针重合点的位置，所以要将重合点上的元素与基准元素交换位置这样下来，原数列在每一轮都被基准元素拆分成了两部分，小于基准元素的数列在基准元素左边的位置，大于基准元素的数列在基准元素的右边位置，
每一部分在下一轮又被拆分成两部分，如此递归下去，直到不可再分为止
**递归结束的条件：** 待比较交换的数列的起始位置下标大于或等于结束下标时，递归排序结束 #### 单边循环法双边循环法从数组的两边比较并交换元素，而单边循环法则从数组的一边遍历，一直往后比较和交换，实现起来更加的简单。
过程如下：
首先也是选取基准元素 pivot（可以随机选择）
设置一个 mark 指针指向数组的起始位置，代表小于基准元素的区域边界
从基准元素下一位开始遍历数组
如果该元素大于基准元素，继续往下遍历
如果该元素小于基准元素，mark 指针往右移，小于基准元素的区域边界就增大了 1（即小于基准元素的多了1位），所以 mark 就 +1，并且该元素和 mark 指向的元素进行交换。
直到一轮遍历结束，此时 mark 所指向的位置，就是排序后基准元素的位置，所以交换基准元素与mark所指的元素
这样，就将数组拆分成了两部分，小于基准元素的的元素在基准元素左边，大于基准元素的元素在基准元素右边
这两部分又继续拆分，如此递归下去，直到不可再分为止.