快速排序

快速排序

推荐这篇博客排序二 快速排序
快速排序的定义
算法第四版：
快速排序是分治的排序算法，它将数组分成两个子数组，将两部分独立的排序。
快速排序的思想
快速排序把数组一分为二，通过base元素，做到左边都比他小，右边都比他大，这个需要while循环判断，一分为二是递归调用
稳定性
首先讲下稳定性的定义，快速排序也是不稳定的。选择排序因为最小的放在前面，比如准备放置第i位置的元素，与它相同j>i且是第i个最小的就会放在位置i，这样的相等但是靠后的位置就放在了前面，就不稳定了。

假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

例子

package com.java.arlgorithm.sort;


import lombok.extern.slf4j.Slf4j;

import java.util.Arrays;

/**
 * @author
 */
@Slf4j
public class QuickSortTest {
    public static void main(String[] args) {
        int[] array = new int[]{5, 6, 3, 4, 1, 6};
        quickSort(array, 0, array.length-1);
        printAll(array);

    }

    public static int devision(int[] list, int left, int right) {
        int base = list[left];
        //while循环做到了一点就是返回的base之后，base所在的位置的左边比base小，右边都比base大，在区间内跟其他所有的参数比较
        //如果还记得冒泡，冒泡从上到下交换，这样的遍历太多，每次快排都把区间隔开，好比二分，这样的排序比较次数就有可能大大的降下来
        while (left < right) {
            while (left < right && base <= list[right]) {
                right--;
            }
            list[left] = list[right];
            while (left < right && base >= list[left]) {
                left++;
            }
            list[right] = list[left];
        }
        list[left] = base;
        return left;

    }

    //
    public static void quickSort(int[] list, int left, int right) {
        if (left < right) {
            int base = devision(list, left, right);
            //递归，不停的分割区间，每个区间都是有序的
            quickSort(list, left, base - 1);
            quickSort(list, base + 1, right);
        }
    }

    public static void printAll(int[] array) {
        log.info(Arrays.toString(array));
    }
}

快排的空间复杂度

O(Nlog2N)

快排的时间复杂度

最坏情况下，快速排序将花费O(N2)时间。就是有序的情况下
最好情况下，快速排序和归并排序一样，花费O(NlogN)时间。经过logn趟划分，便可得到长度为1的子表。这样，整个算法的时间复杂度为O(nlogn)。
平均情况下，快速排序花费O(NlogN)时间。

例子运行结果

[main] INFO  QuickSortTest  - [1, 3, 4, 5, 6, 6]