最小的K个数-快速排序

发表于 | | 阅读次数:

最小的K个数，最大的K个数等需要进行排序的，都可以用到分治的思想，利用快排快速解决

1.快速排序思想

快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

举一个例子：

对 3, 5, 1, 4, 2, 6进行快速排序

在第一次排序的时候，把待比较的值存储在临时空间中，初始值i为最左边的值，j为最右边的值

因为临时变量储存的是最左边的值，所以需要先从右向左进行遍历，否则右边的值会被覆盖。

从右向左找到第一个比temp小的值，位置为j，如第二行j=4时，arr[j]=2,替换a[i]的值。如第二行2，5，1，4，2，6

从左向右找到第一个比temp大的值，位置为i，如第三行i=1时，arr[i]=5,替换a[j]的值。因为在上一次操作中已经替换到a[i].结果如第三行。
继续如上操作，直到最后一次i=j时，temp替换掉arr[i]的，形成
2，1，3，4，5，6的临时有序数组。
对所有的子序列进行如上操作，即可达到全局有序。

最好时间复杂度O(nlogn),当所有的基准值为最小值时,最坏时间复杂度为O(N*N)。对于基准值的选择，最优选择则是把数组恰好二分，不过这只是理想状态，可以对首中尾取平均值进行基准的选择。

空间复杂度为存储栈的空间O(logn)

快速排序代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public void quickSort(int[] arr,int left,int right){
        if(left<right){
            int i=left;
            int j=right;
            int temp=arr[left];
            while(i<j){
                while(i<j&&arr[j]>=temp){
                    j--;
                }
                arr[i]=arr[j];
                while(i<j&&arr[i]<temp){
                    i++;
                }
                arr[j]=arr[i];
            }
            arr[i]=temp;
            quickSort(arr,left,i-1);
            quickSort(arr,i+1,right);
        }
    }

快速排序其实就是一个分治的思想：
对所有的子序列进行递归处理，所有的子序列排序，则全局有序

最小的K个数解答

如果运用了快速排序解决了数组有序性问题，则最小的K个数则是前k个数的数组集合

1
2
3
4
5
6
7
8
9
public int[] getLeastNumbers(int[] arr, int k) {
    if(arr.length==0||k==0){
        return new int[]{};
    }
    quickSort(arr,0,arr.length-1);
    int[] res=new int[k];
    System.arraycopy(arr,0,res,0,k);
    return res;
}

核心则还是快速排序。

当然对于这个最小K个数，只需要排序到K这个位置即可，对于K之后的位置无需排序。所以可以利用快排思想，找到K位置的基准值，返回之前的数组即可。