改进排序算法：快速排序（对冒泡排序的改进）

快速排序的基本思想：通过一趟排序将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序的目的。

Partition函数的作用：选取当中的一个关键字，将它放到一个位置，使得它左边的值都比它小，右边的值比它大，这样的关键字被称为枢轴。

一：取low端的值作为枢轴记录，从high端开始交换

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = {4,5,1,6,2,7,3,8,8,4};
        System.out.println(s.GetLeastNumbers_Solution(arr, 4));   //输出：[1, 2, 3, 4]
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input.length <= 0 || k <= 0 || k > input.length) return list;
        sort(input, 0, input.length - 1);
        System.out.println(Arrays.toString(input));    //输出：[1, 2, 3, 4, 4, 5, 6, 7, 8, 8]
        for (int i = 0; i < k; i++)
            list.add(input[i]);
        return list;
    }
    private void sort(int[] arr, int low, int high)
    {
        int index;
        if (low < high)
        {
            index = partition(arr, low, high);
            sort(arr, low, index - 1);
            sort(arr, index + 1, high);
        }
    }
    private int partition(int[] arr, int low, int high)
    {
        int flag = arr[low];
        while(low < high)
        {
            while (low < high && arr[high] >= flag)
                high--;
            swap(arr, low, high);
            while(low < high && arr[low] <= flag)
                low++;
            swap(arr, low, high);


        }
        return low;
    }
    private void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

二：取high端的值作为枢轴记录，从low端开始交换

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = {4,5,1,6,2,7,3,8,8,4};
        System.out.println(s.GetLeastNumbers_Solution(arr, 4));  //输出：[1, 2, 3, 4]
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input.length <= 0 || k <= 0 || k > input.length) return list;
        sort(input, 0, input.length - 1);
        System.out.println(Arrays.toString(input));  //输出：[1, 2, 3, 4, 4, 5, 6, 7, 8, 8]
        for (int i = 0; i < k; i++)
            list.add(input[i]);
        return list;
    }
    private void sort(int[] arr, int low, int high)
    {
        int index;
        if (low < high)
        {
            index = partition(arr, low, high);
            sort(arr, low, index - 1);
            sort(arr, index + 1, high);
        }
    }
    private int partition(int[] arr, int low, int high)
    {
        int flag = arr[high];
        while(low < high)
        {
            while(low < high && arr[low] <= flag)
                low++;
            swap(arr, low, high);
            while (low < high && arr[high] >= flag)
                high--;
            swap(arr, low, high);

        }
        return low;
    }
    private void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

快速排序的复杂度分析：

时间复杂度：

快速排序的时间性能取决于快速排序递归的深度，可以用递归树来描述递归算法的执行情况。若取的枢轴正好是待排序的序列的中间值，则递归树是平衡的，性能也比较好。

在最优情况下，Partition每次都划分得很均匀，如果排序n个关键字，其递归树的深度为[log2n]+1，即仅需递归log2n次，需要时间为T(n)的话，第一次Partition需要对整个数组扫描一遍，做n次比较，然后，获得的枢轴将数组一分为二，各自还需要T(n/2)的时间。不断划分下去。在最优的情况下，快排算法的时间复杂度为O(nlogn)。

在最坏的情况下，待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列，另一个为空。递归树画出来，为一棵斜树。此时需要执行n-1次递归调用，且第i次划分需要经过n-i次关键字的比较才能找到第i个记录，也就是枢轴的位置，最终时间复杂度为O(n^2)。

平均情况下，时间复杂度为O(nlogn)。

空间复杂度：

主要是递归造成的栈空间的使用。

最好情况下，递归树的深度为log2n，空间复杂度为O(logn)。

最坏情况下，需要进行n-1次递归调用，空间复杂度为O(n)。

平均情况下，空间复杂度为O(logn)。

由于关键字的比较和交换是跳跃进行的，快速排序是一种不稳定的排序方法。

快速排序的优化：

一：优化选取枢轴

三数取中法：取三个关键字，先进行排序，将中间数作为枢轴。一般是取左端、右端和中间三个数，也可以随机选取。这样，至少这个中间数一定不会是最小或者最大的数。

三数取中对小数组来说有很大概率可以选择到一个比较好的枢轴，但是对于非常大的待排序的序列还不足以保证能够选择出一个好的枢轴。因此可以九数取中，它先从数组中分三次取样，每次取三个数，三个样品各取出中数，然后从这三个中数当中再取出一个中数作为枢轴。

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = {4,5,1,6,2,7,3,8,8,4};
        System.out.println(s.GetLeastNumbers_Solution(arr, 4));   //输出：[1, 2, 3, 4]
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input.length <= 0 || k <= 0 || k > input.length) return list;
        sort(input, 0, input.length - 1);
        System.out.println(Arrays.toString(input));    //输出：[1, 2, 3, 4, 4, 5, 6, 7, 8, 8]
        for (int i = 0; i < k; i++)
            list.add(input[i]);
        return list;
    }
    private void sort(int[] arr, int low, int high)
    {
        int index;
        if (low < high)
        {
            index = partition(arr, low, high);
            sort(arr, low, index - 1);
            sort(arr, index + 1, high);
        }
    }
    private int partition(int[] arr, int low, int high)
    {
        int m = low + (high - low) / 2;
        if (arr[low] > arr[high]) swap(arr, low, high);
        if (arr[m] > arr[high]) swap(arr,m, high);
        if (arr[low] < arr[m]) swap(arr, low, m); //此时，low端的值为中间值
        int flag = arr[low];
        while(low < high)
        {
            /*while (low < high && arr[high] >= flag) //无论从low端开始交换还是从high端开始交换都可以
                high--;
            swap(arr, low, high);
            while(low < high && arr[low] <= flag)
                low++;
            swap(arr, low, high);*/
            while(low < high && arr[low] <= flag)
                low++;
            swap(arr, low, high);
            while (low < high && arr[high] >= flag)
                high--;
            swap(arr, low, high);
        }
        return low;
    }
    private void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

二：优化不必要的交换

同上：取low端的值作为枢轴记录，从high端开始交换；取high端的值作为枢轴记录，从low端开始交换

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = {4,5,1,6,2,7,3,8,8,4};
        System.out.println(s.GetLeastNumbers_Solution(arr, 4));   //输出：[1, 2, 3, 4]
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> list = new ArrayList<>();
        if (input.length <= 0 || k <= 0 || k > input.length) return list;
        sort(input, 0, input.length - 1);
        System.out.println(Arrays.toString(input));    //输出：[1, 2, 3, 4, 4, 5, 6, 7, 8, 8]
        for (int i = 0; i < k; i++)
            list.add(input[i]);
        return list;
    }
    private void sort(int[] arr, int low, int high)
    {
        int index;
        if (low < high)
        {
            index = partition(arr, low, high);
            sort(arr, low, index - 1);
            sort(arr, index + 1, high);
        }
    }
    private int partition(int[] arr, int low, int high)
    {
        int flag = arr[low];
        while(low < high)
        {
            while (low < high && arr[high] >= flag)
                high--;
            arr[low]= arr[high];
            
            while(low < high && arr[low] <= flag)
                low++;
            arr[high] = arr[low];
        }
        arr[low]= flag;
        return low;
    }
}

三：优化小数组时的排序方案

如果数组非常小，直接插入排序比快速排序更好。（直接插入排序是简单排序中性能最好的）

快速排序中，用到了递归操作，在大量数据排序时，这点性能影响对于它的整体算法优势而言可以忽略。

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static final int CUTOFF = 7;
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = {4,5,1,6,2,7,3,8,8,4};
        System.out.println(s.GetLeastNumbers_Solution(arr, 4));   //输出：[1, 2, 3, 4]
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        ArrayList<Integer> list = new ArrayList<>();
        if (input.length <= 0 || k <= 0 || k > input.length) return list;

        sort(input, 0, input.length - 1);

        System.out.println(Arrays.toString(input));    //输出：[1, 2, 3, 4, 4, 5, 6, 7, 8, 8]

        for (int i = 0; i < k; i++)
            list.add(input[i]);

        return list;
    }
    private void sort(int[] arr, int low, int high)
    {
        int index;
        if ((high - low) > CUTOFF)
        {
            index = partition(arr, low, high);
            sort(arr, low, index - 1);
            sort(arr, index + 1, high);
        }
        else
            InsertSort(arr, low, high);
    }
    private int partition(int[] arr, int low, int high)
    {
        int flag = arr[low];
        while(low < high)
        {
            while (low < high && arr[high] >= flag)
                high--;
            arr[low]= arr[high];

            while(low < high && arr[low] <= flag)
                low++;
            arr[high] = arr[low];
        }
        arr[low]= flag;
        return low;
    }
    private void InsertSort(int[] arr, int low, int high) //直接插入排序
    {
        for (int i = low + 1; i <= high; i++)
        {
            if (arr[i] < arr[i - 1])
            {
                int save = arr[i];
                int j = i - 1;
                for (; j >= 0 && arr[j] > save; j--)
                    arr[j + 1] = arr[j];
                arr[j + 1] = save;
            }
        }
    }
}

四：优化递归操作

sort函数在其尾部有两次递归操作。如果待排序的序列划分极端不平衡，递归深度将趋近于n，而不是平衡时的logn，这不仅仅是速度快慢的问题。

栈的大小是有限的，每次递归调用会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多。

所以要减少递归。

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
    public static final int CUTOFF = 7;
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = {4,5,1,6,2,7,3,8,8,4};
        System.out.println(s.GetLeastNumbers_Solution(arr, 4));   //输出：[1, 2, 3, 4]
    }
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {

        ArrayList<Integer> list = new ArrayList<>();
        if (input.length <= 0 || k <= 0 || k > input.length) return list;

        sort(input, 0, input.length - 1);

        System.out.println(Arrays.toString(input));    //输出：[1, 2, 3, 4, 4, 5, 6, 7, 8, 8]

        for (int i = 0; i < k; i++)
            list.add(input[i]);

        return list;
    }
    private void sort(int[] arr, int low, int high)
    {
        int index;
        if ((high - low) > CUTOFF)
        {
            while (low < high)
            {
                index = partition(arr, low, high);
                sort(arr, low, index - 1);
                low = index + 1; //尾递归，采用迭代而不是递归的方式，缩减了堆栈深度，提高了整体性能
            }

        }
        else
            InsertSort(arr, low, high);
    }
    private int partition(int[] arr, int low, int high)
    {
        int flag = arr[low];
        while(low < high)
        {
            while (low < high && arr[high] >= flag)
                high--;
            arr[low]= arr[high];

            while(low < high && arr[low] <= flag)
                low++;
            arr[high] = arr[low];
        }
        arr[low]= flag;
        return low;
    }
    private void InsertSort(int[] arr, int low, int high) //直接插入排序
    {
        for (int i = low + 1; i <= high; i++)
        {
            if (arr[i] < arr[i - 1])
            {
                int save = arr[i];
                int j = i - 1;
                for (; j >= 0 && arr[j] > save; j--)
                    arr[j + 1] = arr[j];
                arr[j + 1] = save;
            }
        }
    }
}

import java.util.Arrays;

public class Solution {
    public static final int CUTOFF = 10;
    public static void main(String[] args) {
        Solution s = new Solution();
        int[] arr = {4,5,1,6,2,7,3,8,8,4,2};
        s.quicksort(arr, 0, arr.length - 1);
        System.out.println(Arrays.toString(arr)); //输出：[1, 2, 2, 3, 4, 4, 5, 6, 7, 8, 8]
    }
    private void quicksort(int[] arr, int low, int high)
    {
        if (low + CUTOFF <= high)
        {
            int m = (high + low) / 2;
            if (arr[m] < arr[low]) swap(arr, low, m);
            if (arr[high] < arr[low]) swap(arr, low, high);
            if (arr[high] < arr[m]) swap(arr, m, high); //此时，m端的值为中间值

            swap(arr, m, high - 1);
            int flag = arr[high - 1];

            int i = low;
            int j = high - 1;
            for ( ; ; )
            {
                while(arr[++i] < flag);
                while (arr[--j] > flag);
                if (i < j)
                    swap(arr, i, j);
                else
                    break;
            }
            swap(arr, i, high - 1);

            quicksort(arr, low, i - 1);
            quicksort(arr, i + 1, high);
        }
        else
            InsertSort(arr, low, high);
    }
    private void InsertSort(int[] arr, int low, int high) //直接插入排序
    {
        for (int i = low + 1; i <= high; i++)
        {
            if (arr[i] < arr[i - 1])
            {
                int save = arr[i];
                int j = i - 1;
                for (; j >= 0 && arr[j] > save; j--)
                    arr[j + 1] = arr[j];
                arr[j + 1] = save;
            }
        }
    }
    private void swap(int[] arr, int i, int j)
    {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

}

求k个最小的数： 点击打开链接