Java-快速排序
在要排的数(比如数组A)中选择一个中心值key(比如A[0]),通过一趟排序将数组A分成两部分,其中以key为中心,key右边都比key大,key左边的都key小,然后对这两部分分别重复这个过程,直到整个有序。
整个快排的过程就简化为了一趟排序的过程,然后递归调用就行了。
一趟排序的方法:
1,定义i=0,j=A.lenght-1,i为第一个数的下标,j为最后一个数下标
2,从数组的最后一个数Aj从右往左找,找到第一小于key的数,记为Aj;
3,从数组的第一个数Ai 从左往右找,找到第一个大于key的数,记为Ai;
4,交换Ai 和Aj
5,重复这个过程,直到 i=j
6,调整key的位置,把A[i] 和key交换
假设要排的数组为:A[8] ={ 5 2 8 9 2 3 4 9 }
选择 key = 5, 开始时 i=0,j=7
index 0 1 2 3 4 5 6 7
开始: 5 2 8 9 2 3 4 9
i j
第一次找 5 2 8 9 2 3 4 9
i j
交换: 5 2 4 9 2 3 8 9
i j
第二次找 5 2 4 9 2 3 8 9
i j
交换: 5 2 4 3 2 9 8 9
i j
第三次找 5 2 4 3 2 9 8 9
ij
调整key: 2 5 4 3 5 9 8 9
ij
代码:
public static void main(String[] args) {
int[] arr = { 1, 5, 2, 8, 6, 4, 9, 6 };
quickSort(arr, 0, arr.length - 1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr, int i, int j) {
if (i > j)
return;
int start = i;
int end = j;
int temp = arr[i];
while (start < end) {
while (arr[end] >= temp && start < end) {
end--;
}
if (arr[end] <= temp) {
int k = arr[end];
arr[end] = arr[start];
arr[start] = k;
}
while (arr[start] <= temp && start < end) {
start++;
}
if (arr[start] >= temp) {
int k = arr[start];
arr[start] = arr[end];
arr[end] = k;
}
}
quickSort(arr, i, start - 1);
quickSort(arr, end + 1, j);
}
上一篇: Ubuntu 下 matplotlib 显示中文的方法
下一篇: 小甲鱼 排序算法 快速排序