算法-堆排序、快排-最小K个数且排序输出

浅浅的花香味﹌ 2023-07-09 06:24 24阅读 0赞

# 算法-堆排序、快排-最小K个数且排序输出 #

# 1 概述 #

## 1.1 题目出处 ##

https://leetcode-cn.com/problems/smallest-k-lcci/

## 1.2 题目描述 ##

设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。

示例：

输入： arr = \[1,3,5,7,2,4,6,8\], k = 4  
输出： \[1,2,3,4\]  
提示：

0 <= len(arr) <= 100000  
0 <= k <= min(100000, len(arr))

# 2 题解 #

## 2.1 大顶堆 ##

### 2.1.1 解题思路 ###

1.  采用大顶堆，存最小的k个数。  
    具体来说， 先存前k个数，并按大顶堆规则调整；随后一次遍历其他数和堆顶树比较如果更大则跳过；更小则替换该元素且从堆顶位置开始调整堆
2.  得到排好序的大顶堆，该堆就存了该数组最小的k个数
3.  采用堆排序，随后输出已排序堆即可

### 2.1.2 代码 ###

class Solution { 
        // 1.采用大顶堆，存最小的k个数
        // 2.然后采用堆排序输出这批数字
        public int[] smallestK(int[] arr, int k) { 
            if(arr == null || arr.length == 0 || k<=0){ 
                return new int[0];
            }
            int start;
    
            // 合法堆大小
            int heapSize = arr.length < k ? arr.length : k;
            
            // 找到起点
            if(heapSize % 2 == 0){ 
                start = heapSize/2 - 1;
            }else{ 
                start = heapSize/2;
            }
    
            // 将前堆大小个数元素直接放入堆，并从最后一层适当元素开始调整堆
            for(; start >= 0; start--){ 
                adjustMaxHeap(arr, start, heapSize);
            }
    
    
            // 现在我们得到了一个大顶堆，开始从heap+1元素开始和堆顶元素比较，
            // 如果更大则跳过；更小则替换该元素且从堆顶位置开始调整堆
            if(heapSize<arr.length){ 
                int tmp = 0;
                for(int i = heapSize;i<arr.length;i++){ 
                    if(arr[i]<arr[0]){ 
                        tmp = arr[0];
                        arr[0] = arr[i];
                        arr[i] = tmp;
                        adjustMaxHeap(arr,0,heapSize);
                    }
                }
            }
            
            // 现在经过调整，我们得到了一个大小为k的大顶堆，该大顶堆为最小的k个数
            // 我们开始堆该堆进行排序:将堆顶和堆尾元素交换，并从新堆顶开始调整堆（排除堆尾已排序元素）
            for(int i = 0 ; i < heapSize; i++){ 
                int tmp = arr[0];
                arr[0] = arr[heapSize-i-1];
                arr[heapSize-i-1] = tmp;
                adjustMaxHeap(arr,0,heapSize-i-1);
            }
    
            // 将已排序的堆赋值给堆大小的新数组，并返回
            int[] result = new int[heapSize];
            for(int i = 0; i<heapSize; i++){ 
                result[i] = arr[i];
            }
            return result;
        }
    
        public void adjustMaxHeap(int arr[], int start, int length){ 
            if(length<0){ 
                return;
            }
            // 暂存目标数
            int tmp = arr[start];
            // 比较该节点和孩子节点中的大者，如果比孩子大则不动
            // 如果比孩子小则调整该孩子和本身。且该孩子不小于另一个孩子，不用再交换
            for(int j = (start+1)*2 -1 ; j<length; j = (start+1)*2 -1 ){ 
                // 验证左孩子的j合法性
                if(j < length){ 
                    // 判断右孩子是否存在，存在就要和左孩子比较取较大者
                    if(j+1 < length){ 
                        j = arr[j] > arr[j+1] ? j : j + 1;
                    }
                    //当前节点比两个孩子中大者还大，说明当前位置就是合法位置
                    if(tmp > arr[j]){ 
                        break;
                    }
                    //否则将大孩子值赋给当前位置
                    arr[start] = arr[j];
                    // 继续从原来大孩子的位置开始和大孩子的孩子比
                    start = j;
                }
            }
            // 到这里时，start位置即为合法位置
            arr[start] = tmp;
        }
    }

### 2.1.3 时间复杂度 ###

最优：O(nlogn):  
最差：O(nlogn):  
平均：O(nlogn)

### 2.1.4 空间复杂度 ###

O(min(n,k))

### 2.1.5 注意事项 ###

不要使用  
`Arrays.sort(arr) Arrays.copyOf(arr, k)`等方法，  
面试官不会满意，同时有可能自己面试时可能忘记函数名。

## 2.2 快排改 ##

### 2.2.1 解题思路 ###

想到快速排序思想，只要找到一个分隔数:  
左边和分隔元素加起来一共K个数，就找到了最小的k个数。

如果不满足就视情况继续找左边或右边。

### 2.2.2 代码 ###

class Solution { 
        // 想到快速排序思想，只要找到一个分隔数，
        // 左边和自己加起来一共K个数，就找到了最小的k个数
        public int[] getLeastNumbers(int[] arrs, int k) { 
            // 快排
            quickSort(arrs, 0, arrs.length-1, k);
            // 将结果前k个复制给新数组即可
            int[] result = new int[k];
            for(int i = 0; i < k; i++){ 
                result[i] = arrs[i];
            }
            return result;
        }
        // 改动版本快排,k为需要找到的k个最小的数字
        public void quickSort(int[] arrs, int low, int high, int k){ 
            if(low >= high){ 
                // 就是他自己或其他异常情况，直接返回
                return;
            }
            // 存储分隔元素
            int tmp = arrs[low];
            int i = low,j=high;
            while(i<j){ 
                // 从high最右边开始往左，分别于分隔元素比较，直到找到小于等于分个元素的
                while(i<j&&arrs[j]>tmp){ 
                    j--;
                }
                if(i<j){ 
                    // 此时就将该元素赋值给分隔元素所在位置，且将左边i位置+1
                    // 注意此时j位置元素已经复制走了，可迎接下一个移动过来的比分隔元素大的元素
                    arrs[i++] = arrs[j];
                }
                // 同理，又从左往右找出比分隔元素大的，并放入待交换位置
                while(i<j&&arrs[i]<=tmp){ 
                    i++;
                }
                if(i<j){ 
                    arrs[j--] = arrs[i];
                }
            }
            // 此时，i==j，此位置要么就是分隔元素自己要么就是已经被交换走的元素位置
            // 直接将分隔元素放到此位置即可
            arrs[i] = tmp;
            if(i + 1 - low < k){ 
                // 符合要求元素小于k，就还需要在分隔元素右边找k-(i + 1 - low)个符合要求的，继续快排
                quickSort(arrs, i+1, high, k-(i + 1 - low));
            } else if(i + 1 - low > k){ 
                // 符合要求元素大于k，就还需要在分隔元素左边找k个符合要求的，继续快排
                quickSort(arrs, low, i-1, k);
            }
        }
    }

### 2.2.3 时间复杂度 ###

最优：O(n)  
最差：O(n + n-1 + n-2 +… n-n) = O(`n^2`\-`(1+n)*n/2`) = O((n(n-1)/2))=O(`n^2`)  
平均：O(n+n/2+n/4+…+1) = O(n)

### 2.2.4 空间复杂度 ###

O(1)

### 2.2.5 注意事项 ###

*  本算法需要将数据全部读入内存构建数组，不适合海量数据。
    
    如果非要用，就只能每次读入一条或一小批数据，和分隔元素作对比，比分隔元素小的写入一个文件。下次又去读这个文件，直到找到合适的。但是这种操作会经过多次磁盘读写，效率极低。
 *  如果不能修改原始数组，还需要申请额外空间存储原始数组。

## 2.3 分布式算法 ##

### 2.3.1 解题思路 ###

如果是多机环境，可以将该任务拆分成多个任务，每个任务找出前K大的，最后再来一次合并排序即可找出全局前K大的。

## 2.4 排序算法 ##

### 2.4.1 冒泡排序 ###

#### 2.4.1.1 解题思路 ####

每趟将最大的数字找出，只需要K趟即可找出最大的K个数。

时间复杂度O(K\*N)，空间复杂度O(N)。

需要数据全部读入，不适用于海量数据。

### 2.4.2 交换排序 ###

#### 2.4.2.1 解题思路 ####

每次选出最大的元素，与最前面的元素交换位置。K趟后得到最大的前K个元素。