日常算法——快速排序

快速排序

快速排序采用的思想是分治思想。
快速排序是找出一个元素（理论上可以随便找一个）作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值，如此作为基准的元素调整到排序后的正确位置。递归快速排序，将其他 n-1 个元素也调整到排序后的正确位置。最后每个元素都是在排序后的正 确位置，排序完成。所以快速排序算法的核心算法是分区操作，即如何调整基准的位置以及调整返回基准的最终位置以便分治递归。
如图：

代码实现

package Suanfa;

/**
 * Created by hushangjie on 2017/11/6. 
 */
 public class QuickSort {
    public static void sort(int[] arr, int _left, int _right) {
        int left = _left;
        int right = _right;
        int temp = 0;
        if (left <= right) {
            temp = arr[left];
            while (left != right) {
                while (left < right && arr[right] >= temp) {
                    right--;
                }
                arr[left] = arr[right];
                while (left < right && arr[left] <= temp) {
                    left++;
                }
                arr[right] = arr[left];
            }
            arr[left] = temp;
            sort(arr, 0, left - 1);
            sort(arr, left + 1, _right);
        }
    }

    public static void main(String[] args) {
        int[] a = {32, 2, 33, 22, 434};
        sort(a, 0, a.length - 1);
        for (int i = 0; i < a.length; i++) {
            System.out.println(a[i]);
        }
    }
}

特点

1. 当分区选取的基准元素为待排序元素中的最大或最小值时，为最坏的情况，时间复杂度和直接插入排序的一样，移动次数达到最大值 Cmax = 1+2+...+(n-1) = n*(n-1)/2 = O(n^2) 此时最好时间复杂为 O(n^2)

2. 当分区选取的基准元素为待排序元素中的"中值"，为最好的情况，时间复杂度为 O(nlog2n)。

3. 快速排序的空间复杂度为 O(log2n).

4. 当待排序元素类似[6,1,3,7,3]且基准元素为 6 时，经过分区，形成[1,3,3,6,7],两个 3 的相对位置发生了改变，所是快速排序是一种不稳定排序