快速排序面试题

001什么是快速排序？

1）快排问题和荷兰国旗问题类似，快速排序采用的思想是分治思想。主要分两个步骤：

第一步：从要排序的数组中随便找出一个元素作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值都不小于基准值。

第二步就是对高段位和地段为两部分进行递归排序。

2）算法图解

【1】从【5,3,5,6,2,7】数组中，随机选取一个数（假设这里选的数是5）与最右边的7进行交换 ，如下图

【2】准备好以5为分界点，三个区域分别为小于区、大于区（大于区包含最右侧的一个数）和等于区，并准备一个指针，指向最左侧的数，如下图

【3】接下来，每次操作都拿指针位置的数与5进行比较，交换原则如下：

-----------------------------------------------------------

原则1：指针位置的数<5

拿指针位置的数与小于区右边第一个数进行交换

小于区向右扩大一位

指针向右移动一位

原则2：指针位置的数=5

指针向右移动一位

原则3：指针位置的数>5

拿指针位置的数与大于区左边第一个数进行交换

大于区向左扩大一位

指针位置不动

-------------------------------------------------------

根据图可以看出指针指向的第一个数是5，5=5，满足交换原则2，指针向右移动一位，如下图

【4】从上图可知，此时3<5，根据交换原则第1点，拿3和5（小于区右边第一个数）交换，小于区向右扩大一位，指针向右移动一位，结果如下图

【5】从上图可以看出，此时7>5,满足交换原则第3点，7和2(大于区左边第一个数)交换，大于区向左扩大一位，指针不动，如下图

【6】从上图可以看出，2<5,满足交换原则第1点，2和5（小于区右边第一个数）交换，小于区向右扩大一位，指针向右移动一位，得到如下结果

【7】从上图可以看出，6>5，满足交换原则第3点，6和6自己换，大于区向左扩大一位，指针位置不动，得到下面结果

【8】此时，指针与大于区相遇，则将指针位置的数6与随机选出来的5进行交换，就可以得到三个区域：小于区，等于区，大于区，周而复始完成最终的排序

002快速排序的代码实现？

public static void quickSort(int[] arr) {
    if (arr == null || arr.length < 2) {
	    return;
	}
	quickSort(arr, 0, arr.length - 1);
}
// arr[l..r]排好序
public static void quickSort(int[] arr, int L, int R) {
    if (L < R) {
        swap(arr, L + (int) (Math.random() * (R - L + 1)), R);
		int[] p = partition(arr, L, R);
		quickSort(arr, L, p[0] - 1); // < 区
		quickSort(arr, p[1] + 1, R); // > 区
	}
}
// 这是一个处理arr[l..r]的函数
// 默认以arr[r]做划分，arr[r] -> p     <p   ==p   >p
// 返回等于区域(左边界，右边界), 所以返回一个长度为2的数组res, res[0] res[1]
public static int[] partition(int[] arr, int L, int R) {
    int less = L - 1; // <区右边界
    int more = R; // >区左边界
    int index=L;
    while (index < more) { // L表示当前数的位置   arr[R]  ->  划分值
        if (arr[index] < arr[R]) { // 当前数   <  划分值
            swap(arr, ++less, index++);
        } else if (arr[index] > arr[R]) { // 当前数   >  划分值
            swap(arr, --more, index);
        } else {
            index++;
        }
    }
    swap(arr, more, R);
    return new int[] { less + 1, more };
}

003快速排序时间复杂度？

快速排序的时间复杂度在最坏情况下是O(N2)，平均的时间复杂度是O(N*lgN)。
假设被排序的数列中有N个数。遍历一次的时间复杂度是O(N)，需要遍历多少次呢? 至少lg(N+1)次，最多N次。 为什么最少是lg(N+1)次? 快速排序是采用的分治法进行遍历的，我们将它看作一棵二叉树，它需要遍历的次数就是二叉树的深度，而根据完全二叉树的定义，它的深度至少是lg(N+1)。因此，快速排序的遍历次数最少是lg(N+1)次。 为什么最多是N次? 这个应该非常简单，还是将快速排序看作一棵二叉树，它的深度最大是N。因此，快读排序的遍历次数最多是N次。

004快速排序稳定性？

快速排序是不稳定的算法，它不满足稳定算法的定义。