数组快排

快速排序很多人都懂，大体思路是首先选中一个标志位（通常选定数组的第一个元素），然后用首尾两个标识分别找出大于标志位的和小于标志位的两个数，然后交换，接着继续找下去，直到首尾两个标识相等，此时再将标志位于标识交换，就得到了标志位索面的元素小于标志位，右面的大于标志位，接着递归下去就行了。

网上写代码的很多，但是感觉都很乱，思路不清晰，这里我将数组快排的两种形式（递归与非递归）写出来，方便大家快速理解。

    //递归方法
    public static void quickSort(int[] array, int low, int high) {
        //递归的终止条件就是，如果你的结束标识大于了开始标识就结束
        if (low > high) return;
        int i = low;
        int j = high;
        //选中第一个元素当标志位
        int key = array[low];
        int t;
        while (i < j) {
            //找到第一个小于key的位置
            while (key <= array[j] && i < j)
                j--;
            //找到第一个大于key的位置
            while (key >= array[i] && i < j)
                i++;
            //交换两个数
            if (i < j) {
                t = array[i];
                array[i] = array[j];
                array[j] = t;
            }
        }
        //将标志位和ij的重合位置进行交换
        array[low] = array[i];
        array[i] = key;
        //对标志位的左面进行快排
        quickSort(array, low, i - 1);
        //对标志位的右面进行快排
        quickSort(array, i + 1, high);
    }

    //非递归
    public static void quickSort(int[] a) {
        Stack<int[]> stack = new Stack<>();
        //栈中存的是每次需要快排的数组的区间的首位标识
        stack.add(new int[]{0, a.length - 1});
        //只要栈不为空就说明还有若干段没排好序
        while (!stack.isEmpty()) {
            //弹出第一组排序的首尾标识
            int[] tuple = stack.pop();
            int start = tuple[0], end = tuple[1], i = tuple[0], j = tuple[1];
            //循环和递归是一样的
            while (i < j) {
                while (i < j && a[start] < a[j])
                    j--;
                while (i < j && a[start] >= a[i])
                    i++;
                if (i < j) {
                    int temp = a[j];
                    a[j] = a[i];
                    a[i] = temp;
                }
            }
            if (start != i) {
                int temp = a[start];
                a[start] = a[i];
                a[i] = temp;
            }
            //此时i = j,a[i] = a[j] = key，这个key就是第一个标志位
            //如果此时，i的左面只有一个start元素，此时就不需要排序了
            if (i - 1 > start)
                stack.add(new int[]{0, i - 1});
            //同理，j的右面只有一个元素end，就不需要排序了
            if (j + 1 < end)
                stack.add(new int[]{j + 1, end});
        }
    }

链表快排

整体思想是两个指针p1和p2，保持p1前面的比key小，p1和p2之间的比key大。key就是我们选取的标志位，我这里选的是链表的头结点。

/*class ListNode {
    int val;
    ListNode next = null;

    ListNode(int val) {
        this.val = val;
    }
}*/

public class l148QuickSortList {
    public static ListNode sortList(ListNode head) {
        quickSort(head, null);
        return head;
    }

    public static void quickSort(ListNode head, ListNode end) {
        if (head != end) {
            //先分再排
            ListNode node = sort(head, end);
            //排序
            quickSort(head, node);
            quickSort(node.next, end);
        }
    }

    public static ListNode sort(ListNode head, ListNode end) {
        //指定两个指针p1在前，p2在后
        ListNode p1 = head;
        ListNode p2 = head.next;
        while (p2 != null) {
            //如果p2比head的值小的话，p1前进一位，和p2的val进行交换，然后p2再前进一步
            //始终保持p1前面的比key小，p2和p1中间的比key大于等于，p2后面的是没有比过的
            if (p2.val < head.val) {
                p1 = p1.next;
                int temp = p1.val;
                p1.val = p2.val;
                p2.val = temp;
            }
            p2 = p2.next;
        }
        //如果p1移动了就和key交换值，否则说明都比key大
        if (p1 != head) {
            int tmp = p1.val;
            p1.val = head.val;
            head.val = tmp;
        }
        return p1;
    }
}

看到这里想必你对快排有了更清晰的认识了，多写多练！