QuickSort

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 主元,支点

* 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));

}

}