快速排序是八大排序算法之一，运用也是相当广泛。快速排序是分治思想的一种体现，分治就是将一个规模为N的问题分解成K个规模较小的问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。
比如给定一组数据[31, 68, 45, 90, 23, 39, 54, 12, 87, 76]，我们用快速排序的思想来对这组数据进行排序。
现在我们使用图解来分析它的排序步骤：
（1）第一步：定义两个指针low和high，low指针指向数组的第一个位置，high指针指向数组中的最后一个位置。并且用一个temp变量来存储第一个位置的数据,即temp=31。
（2）第二步：我们定义一个指针移动方向，先从右往左移动，即先移动high指针。先用high指针上的数据和temp进行比较，如果high指针上的数据大于temp,那就一直往左边移动high指针。直到high指针上的数据比temp小时，high指针才停止移动。
（3）第三步：现在出现了high指针上的数据小于了temp,即array[high] < temp，即（12 < 31）。我们就要把high指针指向的数据放到low指针的位置上; high指针停止移动，然后改变指针移动方向，low指针向右移动1位。
（4）第四步：low指针向右移动过程中如果array[low]>temp,就把low上面对应的数据放到array[high]上；并且low指针不动，改变指针移动方向，high指针向前移动一位。
（5）根据这样的规律一直找下去，直到两个指针重合，把temp的数据放到重合位置上面。
（5）这样一轮下来之后，我们就针对放置temp数据的位置的左右两边进行快速排序，即使用递归。
说了这么多我也不知道清没清楚，最后还是回到代码上来处理：
//begin和end是传入数组array的头尾两个下标
public static void quickSort(int[] array,int begin,int end){
if(end <= begin){
return;
}
//step1:定义两个指针下标指向数组两端，并把开始指针处的数据存储起来
int low = begin;
int high = end;
int temp = array[begin];
//step2:定义两个指针的移动
boolean direction = true;
L1:
while(low < high){
if(direction) { //高位指针向左移动
for (int i = high; i > low; i--) {
if (array[i] <= temp) {
array[low++] = array[i]; //把这个小的数放到低位指针的位置,并且低位指针向右移动1位
high = i; //并修改高位指针的位置，让其放置在满足if条件的i上
direction = !direction; //改变指针移动
continue L1;
}
}
high = low; //最后两个位置重合即可跳出循环
}else{
for(int i=low;i<high;i++){
if(array[i] >= temp){
array[high--] = array[i];
low = i;
direction = !direction;
continue L1;
}
}
low = high;
}
}
//step3:把temp放到两个指针重合的位置
array[low] = temp;
//array[high] = temp;
//step4:把放置temp数据的左右两边继续进行快速排序，这很类似二叉树的前序遍历
quickSort(array,begin,low-1);
quickSort(array,low+1,end);
}
快速排序的应用场景：源数据是数据量大并且是顺序存储结构使用快速排序效率最高。
短处：
（1）数据中有大量重复数据的时候性能不好；
（2）数据是链式存储结构的时候，性能下降严重。
那数据是链式存储结构的时候我们用什么排序呢？下篇文章再进行分析。
小白笔记，如有错误欢迎指正！
网友评论