595509b880a4510067ace89522b20e7c
图解快速排序

图解快速排序,动图+代码+分析

[TOC]

简述:

  快速排序(QuickSort)是对冒泡排序的一种改进
  它的基本思想是:通过一趟排序将要排序的数据分割成两个独立的部分,其中一部分的所有数据都比另外一部分的所有数据要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到将整个序列变成有序序列。
  快排利用的是一种分治的思想,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解。

图解:

代码:

方法:

public void quickSort(int[] arr, int left, int right) {
    if (left > right) {
        return;
    }
    int i = left;
    int j = right;
    int pivot = arr[i];
    while (i < j) {
        while (i < j && pivot < arr[j]) {
            j--;
        }
        while (i < j && pivot >= arr[i]) {
            i++;
        }
        if (i < j) {
            swap(arr, i, j);
        }
    }
    swap(arr, i, left);
    quickSort(arr, left, i - 1);
    quickSort(arr, i + 1, right);
}
private void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}

测试:

    public static void main(String[] args) {
        Test test = new Test();
        int[] arr = new int[]{4, 1, 5, 2, 6, 3};
        System.out.println(Arrays.toString(arr));
        test.quickSort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

结果:

[4, 1, 5, 2, 6, 3]
[1, 2, 3, 4, 5, 6]

分析:

时间复杂度

  我们可以利用递归树对快速排序的时间复杂度做简单的分析。我们假设每次分解都是一分为2,则可以画出如下的递归树。

  即求快速排序的时间复杂度等于O(n*h),h为二叉树的高度,即最终求的快速排序的时间复杂度为O(nlogn),这个时候可能有一个疑问,我们不能保证每次分解数组都是一分为2,分解数组所占原数组只比,只影响log的底数,假设每次分解数组都会将数组分解成1/10、9/10,则递归树最长路径为:log以10/9为底,n的对数,最短路径为:lgn,此时底数可忽略不计,时间复杂度仍是O(nlogn)(底数相当于常数)

空间复杂度

  快速排序没有用到额外的存储空间,所以它的空间复杂度是O(1),即原地排序

稳定性

  快速排序不是稳定排序,即原数组中存在[..i,..i..],经过排序后,两个i的顺序可能会被颠倒,与pivot有关。

  最后,期待您的订阅和点赞,专栏每周都会更新,希望可以和您一起进步,同时也期待您的批评与指正!

© 著作权归作者所有
这个作品真棒,我要支持一下!
一个坚持原创的小专栏。分享编程知识,提升工作效率,致力于通过简单的语言,把编程这点事讲清楚。涵盖内容:java、设...
0条评论
top Created with Sketch.