[数据结构与算法]图解排序算法之快速排序算法

精心整理的快速排序，并配图加代码，方便理解，实属不易，但是难免不了存在纰漏，感谢大家的指正与理解！觉的写的不错的小伙伴儿，一键三连支持一下，后期会有持续更新！！抱拳了罒ω罒

1. 算法思路

1．先从数组中取出一个数（通常第一个数）作为基准数。
2．将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3．对左右两边的子数组进行递归排序，直到只剩下一个元素则全部排序完成。

2. 性能

• 时间复杂度：平均情况下的时间复杂度为O(nlogn)。最好的情况是O(n)，最坏情况下时间复杂度为O(n2)。
• 空间复杂度：它是一种原地排序，只需要一个很小的栈作为辅助空间，空间复杂度为O(log2n)，所以适合在数据集比较大的时候使用。
• 稳定性：不稳定的算法

3. 举例说明

??假如有一个数组，如下：

1. 首先，我们以第一个数为基准，然后定义两个哨兵 i 和 j ，首先哨兵 j 从后往前找比基准元素小的数的位置，然后哨兵 i 从前往后找比基准元素大的数的位置。
   
2. 找到指定元素后，将两个指定的元素互换位置。
   
3. 同理继续往后运行，直到 i 和 j 重合。
   
4. 直到哨兵i和哨兵j相遇，相遇位置的元素与基准元素交换。这时相遇位置左边的元素都比基准元素大，右边的元素都比基准元素小。将两边的元素各作为一个子序列进行递归操作。
   

4. 代码示范

public class Test{
	 public static void main(String[] args) {
        int []nums = {5,9,8,7,2,4,2,3,6};
        quickSort(nums,0,nums.length - 1);
        for (int i = 0; i < nums.length; i++) {
            System.out.print(nums[i]+" ");
        }
    }
	/**
     *      快速排序
     * @param nums 待排序数组
     * @param low 数组的第一个元素的索引
     * @param high 数组的最后一个元素的索引
     */
	public static void quickSort(int[]nums,int low,int high){
		//只要两个哨兵相遇那么就退出递归！
		if(low >= high)return;
		//取出第一个数为基数————————————步骤1
		int mid = nums[low];
		int i = low,j = high;
		//i 和 j 两个哨兵没有相遇就一直查找
		while(i< j){
			// j哨兵往前查找，找到小于基数的位置
			while(i< j&& nums[j] >= mid) j--;
			// i哨兵往后查找，找到大于基数的位置
			while(i< j&& nums[i] <= mid) i++;
			//如果两个哨兵没相遇那就将两个交换——————————步骤2和3
			if(i< j)swap(nums,i,j);
		}
		//跳出循环，说明i和j哨兵相遇，并且相遇的位置的值一定是小于等于基数
		//将相遇的位置的值跟基数交换————————————步骤4
		nums[low] = nums[i];
		nums[i] = mid;
		//递归排序左边的子数组
		quickSort(nums,low,i - 1);
		//递归排序右边的子数组
		quickSort(nums,i + 1,high);
	}
	//交换函数
	public static void swap(int[]nums,int i,int j){
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}

}

结果：

2 2 3 4 5 6 7 8 9 

快速排序还有很多改进版本，如随机选择基数，最后一位为基数等等，区间内数据较少时直接用另的方法排序以减小递归深度。