快速排序的具体过程
代码演示分治排序的具体过程
import java.util.Arrays;
public class QuickSort {
public static void sort(int a[], int left, int right) {
System.out.println(Arrays.toString(a));
int i, j, baseNum;
if (left > right) {
return;
}
i = left;
j = right;
baseNum = a[i];
System.out.println("基准数baseNum："+baseNum);
System.out.println("第一个坑a[i]："+a[i]);
while (i < j) {
System.out.println("=========while大循环条件 while (i < j) "+"i="+i+"j="+j+"===========");
System.out.println("===从末尾处开始寻找比基准数小的数=====");
while (i < j && a[j] >= baseNum){
j--;
System.out.println("如果大于等于就继续向前寻找j--:"+j);
}
System.out.println("如果找到了比基准数小的数");
if (i < j){
System.out.println("i="+i+";j="+j+";i<j"+"&& a[j]:"+a[j]+" < baseNum");
System.out.println("将a[j]："+a[j]+"填入到坑a[i]："+a[i]+"中,然后在a[j]:"+a[j]+"上挖一个坑");
System.out.println("a["+i+"] = a["+j+"]");
a[i] = a[j];
System.out.println(Arrays.toString(a));
i++;
System.out.println("这个时候又从头部开始找比基准数大的=>i向后移动一个i++:"+i);
}
System.out.println("=====从开始处向后寻找比基准数大的数======");
while (i < j && a[i] < baseNum){
i++;
System.out.println("如果比基准数小就继续寻找,i=:"+i);
}
System.out.println("如果找到了比基准数大的数");
if (i < j){
System.out.println("i="+i+";j="+j+";i<j"+"&& a[i]:"+a[i]+" > baseNum");
System.out.println("将a[i]:"+a[i]+"填入到上一个坑a[j]:"+a[j]+"中,然后在a[i]:"+a[i]+"上挖一个坑");
a[j] = a[i];
System.out.println("a["+j+"] = a["+i+"]");
System.out.println(Arrays.toString(a));
j--;
System.out.println("这个时候又从后面往前面找比基准数小的，j向前移动一步j--："+j);
}
}
a[i] = baseNum;
sort(a, left, i - 1);
sort(a, i + 1, right);
}
public static void quickSort(int a[]) {
sort(a, 0, a.length - 1);
}
public static void main(String[] args) {
int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
quickSort(a);
System.out.println(Arrays.toString(a));
}
}
[49, 38, 65, 97, 76, 13, 27, 49]
基准数baseNum：49
第一个坑a[i]：49
=========while大循环条件 while (i < j) i=0j=7===========
===从末尾处开始寻找比基准数小的数=====
如果大于等于就继续向前寻找j--:j=6;i=0
如果找到了比基准数小的数
i=0;j=6;i<j&& a[j]:27 < baseNum
将a[j]：27复制到坑a[i]：49中,然后在原来的:27上挖一个坑
a[0] = a[6]
[27, 38, 65, 97, 76, 13, 27, 49]
这个时候又从头部开始找比基准数大的=>i向后移动一个i++:1
=====从开始处向后寻找比基准数大的数======
如果比基准数小就继续寻找,i=:2
如果找到了比基准数大的数
i=2;j=6;i<j&& a[i]:65 > baseNum
将a[i]:65复制到上一个坑a[j]:27中,然后在原来的:65上挖一个坑
a[6] = a[2]
[27, 38, 65, 97, 76, 13, 65, 49]
这个时候又从后面往前面找比基准数小的，j向前移动一步j--：5
=========while大循环条件 while (i < j) i=2j=5===========
===从末尾处开始寻找比基准数小的数=====
如果找到了比基准数小的数
i=2;j=5;i<j&& a[j]:13 < baseNum
将a[j]：13复制到坑a[i]：65中,然后在原来的:13上挖一个坑
a[2] = a[5]
[27, 38, 13, 97, 76, 13, 65, 49]
这个时候又从头部开始找比基准数大的=>i向后移动一个i++:3
=====从开始处向后寻找比基准数大的数======
如果找到了比基准数大的数
i=3;j=5;i<j&& a[i]:97 > baseNum
将a[i]:97复制到上一个坑a[j]:13中,然后在原来的:97上挖一个坑
a[5] = a[3]
[27, 38, 13, 97, 76, 97, 65, 49]
这个时候又从后面往前面找比基准数小的，j向前移动一步j--：4
=========while大循环条件 while (i < j) i=3j=4===========
===从末尾处开始寻找比基准数小的数=====
如果大于等于就继续向前寻找j--:j=3;i=3
如果找到了比基准数小的数
=====从开始处向后寻找比基准数大的数======
如果找到了比基准数大的数
i不小于j 或者i=j
将基准数替换回a[i]
[27, 38, 13, 49, 76, 97, 65, 49]
---对低子表进行递归排序---
[27, 38, 13, 49, 76, 97, 65, 49]
基准数baseNum：27
第一个坑a[i]：27
=========while大循环条件 while (i < j) i=0j=2===========
===从末尾处开始寻找比基准数小的数=====
如果找到了比基准数小的数
i=0;j=2;i<j&& a[j]:13 < baseNum
将a[j]：13复制到坑a[i]：27中,然后在原来的:13上挖一个坑
a[0] = a[2]
[13, 38, 13, 49, 76, 97, 65, 49]
这个时候又从头部开始找比基准数大的=>i向后移动一个i++:1
=====从开始处向后寻找比基准数大的数======
如果找到了比基准数大的数
i=1;j=2;i<j&& a[i]:38 > baseNum
将a[i]:38复制到上一个坑a[j]:13中,然后在原来的:38上挖一个坑
a[2] = a[1]
[13, 38, 38, 49, 76, 97, 65, 49]
这个时候又从后面往前面找比基准数小的，j向前移动一步j--：1
i不小于j 或者i=j
将基准数替换回a[i]
[13, 27, 38, 49, 76, 97, 65, 49]
---对低子表进行递归排序---
[13, 27, 38, 49, 76, 97, 65, 49]
---对高子表进行递归排序---
[13, 27, 38, 49, 76, 97, 65, 49]
---对高子表进行递归排序---
[13, 27, 38, 49, 76, 97, 65, 49]
基准数baseNum：76
第一个坑a[i]：76
=========while大循环条件 while (i < j) i=4j=7===========
===从末尾处开始寻找比基准数小的数=====
如果找到了比基准数小的数
i=4;j=7;i<j&& a[j]:49 < baseNum
将a[j]：49复制到坑a[i]：76中,然后在原来的:49上挖一个坑
a[4] = a[7]
[13, 27, 38, 49, 49, 97, 65, 49]
这个时候又从头部开始找比基准数大的=>i向后移动一个i++:5
=====从开始处向后寻找比基准数大的数======
如果找到了比基准数大的数
i=5;j=7;i<j&& a[i]:97 > baseNum
将a[i]:97复制到上一个坑a[j]:49中,然后在原来的:97上挖一个坑
a[7] = a[5]
[13, 27, 38, 49, 49, 97, 65, 97]
这个时候又从后面往前面找比基准数小的，j向前移动一步j--：6
=========while大循环条件 while (i < j) i=5j=6===========
===从末尾处开始寻找比基准数小的数=====
如果找到了比基准数小的数
i=5;j=6;i<j&& a[j]:65 < baseNum
将a[j]：65复制到坑a[i]：97中,然后在原来的:65上挖一个坑
a[5] = a[6]
[13, 27, 38, 49, 49, 65, 65, 97]
这个时候又从头部开始找比基准数大的=>i向后移动一个i++:6
=====从开始处向后寻找比基准数大的数======
如果找到了比基准数大的数
i不小于j 或者i=j
将基准数替换回a[i]
[13, 27, 38, 49, 49, 65, 76, 97]
---对低子表进行递归排序---
[13, 27, 38, 49, 49, 65, 76, 97]
基准数baseNum：49
第一个坑a[i]：49
=========while大循环条件 while (i < j) i=4j=5===========
===从末尾处开始寻找比基准数小的数=====
如果大于等于就继续向前寻找j--:j=4;i=4
如果找到了比基准数小的数
=====从开始处向后寻找比基准数大的数======
如果找到了比基准数大的数
i不小于j 或者i=j
将基准数替换回a[i]
[13, 27, 38, 49, 49, 65, 76, 97]
---对低子表进行递归排序---
[13, 27, 38, 49, 49, 65, 76, 97]
---对高子表进行递归排序---
[13, 27, 38, 49, 49, 65, 76, 97]
---对高子表进行递归排序---
[13, 27, 38, 49, 49, 65, 76, 97]
[13, 27, 38, 49, 49, 65, 76, 97]
Process finished with exit code 0
简洁代码
import java.util.Arrays;
public class QuickSort1 {
public static void sort(int a[], int left, int right) {
int i, j, baseNum;
if (left > right) {
return;
}
i = left;
j = right;
baseNum = a[i];
while (i < j) {
while (i < j && a[j] >= baseNum){
j--;
}
if (i < j){
a[i] = a[j];
i++;
}
while (i < j && a[i] < baseNum){
i++;
}
if (i < j) {
a[j] = a[i];
j--;
}
}
a[i] = baseNum;
sort(a, left, i - 1);
sort(a, i + 1, right);
}
public static void quickSort(int a[]) {
sort(a, 0, a.length - 1);
}
public static void main(String[] args) {
int a[] = { 49, 38, 65, 97, 76, 13, 27, 49 };
quickSort(a);
System.out.println(Arrays.toString(a));
}
}
参考博客
白话经典算法系列之六 快速排序 快速搞定
【排序算法】快速排序原理及Java实现