基本思想

通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

算法实现

package cn.caojiantao.tutorials.sort;

/**
 * @author caojiantao
 */
public class Fast implements ISort {

    @Override
    public void sort(int[] data) {
        sort(data, 0, data.length - 1);
    }

    private void sort(int[] data, int start, int end) {
        if (start < end) {
            int i = start, j = end, key = data[i];
            while (i < j) {
                while (i < j && data[j] >= key) j--;
                ArrayUtils.swap(data, i, j);
                while (i < j && data[i] < key) i++;
                ArrayUtils.swap(data, i, j);
            }
            sort(data, start, i - 1);
            sort(data, j + 1, end);
        }
    }
}

复杂度

• 时间复杂度 O(nlog₂n)
• 空间复杂度 O(1)

稳定性

不稳定