美文网首页
经典排序 —— 快速排序

经典排序 —— 快速排序

作者: 叫我宫城大人 | 来源:发表于2019-04-28 22:29 被阅读0次

基本思想

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

算法实现

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(nlog2n)
  • 空间复杂度 O(1)

稳定性

不稳定

相关文章

网友评论

      本文标题:经典排序 —— 快速排序

      本文链接:https://www.haomeiwen.com/subject/vbysnqtx.html