数组，快速排序 - 黑马程序员技术交流社区

/*
目的：理解快速排序
思路：用前后索引的移动把目标元素放到数组中正确的位置，此位置前边的元素比目标小，后边的比目标大
步骤：具体已转注释
sy 索引
kp 快排..
输出结果：
---------------------------------
F:\MyCode\EditPlus_code>javac SortKPTest.java
F:\MyCode\EditPlus_code>java SortKPTest
-3 2 2 4 32 98
-----------------------------------
*/
public class SortKPTest {
//main
public static void main(String[] args) {
int[] arr = new int[]{2, 4, -3, 32, 98, 2};
SortKP kp = new SortKP();
kp.kp(arr, 0, 5); //对数组中0到5号元素进行排序;
for(int x : arr) { //遍历排序后的数组
System.out.print(" "+x+" ");
}
System.out.println();
}
}
class SortKP{ //快速排序
public int sy(int[] a, int i, int j) {
int v = a[i]; //把索引为i的元素保存到v中，寻找元素v在整个数组中排序后的位置
while(i<j) { //只有当前索引小于后索引才进入循环
while(i<j && a[j]>=v) {
j--;
}
a[i] = a[j]; //i和j 是前索引和后索引，前索引不变，后索引对应的元素和需要找位置的元素 v 比较，
//当发现 v 更小，就把后索引往前移，继续判断循环，
//当发现 v 更大，把后索引元素放到前索引元素位置（上边前索引元素已经保存在v中），
//此时，后索引 j所在的位置之后已经都比 v 大，往下走
while(i<j && a[i]<=v) {
i++;
}
a[j] = a[i]; //同理，后索引不变，前索引对应的元素和需要找位置的元素 v 比较，
//当发现 v 更大，就把前索引往后移，继续判断循环，
//当发现 v 更小，把前索引元素放到后索引元素位置，
//此时，后索引 i所在的位置之后已经都比 v 小，往下走
//接着进入下一次外循环
}
a[i] = v; //直到当前后索引的位置重合，此时这个索引指向的位置就是 V 的位置（前边比v小，后边比v大）
//放到eclipse中通过断点查看此时的a[i]可知，v元素放到正确的位置
//或是 a[j] = v;
return i; //返回已经找到的元素的索引
}
public void kp(int[] a, int i, int j) {
int pos; //创建一个记录位置的变量，用来记录上边 sy方法返回的位置，把数组分成前后两个部分继续排序
if(i<j) { //当前索引i和后索引j之间有元素，才进行判断
pos = sy(a, i, j); //返回一个排好元素的标号，把数组分成两半
kp(a, pos+1, j); //排数组后边的元素
kp(a, i, pos-1); //排数组前边的元素
}
}
}

复制代码