Android面试题集锦二（算法篇）

• 快速排序是对冒泡排序的一种改进，也是采用分治法的一个典型的应用。

• 概念：
  1、任意选取一个数据（比如数组中的第一个数）作为关键数据，我们称为基准数（Pivot）
  2、将所有小于基准数的都放到它前面，所有比它大的都放到它后面，这个过程成为一趟快速排序，也称为分区操作(partition）

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

• 基准的选取：最优的情况是基准值刚好取在无序区数值的中位数，这样能够最大效率地让两边排序，同时最大地减少递归划分的次数，但是一般很难做到最优。基准的选取一般有三种方式，选取数组的第一个元素，选取数组的最后一个元素，以及选取第一个、最后一个以及中间的元素的中位数（如4 5 6 7, 第一个4, 最后一个7, 中间的为5, 这三个数的中位数为５, 所以选择5作为基准）。

• Dual-Pivot快排：双基准快速排序算法，其实就是用两个基准数, 把整个数组分成三份来进行快速排序，在这种新的算法下面，比经典快排从实验来看节省了10%的时间。

快速排序（升序）原理实现图示：
规则：
1、当前元素大于基准数，不做任何变化。
2、当前元素小于等于基准数时，分割指示器右移一位；当前元素下标小于等于分割指示器时，当前元素保持不动；
当前元素下标大于分割指示器时，当前元素和分割指示所指元素交换。

public class QuickSort {
    public static int[] sort(int[] array, int start, int end) {
        if (array.length < 1 || start < 0 || end >= array.length || start > end)
            return null;
        
        int zoneIndex = partition(array, start, end);
        if (zoneIndex > start)
            sort(array, start, zoneIndex - 1);
        if (zoneIndex < end)
            sort(array, zoneIndex + 1, end);
        System.out.println("本轮排序后的数组");
        PrintArray.printIndex(array,start,end);
        System.out.println("--------------------");
        return array;
    }
    
    public static int partition(int[] array, int start, int end) {
        int pivot = (int) (start + Math.random() * (end - start + 1));
        System.out.println("开始下标："+start+",结束下标:"+end+",基准数下标："
                +pivot+",元素值:"+array[pivot]);
        
        int zoneIndex = start - 1;
        swap(array, pivot, end);
        for (int i = start; i <= end; i++){
            if (array[i] <= array[end]) {
                zoneIndex++;
                if (i > zoneIndex)
                    swap(array, i, zoneIndex);
            }
            System.out.println("zoneIndex："+zoneIndex+",i:"+i);
            PrintArray.printIndex(array,start,end);
        }
        System.out.println("---------------");
        return zoneIndex;
    }

    
    public static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }

    public static void main(String[] args) {
        PrintArray.print(PrintArray.SRC);
        System.out.println("============================================");
        int[] dest = QuickSort.sort(PrintArray.SRC,0,PrintArray.SRC.length-1);
        PrintArray.print(dest);
    }
}