失眠网 > 快速掌握排序算法——快速排序（图解）

快速掌握排序算法——快速排序（图解）

时间：2019-01-18 15:16:39

相关推荐

快速掌握排序算法——快速排序（图解）

前言

八大排序算法中我们最常用的还是快排，其效率和代码实现难度上都符合使用情况。可是知道其原理，但是手撸代码很久没有实现后，总是会难免磕磕绊绊，故作此文快速回顾，引入图解页方便新学同学快速理解。代码与搭配食用更佳噢。

排序之插入排序（直接插入、折半插入、希尔排序）

堆排序（源码C）

简述

简单的说，快排本质上是一个个寻找数组中每个元素的正确位置的过程，这个过程中暂叫确定的元素叫标准位。首先寻找到标准位在目标排序中的正确位置——通过双指针Left和Right，以排序数组为区间，二者相向运动。具体为通过交互实现：

记录标准位的值，留存；

左右不相碰的时候：

从右到左找寻比标准位小的值，第一步骤是找到的值（比其小）覆盖标准位；

从左到右寻找比标准位大的值，右指针的值被左指针覆盖（即上一步骤找到值的位置[有两份，覆盖了最初标准位多了一份]，被新找到的覆盖）

相碰的位置被替换回标准位的值(找到标准值在目标排序位置的正确位置)

标准位前后两个数组重复该过程，整体以此循环函数过程n次。（递归）

如下图：

代码

快排代码：

public class QuickSort {public void quickSort(int arr[] , int l , int r){if (l > r){return;}int left = l , right = r;int comparator = arr[left];//左指针遇到右指针，完成一次标准位定位while( left < right){//找比标准位comparator小的值while (left < right && arr[right] >= comparator) {right--;}arr[left] = arr[right];//找比标准位comparator大的值while(left < right && arr[left] < comparator){left ++;}//填上标准位的值arr[right] = arr[left];}//arr[right] = comparator; ， left相遇了right，二者相等arr[left] = comparator;//left == right ，迭代完成所以待排序数组的元素定位quickSort(arr , l , left-1);quickSort(arr , left+1 , r);}public static void main(String[] args) {int []arr = new int[]{3,5,7,4,9,6,8,1,2,3,3,0};new QuickSort().quickSort(arr ,0 , arr.length-1);System.out.println(Arrays.toString(arr));}}