实现该算法的背景
快速排序实现的方式有各种各样的,但是却很少看到算法导论中的实现。就是书上那个,我很是纳闷。所以在这里贴一份这样的实现,以便需要的人的用。
算法导论中的伪代码
这里先贴出伪代码,这个我觉得算是比较好理解快排的了,更重要的非常简洁。对于记性不好的我,非常友好。
QUICKSORT(A, p, r)
if p < r
q = PARTITION(A,p,r)
QUICKSORT(A,p,q-1)
QUICKSORT(A,q+1,r)
PARTITION(A, p, r)
x = A[r]
i = p-1
for j = p to r-1
if A[j] <= x //<=与书上有区别,符号的区别,不会打那个。。。。
i = i + 1
exchange A[i] with A[j]
exchange A[i+1] with A[r]
return i + 1
理解的话,我用大白话叙述一下。目的将数组划分为 4 个部分,1:比 x 小的,2:为比 x 大,3:等于 x 的,4: 可能为空。粘一些书上的话。设任意p -> r,数组下标为k。
- 当 p ≤ k ≤ i , 则 A[k] ≤ x
- 当 i+1 ≤ k ≤ j-1,则 A[k] > x
- 当 k = r ,则 A[k] = x
证明:第一轮迭代之前是成立的,每一轮迭代都成立。
第一轮迭代之前:
i = p-1 ,j = p,所以1,2 这两成立,因为没有值在 [p ,i] 和 [i+1,j-1]之间。k = r,A[k] = A[r] = x。
每一轮迭代:
存在两种情况:
A[j] > x ,j=j+1,i不变,只有 j 变化了,所以只要条件2后半部分 k ≤ j-1,k=j,A[k] > x成立,条件1,2,3成立。
A[j] ≤ x,i=i+1,交换 A[i=i+1] 和 A[j] , k=j,在[p,i],A[i=i+1]=A[j] ≤ x,条件1满足,我们知道在迭代前,A[i+1] > x ,因为 k ≥ i+1,A[k] > x。所以交换的结果为 A[j] > x,永远确保A[j-1] > x。
如果不能理解的话,去看书本,或者其他博主的回答吧。就不粘图了。
基于java语言的代码实现
回到我们实现代码上来。用static 因为在main 中运行。
public class QuickSort {
public static int partition(int[] Array, int start, int end){
int x = Array[end];
int i = start-1;
for (int j = start; j <= end-1; j++) {
if(Array[j] <= x){
i = i + 1;
exchange(Array,i,j);
}
}
exchange(Array,i+1,end);
return i+1;
}
public static void exchange(int[] Array, int i, int j){
int temp = Array[i];
Array[i] = Array[j];
Array[j] = temp;
}
public static void quickSort(int [] Array, int start, int end){
if(start < end){
int mid = partition(Array,start,end);
quickSort(Array,start, mid -1);
quickSort(Array, mid+1, end);
}
}
public static void main(String[] args) {
int[] Array = new int[]{2,8,7,1,3,5,6,4};
arrayToString(Array);
quickSort(Array,0,Array.length-1);
arrayToString(Array);
Array = new int[]{10,1,6,9,4,9,18};
arrayToString(Array);
quickSort(Array,0,Array.length-1);
arrayToString(Array);
}
public static void arrayToString(int [] Array){
System.out.print("[");
for (int i = 0; i < Array.length; i++) {
if(i != Array.length -1){
System.out.print(Array[i]+",");
}else {
System.out.print(Array[i]);
}
}
System.out.print("]\n");
}
}
这是运行结果:
[2,8,7,1,3,5,6,4]
[1,2,3,4,5,6,7,8]
[10,1,6,9,4,9,18]
[1,4,6,9,9,10,18]
总结
用这个去理解的话,只要设置好初始值以及结束值和一个比较条件即可。x = Array[end] , i = start -1 ,
j=start 且 j <= end-1, 用Array[j] 和 x 比较,返回 =x 的位置即 i+1。
网友评论