快速排序

选择一个元素做为分隔标准,将数据分为两半,其中一半比指定元素大,另一半比指定元素小,接着按同样方式分别对两部分数据各自再进行快速排序;

时间复杂度:O(nlog2N)

标准元素的选取通常有两种方式:

一. 数组的第一个元素

二. 数组的最中间元素

我们先按第一种方式进行排序,也就是以数组的第一个元素做为标准元素进行排序.

先上代码:

void quickSort(int[] arrays, int start, int end) {
        System.out.println("排序数组 start=" + start + ",end=" + end + ",array=" + Arrays.toString(arrays));
        if (start < end) {
            int pivot = arrays[start];
            // 参照元素选取
            int i = start;
            int j = end + 1;
            while (true) {
                while (i < end && pivot > arrays[++i]) {
                    // 从前向后遍历,找到比参照点[大]的元素
                    // 遇到比参照元素值[大]的元素会停止循环
                    ;
                }
                while (j > start && pivot < arrays[--j]) {
                    // 从后向前遍历,找到比参照点[小]的元素
                    // 遇到比参照元素值遇到小的元素会停止循环
                    ;
                }
                if (i < j) {
                    // 保证交换元素时,i,j 索引位置不交叉,间接保证大的数据会被交换到数组后面
                    // 将i对应比参照值大的元素,与j对应比参照值小的元素,交互位置
                    // 同时按当前位置继续遍历数组
                    swap(i, j, arrays);
                    System.out.println("start=" + start + ",end=" + end + ",pivot=" + pivot + "\n\tarray=" + Arrays.toString(arrays));
                } else {
                    break;
                }
            }
            swap(j, start, arrays);
            System.out.println("start=" + start + ",end=" + end + ",pivot=" + pivot + "\n\tarray=" + Arrays.toString(arrays));
            quickSort(arrays, start, j - 1);
            quickSort(arrays, j + 1, end);
        }
}

以如下原始数组为例,看一下排序过程;

[42, 41, 31, 7, 17, 2, 55, 26, 80, 27]

说明:

1. 第一次遍历,参照元素选为首元素42;

2. 起始位置为数组第0个元素;

3. 结束位置为数组最后一个元素;

排序数组 start=0,end=9,array=[42, 41, 31, 7, 17, 2, 55, 26, 80, 27]

说明:

1. 索引i从前向后遍历,寻找比参照值(42)大的元素,该元素为55;

2. 索引j从后向前遍历,寻找比参照值(42)小的元素,该元素为:27

3. 两元素交换位置,得到如下该数组,

start=0,end=9,pivot=42

array=[42, 41, 31, 7, 17, 2, 27, 26, 80, 55]

说明:

1. 交换元素后,索引i和索引j继续遍历;

2. 索引i遍历到的下一个比参照值(42)大的数据是80,索引值是8;

3. 索引j遍历到的下一个比参照值(42)小的数据是26,索引值是7;

4. 索引i值 > 索引j值,数组元素不进行交换,如果交换,相当于把大的数据被交互到前面,小的数据被交互到后面了,是不符合整体排序预期的;

5. 虽然遍历结束了,但是索引j对应的元素(26)还是比参数值(42)小的,也是不符合预期的,要对这两个元素进行交互位置,最后得到如下结果.

start=0,end=9,pivot=42

array=[26, 41, 31, 7, 17, 2, 27, 42, 80, 55]

说明:

1. 我们看下第一次遍历后的数组可以发现,按参照元素(42)分隔的数组,左侧都是比吧参照元素小的,右侧是比参照元素大的;

2. 再对分开的两部分数组分别进行排序,左边的排序数组范围是0~6;右边的排序数组范围是8~9;

排序数组 start=0,end=6,array=[26, 41, 31, 7, 17, 2, 27, 42, 80, 55]

start=0,end=6,pivot=26

array=[26, 2, 31, 7, 17, 41, 27, 42, 80, 55]

start=0,end=6,pivot=26

array=[26, 2, 17, 7, 31, 41, 27, 42, 80, 55]

start=0,end=6,pivot=26

array=[7, 2, 17, 26, 31, 41, 27, 42, 80, 55]

排序数组 start=0,end=2,array=[7, 2, 17, 26, 31, 41, 27, 42, 80, 55]

start=0,end=2,pivot=7

array=[2, 7, 17, 26, 31, 41, 27, 42, 80, 55]

排序数组 start=0,end=0,array=[2, 7, 17, 26, 31, 41, 27, 42, 80, 55]

排序数组 start=2,end=2,array=[2, 7, 17, 26, 31, 41, 27, 42, 80, 55]

排序数组 start=4,end=6,array=[2, 7, 17, 26, 31, 41, 27, 42, 80, 55]

start=4,end=6,pivot=31

array=[2, 7, 17, 26, 31, 27, 41, 42, 80, 55]

start=4,end=6,pivot=31

array=[2, 7, 17, 26, 27, 31, 41, 42, 80, 55]

排序数组 start=4,end=4,array=[2, 7, 17, 26, 27, 31, 41, 42, 80, 55]

排序数组 start=6,end=6,array=[2, 7, 17, 26, 27, 31, 41, 42, 80, 55]

排序数组 start=8,end=9,array=[2, 7, 17, 26, 27, 31, 41, 42, 80, 55]

start=8,end=9,pivot=80

array=[2, 7, 17, 26, 27, 31, 41, 42, 55, 80]

排序数组 start=8,end=8,array=[2, 7, 17, 26, 27, 31, 41, 42, 55, 80]

排序数组 start=10,end=9,array=[2, 7, 17, 26, 27, 31, 41, 42, 55, 80]

快排序：[2, 7, 17, 26, 27, 31, 41, 42, 55, 80]

以上,就是数组的整个排序过程,明显可见,元素交换次数是要比冒泡排序少很多的,速度较快的原因.在排序过程中,如果是相邻的进行了交换,也就意味着是最坏的情况,这时候的时间复杂度是O(N^2). 整个算法也是采用”二分法”,对数组进行分别排序.

附上swap()方法代码

  void swap(int i, int k, int[] array) {
        int tmp = array[i];
        array[i] = array[k];
        array[k] = tmp;
    }