快速排序算法

快速排序算法是从上到下解决问题
使用递归实现，通过巧妙的方式，实现原地排序

/**
 * 快速排序测试类
 *
 * @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);

    }

    /**
     * 递归函数
     * @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);
    }

    /**
     * 分区函数
     *
     * i指针的目的是指向第一个大于pivot的值
     * j指针一直向后遍历
     *
     *
     * @param a
     * @param p
     * @param r 分区点pivot
     * @return
     */
    private int partition(int[] a, int p, int r) {
        //选择最后一个数据作为分区点pivot
        int pivot = a[r];
        int i = p;
        for (int j = p; j < r; j++) {
            if (a[j] < pivot) {
                if (i == j) {
                    //说明之前的数都小于pivot
                    i++;
                } else {
                    //说明i与j相邻且j快i1步 或 i与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)
非稳定性排序
原地排序算法，空间复杂度O(1)

归并排序算法

未完待续……