快速排序（Quicksort）是对冒泡排序的一种改进。
它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
文字理解有些困难，先从网上找下代码看一看
public static void quickSort(int[] a, int left, int right) {
if (left >= right)
return;
int pivot = a[left];//定义基准值为数组第一个数
int i = left;
int j = right;
while (i < j) {
while (pivot <= a[j] && i < j)//从右往左找比基准值小的数
{
j--;
}
while (pivot >= a[i] && i < j)//从左往右找比基准值大的数
{
i++;
}
if (i < j) //如果i<j，交换它们
{
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
a[left] = a[i];
a[i] = pivot;//把基准值放到合适的位置
quickSort(a, left, i - 1);//对左边的子数组进行快速排序
quickSort(a, i + 1, right);//对右边的子数组进行快速排序
}
以数组第一个数值作为基值，从右向左寻找比基值小的数，从左向右寻找比基值大的数，然后互换。用i和j记录数组下标，一直到 i>=j 时，把基值和分界线值交换，把基值两边的数值继续进行快速遍历，一直到每次的快速排序左下标 > 右下标为止
大概的流程清楚点了，再加一下log准备跑一下看看
public void quickSortTest(int[] a, int left, int right) {
System.out.println("初始数组" + Arrays.toString(a) + "左边起始下标" + left + "右边起始下标" + right);
if (left >= right) {
System.out.println("数组左下标大于等于右下标，return");
return;
}
int pivot = a[left];
System.out.println("基值pivot=" + pivot);
int i = left;
int j = right;
while (i < j) {
while (pivot <= a[j] && i < j) {
System.out.println("右边起————a[" + j + "]=" + a[j] + "大于等于pivot不满足条件，做j--操作");
j--;
}
while (pivot >= a[i] && i < j) {
System.out.println("左边起————a[" + i + "]=" + a[i] + "小于等于pivot不满足条件，做i--操作");
i++;
}
if (i < j) {
int value = a[i];
a[i] = a[j];
a[j] = value;
System.out.println(a[i] + "和" + a[j] + "互换,互换后数组：" + Arrays.toString(a));
}
}
System.out.println("左边的下标大于等于右边的下标了，说明数组需要判断的数据已经判断完一遍了，把基值" + pivot + "和分界线值" + a[i] + "交换");
a[left] = a[i];
a[i] = pivot;
System.out.println("基值和分界线值交换后数组：" + Arrays.toString(a));
quickSortTest(a, left, i - 1);
quickSortTest(a, i + 1, right);
}
打印出来log
初始数组[7, 5, 3, 2, 9, 10, 8, 4, 6, 1]左边起始下标0右边起始下标9
基值pivot=7
左边起————a[0]=7小于等于pivot不满足条件，做i--操作
左边起————a[1]=5小于等于pivot不满足条件，做i--操作
左边起————a[2]=3小于等于pivot不满足条件，做i--操作
左边起————a[3]=2小于等于pivot不满足条件，做i--操作
1和9互换,互换后数组：[7, 5, 3, 2, 1, 10, 8, 4, 6, 9]
右边起————a[9]=9大于等于pivot不满足条件，做j--操作
左边起————a[4]=1小于等于pivot不满足条件，做i--操作
6和10互换,互换后数组：[7, 5, 3, 2, 1, 6, 8, 4, 10, 9]
右边起————a[8]=10大于等于pivot不满足条件，做j--操作
左边起————a[5]=6小于等于pivot不满足条件，做i--操作
4和8互换,互换后数组：[7, 5, 3, 2, 1, 6, 4, 8, 10, 9]
右边起————a[7]=8大于等于pivot不满足条件，做j--操作
左边的下标大于等于右边的下标了，说明数组需要判断的数据已经判断完一遍了，把基值7和分界线值4交换
基值和分界线值交换后数组：[4, 5, 3, 2, 1, 6, 7, 8, 10, 9]
初始数组[4, 5, 3, 2, 1, 6, 7, 8, 10, 9]左边起始下标0右边起始下标5
基值pivot=4
右边起————a[5]=6大于等于pivot不满足条件，做j--操作
左边起————a[0]=4小于等于pivot不满足条件，做i--操作
1和5互换,互换后数组：[4, 1, 3, 2, 5, 6, 7, 8, 10, 9]
右边起————a[4]=5大于等于pivot不满足条件，做j--操作
左边起————a[1]=1小于等于pivot不满足条件，做i--操作
左边起————a[2]=3小于等于pivot不满足条件，做i--操作
左边的下标大于等于右边的下标了，说明数组需要判断的数据已经判断完一遍了，把基值4和分界线值2交换
基值和分界线值交换后数组：[2, 1, 3, 4, 5, 6, 7, 8, 10, 9]
初始数组[2, 1, 3, 4, 5, 6, 7, 8, 10, 9]左边起始下标0右边起始下标2
基值pivot=2
右边起————a[2]=3大于等于pivot不满足条件，做j--操作
左边起————a[0]=2小于等于pivot不满足条件，做i--操作
左边的下标大于等于右边的下标了，说明数组需要判断的数据已经判断完一遍了，把基值2和分界线值1交换
基值和分界线值交换后数组：[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
初始数组[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]左边起始下标0右边起始下标0
数组左下标大于等于右下标，return
初始数组[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]左边起始下标2右边起始下标2
数组左下标大于等于右下标，return
初始数组[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]左边起始下标4右边起始下标5
基值pivot=5
右边起————a[5]=6大于等于pivot不满足条件，做j--操作
左边的下标大于等于右边的下标了，说明数组需要判断的数据已经判断完一遍了，把基值5和分界线值5交换
基值和分界线值交换后数组：[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
初始数组[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]左边起始下标4右边起始下标3
数组左下标大于等于右下标，return
初始数组[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]左边起始下标5右边起始下标5
数组左下标大于等于右下标，return
初始数组[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]左边起始下标7右边起始下标9
基值pivot=8
右边起————a[9]=9大于等于pivot不满足条件，做j--操作
右边起————a[8]=10大于等于pivot不满足条件，做j--操作
左边的下标大于等于右边的下标了，说明数组需要判断的数据已经判断完一遍了，把基值8和分界线值8交换
基值和分界线值交换后数组：[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]
初始数组[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]左边起始下标7右边起始下标6
数组左下标大于等于右下标，return
初始数组[1, 2, 3, 4, 5, 6, 7, 8, 10, 9]左边起始下标8右边起始下标9
基值pivot=10
左边起————a[8]=10小于等于pivot不满足条件，做i--操作
左边的下标大于等于右边的下标了，说明数组需要判断的数据已经判断完一遍了，把基值10和分界线值9交换
基值和分界线值交换后数组：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]
初始数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]左边起始下标8右边起始下标8
数组左下标大于等于右下标，return
初始数组[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]左边起始下标10右边起始下标9
数组左下标大于等于右下标，return
1 2 3 4 5 6 7 8 9 10
结合log捋一遍代码，快速排序的过程就明白了。后来在网上看到了一个图解，非常形象。博客地址https://blog.csdn.net/adusts/article/details/80882649
image.png
image.png
image.png
image.png
image.png
image.png
image.png
image.png
这个图解非常的形象，对此产生了浓厚的兴趣，搜索发现这个是《啊哈！算法》这本书的图解，准备买一本看看。
快速排序上面介绍的是不动基准数的思想，还有种是将基准数a[0]一开始就参与其中https://blog.csdn.net/MoreWindows/article/details/6684558这篇文章看完感觉讲的很好。
根据上面文章所表达的“填坑”思想，练一下手，用栈的方式书写一遍代码
public void quickSortStack(int[] a) {
Stack<Integer> stack = new Stack<>();
stack.push(0);
stack.push(a.length - 1);
while (!stack.empty()) {
int right = stack.pop();
int left = stack.pop();
int pivot = a[left];
int i = left;
int j = right;
while (i < j) {
while (a[j] > pivot && i < j) {
j--;
}
if (i < j) {
a[i] = a[j];
i++;
}
while (a[i] < pivot && i < j) {
i++;
}
if (i < j) {
a[j] = a[i];
j--;
}
}
a[i] = pivot;
if (left < i - 1) {
stack.push(left);
stack.push(i - 1);
}
if (right > i + 1) {
stack.push(i + 1);
stack.push(right);
}
}
}
网友评论