package harry.algorithms;
import org.junit.Test;
import java.util.Arrays;
/**
* Created by IntelliJ IDEA.
* User: Administrator
* Date: 11-9-18
* Time: 下午8:14
* To change this template use File | Settings | File Templates.
*/
public class QuickSort {
/**
*
* @param A
* @param p
* @param r
*
* the i,j,p,r of below of pseudo code are the number of which element,
* not the index.But pay attention, in the real code, will change to index.
*
* x = A[r] //pivot element 主元,支點(diǎn)
* i = p-1
* for j=p to r-1
* if A[j] <= x
* i++;
* exchange A[i] with A[j]
*
* exchange A[i+1] with A[r]
* return i+1
*/
private int partition(int[] A,int p, int r) {
int x = A[r]; //pivot element
int i = p-1;
for (int j=p; j<r; j++) {
if (A[j]<=x) {
i++;
exchange(A,i,j);
}
}
exchange(A,i+1,r);
return i+1;
}
private void exchange(int[] A, int i, int j) {
int k= A[i];
A[i] = A[j];
A[j] = k;
}
public void quickSort(int[] A, int p, int r) {
if (p<r) {
int q = partition(A, p, r);
quickSort(A, p, q-1);
quickSort(A, q+1, r);
}
}
@Test
public void test(){
int[] A={2,8,7,1,3,5,6,4};
quickSort(A, 0,A.length-1);
System.out.println(Arrays.toString(A));
}
}
