排序算法一快速排序

概述

　一种分治的排序算法，他将一个数组分成两个数组，将两部分独立的排序。

快速排序和归并排序是互补的

归并排序是将数组分成两个子数组分别排序，并将有序的子数组归并以将整个数组排序，

而快速排序将数组排序的方式是当两个子数组都有序时整个数组也就有序了。

快速排序的基本思想是：挖坑填数+分治法

1、先从数列中取出一个数作为基准数

2、分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边

3、再对左右区间重复第二步，直到各区间只有一个数

三数取中法选取基准值

　　  该排序适用于对数据量较大的数据进行排序，而对于数据量较小的数据则表现一般
　　基本思想:取第一个数，最后一个数，第（N/2）个数即中间数，三个数中数值中间的那个数作为基准值。

　　　　　　 举个例子，对于int a[] = { 2,5,4,9,3,6,8,7,1,0};，

　　　　　　 ‘2’、‘3’、‘0’，分别是第一个数，第（N/2）个是数，最后一个数，

　　　　　　 三个数中3最大，0最小，2在中间，所以取2为基准值。

class QuickSort {
    private static void quickSort(int[] end, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            //获取中值
            getPosition(end, left, mid, right);
            //value是中值，放在倒数第二位置
            int value = end[right - 1];
            //a向右找比中值大的与b向左找比中值小的，然后交换
            int a = left;
            int b = right - 1;
            while (true) {
                //左边比对照点小，向前走
                while (a<b && end[++a] <= value) {
                }
                //右边比对照点大，向后走
                while (a<b && end[--b] >= value) {
                }
                if (a < b) {
                    swap(end, a, b);
                } else  break;
            }
            swap(end, a, right - 1);
            quickSort(end, left, a - 1);
            quickSort(end, a + 1, right);
        }


    }

    //选定中值并排序，将中值置于倒数第一位便于排序时插入
    private static void getPosition(int[] end, int left, int mid, int right) {
        if (end[left] > end[mid]) {
            swap(end, left, mid);
        }
        if (end[left] > end[right]) {
            swap(end, left, right);
        }
        if (end[mid] > end[right]) {
            swap(end, mid, right);
        }
        //选定中值并排序，将中值置于倒数第一位便于排序时插入
        swap(end, mid, right - 1);
    }

    private static void swap(int[] arr, int a, int b) {
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}