快速排序(剑指offer )

import java.util.Random;


public class QuickSort {

    public static void main(String[] args) {
        int[] arr = {1, 8, 3, 9, 4, 5, 7, 6};
        quickSort(arr, 8, 0, 7);
        for (int i = 0; i < 8; i++) {
            System.out.println(arr[i]);
        }

//        int i = (int) (0.7 * 8);
//        System.out.println(i);

    }

    public static void quickSort(int[] arr, int length, int start, int end) {
        if (start == end) {
            return ;
        }
        int index = partition(arr, length, start, end);
        if (index > start) {
            quickSort(arr, length, start, index - 1);
        }

        if (index < end) {
            quickSort(arr, length, index + 1, end);
        }
    }
    // 分割
    public static int partition(int[] arr, int length, int start, int end) {
        if (arr == null || length == 0) {
            return 0;
        }
        // 随机取值 pivot
        int index = randomInt(start, end);
        // 交换到最后一个节点上
        swap(arr, index, end);
        // 双指针 small index
        int small = start - 1;
        for (index = start; index < end; index++) {
            
            if (arr[index] < arr[end]) {
                small++;
                if (small != index) {
                    swap(arr, index, small);
                }

            }
        }
        small++;
        swap(arr, small, end);
        return small;
    }
    public static int randomInt(int min, int max) {
//        return (int) (min + Math.random() * max);
        return (int) (min + Math.random()*(max - min +1));
    }
    // 中轴元素选取
    public static int randomIntrange(int[] arr, int start, int end) {
        int mid = start + (end - start) >> 1;
        int y1 = arr[start] > arr[mid] ? start : mid;
        int y2 = arr[start] > arr[end] ? start : end;
        int y3 = arr[mid] > arr[end] ? mid : end;
        if (y1 == y2) {
            return y3;
        }else {
            return y1 > y2 ? y2 : y1;
        }
    }

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

其他可以改进的地方（网络搜集） ：

1、 快速排序在处理小规模数据时的表现不好.这个时候可以改用插入排序(链接插入排序)。

当数据规模小于一定程度时，改用插入排序。具体小到何种规模时，采用插入排序，这个理

论上还不解，一些文章中说是 5 到 25 之间。SGI STL 中的快速排序采用的值是 10.

2、对于一个每个元素都完全相同的一个序列来讲，快速排序也会退化到 O(n^2)。

要将这种情况避免到，可以这样做：

在分区的时候，将序列分为 3 堆，一堆小于中轴元素，一堆等于中轴元素，一堆大于中轴元

素，下次递归调用快速排序的时候，只需对小于和大于中轴元素的两堆数据进行排序，中间

等于中轴元素的一堆已经放好