04.快速排序

冒泡排序

1.基本思想
2.排序过程
3.代码实现
4.如何优化
5.复杂度
6.使用场景

1.基本思想

快速排序是通过一趟排序将要排序的数据分割成独立的两部分。
其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序。
整个排序过程可以递归进行，以此达到整个数据变成有序序列。

2.排序过程

1、设待排序数组为data
2、设置key = 0，i = 0，j = data.length – 1，从j开始从后往前遍历数组，当找到data[j] < data[key]的数的时候，交换j和key位置的数，让key = j，j递减；然后开始递增i，当找到data[i]>= data[key]时，交换i和key位置的数，让key = i，i递减。
3、当i < j时，重复第二步，直到i == j，此时将数组以i为界分割为两段，一段是[0, i - 1]，一段是[i + 1, data.length - 1]，对这两段分别进行快速排序，直到不能再分段为止，排序结束。
image

3.代码实现

代码如下所示

/**
 * 递归的快速排序
 * @param begin 排序的开始位置
 * @param end 排序的结束位置
 */
public static void Sort(int[] array , int begin, int end) {
    if (begin >= end) {  //  如果分段中的数小于等于1个，直接返回
        return;
    }
    int left = begin;
    int right = end;
    int key = array[left];
    while (left < right) {
        while (right > left) {
            if (array[right] <= key) {  //  注意在这两处判断的地方要有一处有等于号
                //交换两个数的位置
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
                break;
            }
            right--;  //  不管是否发生交换，这里都需要移动
        }
        while (left < right) {
            if (array[left] > key) {
                //交换两个数的位置
                int temp = array[left];
                array[left] = array[right];
                array[right] = temp;
                break;
            }
            left++;  //  不管是否发生交换，这里都需要移动
        }
    }
    Sort(array , begin, left - 1);  // 递归时记得减1和加1
    Sort(array , left + 1, end);

    for(int i=0;i<array.length;i++){
        System.out.println("yc1-----" +array[i]);
    }
}

4.如何优化

1.当待排序序列的长度分割到一定大小后，使用插入排序。
2.快排函数在函数尾部有两次递归操作，我们可以对其使用尾递归优化。优化后，可以缩减堆栈深度，由原来的O(n)缩减为O(logn)，将会提高性能。
3.从左、中、右三个数中取中间值。

5.复杂度

快速排序的最优时间复杂度为O(nlogn)，最差时间复杂度为O(n2)，平均时间复杂度为O(nlogn)，空间复杂度为O(n)。具有速度快，适用范围广（实数都可以用），使用方便等优点。缺点在于在最差情况下（逆序或者全部相等），时间复杂度很高，达到O(n2)。并且迭代深度过深，容易引发栈溢出错误。