快速排序算法

快速排序算法是從上到下解決問題
使用遞歸實現(xiàn)，通過巧妙的方式，實現(xiàn)原地排序

/**
 * 快速排序測試類
 *
 * @Author WR
 * @Date 2020/2/1 0001 10:51
 */
public class QuickSortTest {

    @Test
    public void test(){
        int[] a = {2,6,8,10,1,3,4,5,9};
        System.out.println("排序前：" + Arrays.toString(a));
        quickSort(a);
        System.out.println("排序后：" + Arrays.toString(a));
    }

    /**
     * 快速排序
     * @param a
     */
    public void quickSort(int[] a) {
        quickSortInternally(a, 0, a.length - 1);

    }

    /**
     * 遞歸函數(shù)
     * @param a
     * @param p
     * @param r
     */
    private void quickSortInternally(int[] a, int p, int r) {
        //遞推終止條件
        if (p >= r) {
            return;
        }

        //遞推公式
        int q = partition(a, p, r);
        quickSortInternally(a, p, q - 1);
        quickSortInternally(a, p + 1, r);
    }

    /**
     * 分區(qū)函數(shù)
     *
     * i指針的目的是指向第一個大于pivot的值
     * j指針一直向后遍歷
     *
     *
     * @param a
     * @param p
     * @param r 分區(qū)點pivot
     * @return
     */
    private int partition(int[] a, int p, int r) {
        //選擇最后一個數(shù)據(jù)作為分區(qū)點pivot
        int pivot = a[r];
        int i = p;
        for (int j = p; j < r; j++) {
            if (a[j] < pivot) {
                if (i == j) {
                    //說明之前的數(shù)都小于pivot
                    i++;
                } else {
                    //說明i與j相鄰且j快i1步 或 i與j之間包含其他數(shù)據(jù)，且數(shù)據(jù)大于a[j]。交換i與j且i指向下一個
                    int tmp = a[i];
                    a[i++] = a[j];
                    a[j] = tmp;
                }
            }
        }

        //到此為止，i指向若干次交換后第一個大于pivot的位置，i之前都小于pivot,i之后都大于pivot，交換i與pivot
        int tmp = a[r];
        a[r] = a[i];
        a[i] = tmp;

        return i;
    }

}

分析
時間復雜度O(nlogn)，極端情況下O(n^2)
非穩(wěn)定性排序
原地排序算法，空間復雜度O(1)

歸并排序算法

未完待續(xù)……