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