①归并排序、快速排序、堆排序、计数排序[算法、代码模板、面试题]

心已赠人 2024-04-17 10:18 35阅读 0赞

![在这里插入图片描述][8d8e0d8a542946af858489a536162608.gif_pic_center]

> 个人简介：Java领域新星创作者；阿里云技术博主、星级博主、专家博主；正在Java学习的路上摸爬滚打，记录学习的过程~  
> 个人主页：[.29.的博客][.29.]  
> 学习社区：[进去逛一逛~][Link 1]

> ![在这里插入图片描述][be111d444fa34ccf8a39c17607ee05b7.png]

#### 排序\[算法、代码模板、面试题\] ####

*  ①归并排序、快速排序 、堆排序、计数排序
 *   *  ?归并排序
     *   *  ⚪步骤
         *  ⚪实现
         *  ⚪复杂度
     *  ?快速排序
     *   *  ⚪步骤
         *  ⚪实现
         *  ⚪复杂度
     *  ?堆排序
     *   *  ⚪步骤
         *  ⚪实现
         *  ⚪复杂度
     *  ?912. 排序数组
     *  ?315. 计算右侧小于当前元素的个数
     *  ?561. 数组拆分
     *  ?1122. 数组的相对排序（计数排序）
     *  ?268. 丢失的数字（计数排序）
     *  ?215. 数组中的第K个最大元素
     *  ?347. 前 K 个高频元素
     *  ?LCR 159. 库存管理 III(计数排序)
     *  ?LCR 170. 交易逆序对的总数

--------------------

## ①归并排序、快速排序 、堆排序、计数排序 ##

### ?归并排序 ###

#### ⚪步骤 ####

`归并排序`：

归并排序是一种分治法（Divide and Conquer）的经典排序算法，它的基本思想是将原始数组划分成较小的数组，然后递归地对这些小数组进行排序，最后再将排好序的小数组合并成一个整体有序的数组。下面是\*\*归并排序的详细过程： \*\*

`详细步骤`：

**分解（Divide）:**

*  将数组一分为二，找到中间位置。
 *  递归地对左右两个子数组进行分解，直到每个子数组只有一个元素。

**排序（Conquer）：**

*  当每个子数组只包含一个元素时，认为它已经有序。

**合并（Merge）：**

*  将两个有序的子数组合并成一个有序的数组。
 *  创建一个临时数组，依次比较两个子数组的元素，将较小的元素放入临时数组。
 *  如果其中一个子数组的元素已经全部放入临时数组，将另一个子数组的剩余部分直接放入临时数组。
 *  将临时数组复制回原始数组的相应位置，完成合并。

#### ⚪实现 ####

`算法实现`：

public class mergeSortTest {
        
    	
    	//main函数，用于测试
    	public static void main(String[] args) {
        
    		//手动创建数组
    		int[] arr = new int[] {
        1,5,88,3,-8,7,256,-8,6,15,-96};
    		//使用归并排序
    		process(0,arr.length-1,arr);
    		//遍历排序后数组
    		for(int i = 0;i < arr.length;++i) {
        
    			System.out.print(arr[i] + " ");
    		}
    	}
    
    	//分解 + 合并（分解合并过程中已完成排序）：
    	public static void process(int L, int R, int[] arr) {
        
    		if(L == R) return;            //下标重合，结束
    		int mid = L + ((R - L) >> 1); //获取中间下标mid、 (R - L) >> 1 等同于 (R - L) / 2
    		process(L , mid, arr);        //分解左子数组
    		process(mid + 1, R, arr);     //分解右子数组
    		merge(L, mid, R, arr);        //合并
    	}
    	
    	//合并：
    	public static void merge(int L, int mid, int R, int[] arr) {
        
    		int[] help = new int[R - L + 1];  //帮组数组
    		int p1 = L;                       //左子数组起始下标
    		int p2 = mid + 1;                 //右子数组起始下标
    		int i = 0;                        //帮组数组起始下标
    		
    		//合并，两个子数组元素按顺序比较，较小的元素放入帮组数组，重复此步骤。
    		while(p1 <= mid && p2 <= R) {
        
    			help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
    		}
    		while(p1 <= mid) {
        
    			help[i++] = arr[p1++];
    		}
    		while(p2 <= R) {
        
    			help[i++] = arr[p2++];
    		}
    		
    		//将帮助数组的元素赋值回元素组。
    		for(i = 0;i < help.length; ++i) {
        
    			arr[i + L] = help[i];
    		}
    	}
    	
    }

#### ⚪复杂度 ####

`复杂度分析`：

*  **时间复杂度：** O(n log n) - 归并排序始终都是O(n log n)的，无论最坏情况还是平均情况。
 *  **空间复杂度：** O(n) - 归并排序需要一个与原始数组同样大小的辅助数组来进行合并操作，因此空间复杂度为O(n)。

--------------------

### ?快速排序 ###

#### ⚪步骤 ####

`快速排序`：

快速排序（Quick Sort）是一种常用的基于分治思想的排序算法。它的基本思想是通过一趟排序将待排序的记录分割成独立的两部分，其中一部分的所有记录均比另一部分的记录小，然后分别对这两部分记录继续进行排序，以达到整个序列有序的目的。快速排序的核心是选择一个基准元素，将小于等于基准的元素放在左边，大于基准的元素放在右边，然后对左右两个子序列分别递归地应用相同的方法。

`详细步骤`：

1.  **选择基准元素：**
    
     *  从待排序数组中选择一个元素作为基准元素。通常选择第一个元素、最后一个元素或者中间元素。（本文等概率随机选取一个元素作为基准，避免最坏复杂度的发生）
2.  **分区（Partition）：**
    
     *  将数组中小于等于基准的元素放在基准的左边，大于基准的元素放在右边。这一步通常称为分区操作。
     *  使用两个指针，一个在数组的起始位置，一个在数组的结束位置，分别向中间移动，交换不符合条件的元素，直到两个指针相遇。
3.  **递归排序：**
    
     *  对基准左右两侧的子数组进行递归排序。重复以上步骤，直到每个子数组的大小为1或0。

#### ⚪实现 ####

`算法实现`：

public class Qsort {
        
        //main函数，用于测试
    	public static void main(String[] args) {
        
    		//手动创建数组，用于测试
    		int[] arr = new int[] {
        1,5,99,-29,698,-111,0,63,88,3,3,7,1,-8,7,256};
    		
    		//若数组为空，长度<2等情况，无需排序
    		if(arr == null || arr.length < 2) {
        
    			return;
    		}
    		
    		//使用快速排序，传入数组头部和尾部下标
    		quickSort(0, arr.length-1, arr);
    		for(int i = 0;i < arr.length;++i) {
        
    			System.out.print(arr[i] + " ");
    		}
    	}
    	
    	//快速排序函数：
    	public static void quickSort(int L, int R, int[] arr) {
        
    		//下表不越界情况下：进行基准选取、划分、递归排序
    		if(L < R) {
        
    			//使用random函数，随机选取一个元素作为基准，使得复杂度总是O(n log n)
    			swap(R, L + (int)(Math.random() * (R - L + 1)), arr);
    			//进行划分，获取到两个边界值：小于基准的边界less，大于基准的边界more
    			//p[0] = less + 1 ，p[1] = more - 1
    			int[] p = partition(L, R, arr);
    			//分别对划分后的子数组继续进行上述操作，是为递归排序
    			quickSort(L, p[0] - 1, arr);
    			quickSort(p[1] + 1, R, arr);
    		}
    	}
    	
    	//划分函数：
    	public static int[] partition(int L, int R, int[] arr) {
        
    		//定义小于基准的边界less，大于基准的边界more
    		int less = L - 1;
    		int more = R;
    		//从数组起始下标L开始遍历，直到超过大于基准的边界more，即下标越界
    		while(L < more) {
        
    			//当前元素小于基准，与less边界外的元素交换，less边界扩展1位，下一元素作为当前元素
    			if(arr[L] < arr[R]) {
                
    				swap(++less, L++, arr);
    			//当前元素大于基准，与more边界外的元素交换，more边界扩展1位，交换后，当前元素未被比较，无需后移
    			}else if(arr[L] > arr[R]) {
        
    				swap(--more, L, arr);
    			//等于基准，无需交换，直接后移
    			}else {
        
    				++L;
    			}
    		}
    		//划分完成后，将数组末尾的基准元素与more边界位置元素交换，真正的more边界变为more + 1
    		swap(more, R, arr);
    		//将边界存入数组返回：
    		return new int[] {
        less + 1, more};
    	}
    	
    	//交换函数：
    	public static void swap(int a, int b, int[] arr) {
        
    		int tmp = arr[a];
    		arr[a] = arr[b];
    		arr[b] = tmp;
    	}
        
    }

#### ⚪复杂度 ####

`复杂度分析`：

*  **时间复杂度：** 平均情况下为O(n log n)，最坏情况为O(n^2)。快速排序的性能高度依赖于选择的基准元素。
 *  **空间复杂度：** O(log n) - 快速排序是一种原地排序算法，只需要常数级别的额外空间用于递归调用的栈。

--------------------

### ?堆排序 ###

#### ⚪步骤 ####

`堆排序`：

堆排序（Heap Sort）是一种基于二叉堆数据结构的排序算法，它利用堆的性质进行排序。堆是一个完全二叉树，可以分为最大堆和最小堆两种类型。在最大堆中，父节点的值大于或等于其子节点的值；而在最小堆中，父节点的值小于或等于其子节点的值。

以下是堆排序的详细步骤：

`详细步骤`：

1.  **建堆（Heapify）：**
    
     *  将待排序的数组构建成一个堆。建堆的过程是从最后一个非叶子节点开始，依次向上调整各个子树，使其满足堆的性质。
2.  **排序：**
    
     *  交换堆顶元素（最大或最小元素）和堆的最后一个元素，然后将堆的大小减 1。
     *  再次调整堆，使其满足堆的性质。
     *  重复上述步骤，直到堆的大小为 1，排序完成。

#### ⚪实现 ####

`代码实现`：

public class heapSortTest {
        
    	//main函数、测试用
    	public static void main(String[] args) {
        
    		int[] arr = new int[]{
        1,5,88,9,-88,-99,-685,78,4,3,3,7,1,-8,7,256};
    		heapSort(arr);
    		for(int i = 0;i < arr.length;++i) {
        
    			System.out.print(arr[i] + " ");
    		}
    	}
    	
    	// 堆排序，排序函数
    	public static void heapSort(int[] arr) {
        
    		if(arr == null || arr.length < 2) return;
    		
    		for(int i = arr.length - 1; i >= 0; --i) {
        
    			heapify(arr, i, arr.length - 1);
    		}
    		
    		int heapSize = arr.length;
    		swap(arr, 0, --heapSize);
    		
    		while(heapSize > 0) {
        
    			heapify(arr, 0, heapSize);
    			swap(arr, 0, --heapSize);
    		}
    	}
    	
    	//heapify，建堆函数
    	public static void heapify(int[] arr, int index, int heapSize) {
        
    		//获取左孩子下标
    		int left = 2 * index + 1;
    		//left < heapSize : 当前节点存在左孩子
    		while(left < heapSize) {
        
    			// 获取左孩子、右孩子中最大值
    			int largest = left + 1 < heapSize && arr[left] < arr[left + 1] ? left + 1 : left;
    			// 较大孩子元素与父节点元素比较，更新较大值下标
    			largest = arr[index] < arr[largest] ? largest : index;
    			// 父节点最大，无法下移，直接停止
    			if(index == largest) break;
    			// 父节点小于较大孩子，下移
    			swap(arr, index, largest);
    			// 维护父节点和左孩子
    			index = largest;
    			left = 2 * index + 1;
    		}
    	}
    	
    	//交换函数
    	public static void swap(int[] arr, int a, int b) {
        
    		int temp = arr[a];
    		arr[a] = arr[b];
    		arr[b] = temp;
    	}
    	
    }

#### ⚪复杂度 ####

`复杂度分析`：

*  **时间复杂度：** 建堆操作的时间复杂度为O(n)，排序操作的时间复杂度为O(n log n)。因此，堆排序的总体时间复杂度为O(n log n)。
 *  **空间复杂度：** 堆排序是一种原地排序算法，只需使用常数级别的额外空间，因此空间复杂度为O(1)。

--------------------

### ?912. 排序数组 ###

\[⚪点击跳转【LeetCode 912. 排序数组】\]([912. 排序数组 - 力扣（LeetCode）][912. _ - _LeetCode])

`题目`：

> 给你一个整数数组 `nums`，请你将该数组升序排列。
> 
> **示例 1：**
> 
>     输入：nums = [5,2,3,1]
>     输出：[1,2,3,5]
> 
> **示例 2：**
> 
>     输入：nums = [5,1,1,2,0,0]
>     输出：[0,0,1,1,2,5]
> 
> **提示：**
> 
>  *  `1 <= nums.length <= 5 * 104`
>  *  `-5 * 104 <= nums[i] <= 5 * 104`

`解法一：归并排序`：

//使用归并排序
    class Solution {
        
        public int[] sortArray(int[] nums) {
        
            int length = nums.length;
            mergeSort(nums,0,nums.length - 1);
            return nums;
        }
    
        public void mergeSort(int[] arr,int l,int r){
        
            //子数组长度为1，停止
            if(l == r) return;
            //取中点
            int mid = l + ((r - l) >> 1);
            //递归排序左子数组
            mergeSort(arr,l,mid);
            //递归排序右子数组
            mergeSort(arr,mid + 1,r);
            //合并两个排序好的数组
            merge(arr,l,mid,r);
        }
    
        public void merge(int[] arr,int l,int mid,int r){
        
            //help数组
            int[] help = new int[r - l + 1];
            //help数组下标
            int i = 0;
            //左子数组头p1
            int p1 = l;
            //右子数组头p2
            int p2 = mid + 1;
            //合并两个有序数组，存入help数组
            while(p1 <= mid && p2 <= r){
        
                help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
            }
            while(p1 <= mid){
        
                help[i++] = arr[p1++];
            }
            while(p2 <= r){
        
                help[i++] = arr[p2++];
            }
    
            //将help数组的元素赋值回目标数组
            for(int j = 0;j < help.length;++j){
        
                arr[l + j] = help[j];
            }
    
        }
    }

`解法二：快速排序`：

class Solution {
        
        //快排
        public int[] sortArray(int[] nums) {
        
            if(nums == null || nums.length < 2) return nums; //空或长度1，无需排序
    
            qSort(nums,0,nums.length - 1); //快排
    
            return nums;
        }
    
        public static void qSort(int[] arr,int l,int r){
        
            //数组头尾不冲突
            if(l < r){
        
                //利用random等概率随机获取基准 与尾部元素交换位置
                swap(arr,r,l + (int)(Math.random() * (r - l + 1)));
                //得到长度二的数组，两个元素分别代表大于基准元素与小于基准元素的边界
                int[] p = partition(arr,l,r);
                qSort(arr,l,p[0]);
                qSort(arr,p[1],r);
            }
        }
    
        //划分函数
        public static int[] partition(int[] arr,int l,int r){
        
            int less = l - 1; //小于基准的边界
            int more = r;     //大于基准的边界
            while(l < more){
        
                if(arr[l] < arr[r]){
        
                    swap(arr,++less,l++);
                }else if(arr[l] > arr[r]){
        
                    swap(arr,--more,l);
                }else{
        
                    ++l;
                }
            }
            swap(arr,more,r);
            return new int[]{
        less,more + 1};
        }
    
        //交换
        public static void swap(int[] arr,int a,int b){
        
            int tmp = arr[a];
            arr[a] = arr[b];
            arr[b] = tmp;
        }
    }

`解法三：堆排序`：

class Solution {
        
        public int[] sortArray(int[] nums) {
        
            heapSort(nums);
            return nums;
        }
    
        public static void heapSort(int[] arr){
        
            if(arr == null || arr.length < 2) return;
    
            for(int i = arr.length - 1; i >= 0; --i){
        
                heapify(arr, i, arr.length);
            }
    
            int heapSize = arr.length;
            swap(arr, 0, --heapSize);
    
            while(heapSize > 0){
        
                heapify(arr, 0, heapSize);
                swap(arr, 0, --heapSize);
            }
        }
    
        public static void heapify(int[] arr, int index, int heapSize){
        
            int left = 2 * index + 1;
            while(left < heapSize){
        
                int largest = left + 1 < heapSize && arr[left] < arr[left+1] ? left + 1 : left;
                largest = arr[index] < arr[largest] ? largest : index;
                if(largest == index) break;
                swap(arr, index, largest);
                index = largest;
                left = 2 * index + 1;
            }
        }
    
        public static void swap(int[] arr, int a, int b){
        
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }

--------------------

### ?315. 计算右侧小于当前元素的个数 ###

[⚪点击跳转：315. 计算右侧小于当前元素的个数][315.]

> 给你一个整数数组 `nums` ，按要求返回一个新数组 `counts` 。数组 `counts` 有该性质： `counts[i]` 的值是 `nums[i]` 右侧小于 `nums[i]` 的元素的数量。
> 
> **示例 1：**
> 
>     输入：nums = [5,2,6,1]
>     输出：[2,1,1,0] 
>     解释：
>     5 的右侧有 2 个更小的元素 (2 和 1)
>     2 的右侧仅有 1 个更小的元素 (1)
>     6 的右侧有 1 个更小的元素 (1)
>     1 的右侧有 0 个更小的元素
> 
> **示例 2：**
> 
>     输入：nums = [-1]
>     输出：[0]
> 
> **示例 3：**
> 
>     输入：nums = [-1,-1]
>     输出：[0,0]
> 
> **提示：**
> 
>  *  `1 <= nums.length <= 105`
>  *  `-104 <= nums[i] <= 104`

`利用归并排序性质，完成计数`：

// 利用归并排序的特性， 计算 nums[i] 右侧小于 nums[i] 的元素的数量。
    class Solution {
        
        static int[] counts; // 题目要求的counts数组
        static int[] index;  // 下标数组，记录nums元素的移动，即：元素移动，下标做同样操作。
    
        public List<Integer> countSmaller(int[] nums) {
        
            List<Integer> list = new ArrayList<>(); //创建集合，因为:函数返回值为List<Integer>
            if(nums == null) return list;           //数组为空，直接返回空集合
            if(nums.length == 1){
                           //数组长度=1
                list.add(0);      //右侧没有小于nums[i]的元素，所以nums[i]=0，添加到集合中
                return list;      //直接返回
            }
    
            //初始化counts和index
            int n = nums.length;
            this.counts = new int[n];
            this.index = new int[n];
    
            //为下标数组元素 附上 下标值
            for(int i = 0;i < n; ++i){
        
                index[i] = i;
            }
    
            //进行归并排序，在排序过程中完成计数
            mergeSort(nums, 0, n - 1);
    
            //将得到的符合规则的counts数组元素赋值给集合再返回，因为:函数返回值为List<Integer>
            for(int count : counts) list.add(count);
            return list;
        }
    
        //归并排序：
        public static void mergeSort(int[] arr, int l, int r){
        
            if(l == r) return;
            int mid = l + ((r - l) >> 1);
            mergeSort(arr, l, mid);
            mergeSort(arr, mid + 1, r);
            merge(arr, l, mid, r);
        }
    
        //合并有序子序列
        public static void merge(int[] arr, int l, int mid, int r){
        
            int[] help = new int[r - l + 1];   //元素的help数组，用于合并有序子序列
            int[] helpI = new int[r - l + 1];  //下标的help数组，用于记录合并有序子序列时元素的移动
            int i = 0;        //下标
            int p1 = l;       //左子序列头元素下标
            int p2 = mid + 1; //右子序列头元素下标
    
            while(p1 <= mid && p2 <= r){
        
                //按照逆序，进行归并排序的合并
                if(arr[p1] > arr[p2]){
        
                    //因为逆序，所以p2到R范围内的元素是降序的，即：
                    //当前情况下nums[i] 右侧小于 nums[i] 的元素的数量 = r - p2 + 1
                    //在排序过程中，累加所有情况下的r - p2 + 1，就能的到总数。
                    counts[index[p1]] += r - p2 + 1;
                    help[i] = arr[p1];
                    helpI[i++] = index[p1++];
                }else{
        
                    help[i] = arr[p2];
                    helpI[i++] = index[p2++];
                }
            }
            while(p1 <= mid){
        
                help[i] = arr[p1];
                helpI[i++] = index[p1++];
            }
            while(p2 <= r){
        
                help[i] = arr[p2];
                helpI[i++] = index[p2++];
            }
    
            //将help数组中的元素 赋值回原数组中，完成合并。
            for(i = 0;i < help.length; ++i){
        
                arr[i + l] = help[i];
                index[i + l] = helpI[i];
            }
        }
    }

--------------------

### ?561. 数组拆分 ###

[⚪点击跳转：561. 数组拆分][561.]

> 给定长度为 `2n` 的整数数组 `nums` ，你的任务是将这些数分成 `n` 对, 例如 `(a1, b1), (a2, b2), ..., (an, bn)` ，使得从 `1` 到 `n` 的 `min(ai, bi)` 总和最大。
> 
> 返回该 **最大总和** 。
> 
> **示例 1：**
> 
>     输入：nums = [1,4,3,2]
>     输出：4
>     解释：所有可能的分法（忽略元素顺序）为：
>     1. (1, 4), (2, 3) -> min(1, 4) + min(2, 3) = 1 + 2 = 3
>     2. (1, 3), (2, 4) -> min(1, 3) + min(2, 4) = 1 + 2 = 3
>     3. (1, 2), (3, 4) -> min(1, 2) + min(3, 4) = 1 + 3 = 4
>     所以最大总和为 4
> 
> **示例 2：**
> 
>     输入：nums = [6,2,6,5,1,2]
>     输出：9
>     解释：最优的分法为 (2, 1), (2, 5), (6, 6). min(2, 1) + min(2, 5) + min(6, 6) = 1 + 2 + 6 = 9
> 
> **提示：**
> 
>  *  `1 <= n <= 104`
>  *  `nums.length == 2 * n`
>  *  `-104 <= nums[i] <= 104`

`题解（归并排序）`：

//归并排序
    class Solution {
        
        public int arrayPairSum(int[] nums) {
        
            //排序数组（这里使用归并排序，还推荐使用堆排序、快速排序）
            mergeSort(nums, 0, nums.length - 1);
    
            //根据分析，有序的数组分成n对，就能满足题意
            int ans = 0;
            for(int i = 0;i < nums.length; i += 2){
        
                //将每队的min(ai, bi)累加起来，得到总和
                ans += nums[i];
            }
    
            //返回结果
            return ans;
        }
    
        public static void mergeSort(int[] arr, int l, int r){
        
            if(l == r) return;
            int mid = l + ((r - l) >> 1);
            mergeSort(arr, l, mid);
            mergeSort(arr, mid + 1, r);
            merge(arr, l, mid, r);
        }
    
        public static void merge(int[] arr, int l,int mid, int r){
        
            int[] help = new int[r - l + 1];
            int p1 = l;
            int p2 = mid + 1;
            int i = 0;
    
            while(p1 <= mid && p2 <= r){
        
                help[i++] = arr[p1] <= arr[p2] ? arr[p1++] : arr[p2++];
            }
            while(p1 <= mid){
        
                help[i++] = arr[p1++];
            }
            while(p2 <= r){
        
                help[i++] = arr[p2++];
            }
    
            for(i = 0;i < help.length; ++i){
        
                arr[i + l] = help[i];
            }
        }
    }

`题解（堆排序）`：

class Solution {
        
        public int arrayPairSum(int[] nums) {
        
            int n = nums.length;
            heapSort(nums, n); //堆排序
    
            int ans = 0;
            for(int i = 0;i < n; i += 2){
        
                ans += nums[i];
            }
    
            return ans;
        }
    
        public static void heapSort(int[] arr, int n){
        
            if(arr == null || n < 2) return;
    
            for(int i = n - 1; i >= 0; --i){
        
                heapify(arr, i, n);
            }
    
            int heapSize = n;
            swap(arr, 0, --heapSize);
    
            while(heapSize > 0){
        
                heapify(arr, 0, heapSize);
                swap(arr, 0, --heapSize);
            }
        }
    
        public static void heapify(int[] arr, int index, int heapSize){
        
            int left = 2 * index + 1;
            while(left < heapSize){
        
                int largest = left + 1 < heapSize && arr[left + 1] > arr[left] ? left + 1 : left;
                largest = arr[index] > arr[largest] ? index : largest;
                if(index == largest) break; //无法下移，停止
                swap(arr, index, largest);  //可以下移，交换
                index = largest;            //交换完后完成下移
                left = 2 * index + 1;       //维护左孩子
            }
        }
    
        public static void swap(int[] arr, int a, int b){
        
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }

`题解（快速排序）【速度最快】`：

class Solution {
        
        public int arrayPairSum(int[] nums) {
        
            int n = nums.length;
            quickSort(nums, 0, n - 1);
    
            int ans = 0;
            for(int i = 0;i < n; i += 2){
        
                ans += nums[i];
            }
    
            return ans;
        }
    
        public static void quickSort(int[] arr, int l, int r){
        
            if(l < r){
        
                swap(arr, r, l + (int)(Math.random() * (r - l + 1)));
                int[] p = partition(arr, l, r);
                quickSort(arr, l, p[0]);
                quickSort(arr,p[1], r);
            }
        }
    
        public static int[] partition(int[] arr, int l, int r){
        
            int less = l - 1;
            int more = r;
            while(l < more){
        
                if(arr[l] < arr[r]){
        
                    swap(arr, ++less, l++);
                }else if(arr[l] > arr[r]){
        
                    swap(arr, --more, l);
                }else{
        
                    ++l;
                }
            }
            swap(arr, more, r);
            return new int[]{
        less, more + 1};
        }
    
        public static void swap(int[] arr, int a, int b){
        
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    
    }

--------------------

### ?1122. 数组的相对排序（计数排序） ###

[⚪点击跳转：1122. 数组的相对排序][1122.]

> 给你两个数组，`arr1` 和 `arr2`，`arr2` 中的元素各不相同，`arr2` 中的每个元素都出现在 `arr1` 中。
> 
> 对 `arr1` 中的元素进行排序，使 `arr1` 中项的相对顺序和 `arr2` 中的相对顺序相同。未在 `arr2` 中出现过的元素需要按照升序放在 `arr1` 的末尾。
> 
> **示例 1：**
> 
>     输入：arr1 = [2,3,1,3,2,4,6,7,9,2,19], arr2 = [2,1,4,3,9,6]
>     输出：[2,2,2,1,4,3,3,9,6,7,19]
> 
> **示例 2:**
> 
>     输入：arr1 = [28,6,22,8,44,17], arr2 = [22,28,8,6]
>     输出：[22,28,8,6,17,44]
> 
> **提示：**
> 
>  *  `1 <= arr1.length, arr2.length <= 1000`
>  *  `0 <= arr1[i], arr2[i] <= 1000`
>  *  `arr2` 中的元素 `arr2[i]` **各不相同**
>  *  `arr2` 中的每个元素 `arr2[i]` 都出现在 `arr1` 中

`题解（计数排序）`：

计数排序是一种非比较性的整数排序算法，适用于待排序元素的范围较小的情况。该算法的基本思想是统计每个元素的出现次数，然后根据这些统计信息将元素放回正确的位置。

class Solution {
        
        //计数排序
        public int[] relativeSortArray(int[] arr1, int[] arr2) {
        
            //题目给定元素大小不超过1000，就可以设置一个1001长度的数组来进行计数排序
            int[] arr = new int[1001];         //计数数组
            int[] ans = new int[arr1.length];  //排序数组
            int index = 0;                     //排序数组的下标
    
            //遍历arr1，遍历到元素，就使arr数组对应下标的值+1
            for(int num : arr1){
        
                arr[num] += 1;
            }
    
            //遍历arr2数组，先将与arr2相对顺序元素放入排序数组
            for(int num : arr2){
        
                for(int i = 0;i < arr[num]; ++i){
        
                    ans[index++] = num;
                }
                arr[num] = 0; //维护计数数组
            }
    
            //遍历计数数组，将剩下的元素排序好并放入排序数组
            for(int k = 0;k < 1001; ++k){
        
                for(int i = 0;i < arr[k]; ++i){
        
                    ans[index++] = k;
                }
            }
            
            return ans;
        }
    }

--------------------

### ?268. 丢失的数字（计数排序） ###

[⚪点击跳转：268. 丢失的数字][268.]

> 给定一个包含 `[0, n]` 中 `n` 个数的数组 `nums` ，找出 `[0, n]` 这个范围内没有出现在数组中的那个数。
> 
> **示例 1：**
> 
>     输入：nums = [3,0,1]
>     输出：2
>     解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。
> 
> **示例 2：**
> 
>     输入：nums = [0,1]
>     输出：2
>     解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。
> 
> **示例 3：**
> 
>     输入：nums = [9,6,4,2,3,5,7,0,1]
>     输出：8
>     解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。
> 
> **示例 4：**
> 
>     输入：nums = [0]
>     输出：1
>     解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。
> 
> **提示：**
> 
>  *  `n == nums.length`
>  *  `1 <= n <= 104`
>  *  `0 <= nums[i] <= n`
>  *  `nums` 中的所有数字都 **独一无二**

`题解（计数排序）`

class Solution {
        
        public int missingNumber(int[] nums) {
        
            int ans = -1;               //没有出现在数组中的那个数。
            int n = nums.length;        //题目提到的n
            int[] arr = new int[n + 1]; //计数数组，用于记录元素出现的次数
            for(int num : nums){
                //使用计数数组，记录并排序nums数组元素
                arr[num] += 1;
            }
            for(int i = 0;i <= n; ++i){
         //遍历计数数组，值为0表示未出现
                if(arr[i] == 0){
        
                    ans = i;
                    break;
                }
            }
            return ans;
        }
    }

--------------------

### ?215. 数组中的第K个最大元素 ###

[⚪点击跳转：215. 数组中的第K个最大元素][215. _K]

> 给定整数数组 `nums` 和整数 `k`，请返回数组中第 `**k**` 个最大的元素。
> 
> 请注意，你需要找的是数组排序后的第 `k` 个最大的元素，而不是第 `k` 个不同的元素。
> 
> 你必须设计并实现时间复杂度为 `O(n)` 的算法解决此问题。
> 
> **示例 1:**
> 
>     输入: [3,2,1,5,6,4], k = 2
>     输出: 5
> 
> **示例 2:**
> 
>     输入: [3,2,3,1,2,4,5,5,6], k = 4
>     输出: 4
> 
> **提示：**
> 
>  *  `1 <= k <= nums.length <= 105`
>  *  `-104 <= nums[i] <= 104`

`题解（快速排序）`：

class Solution {
        
        public int findKthLargest(int[] nums, int k) {
        
            quickSort(nums, 0, nums.length - 1);
    
            int ans = Integer.MIN_VALUE;
            for(int i = 0;i <= nums.length - k; ++i){
        
                ans = nums[i];
            }
    
            return ans;
        }
    
        public static void quickSort(int[] arr, int l, int r){
        
            if(l < r){
        
                swap(arr, r, l + (int)(Math.random() * (r - l)));
                int[] p = partition(arr, l, r);
                quickSort(arr, l, p[0]);
                quickSort(arr, p[1], r);
            }
        }
    
        public static int[] partition(int[] arr, int l, int r){
        
            int less = l - 1;
            int more = r;
            while(l < more){
        
                if(arr[l] < arr[r]){
        
                    swap(arr, ++less, l++);
                }else if(arr[l] > arr[r]){
        
                    swap(arr, --more, l);
                }else{
        
                    ++l;
                }
            }
            swap(arr, more, r);
            return new int[]{
        less, more + 1};
        }
    
        public static void swap(int[] arr, int a, int b){
        
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }

--------------------

### ?347. 前 K 个高频元素 ###

[⚪点击跳转：347. 前 K 个高频元素][347. _ K]

> 给你一个整数数组 `nums` 和一个整数 `k` ，请你返回其中出现频率前 `k` 高的元素。你可以按 **任意顺序** 返回答案。
> 
> **示例 1:**
> 
>     输入: nums = [1,1,1,2,2,3], k = 2
>     输出: [1,2]
> 
> **示例 2:**
> 
>     输入: nums = [1], k = 1
>     输出: [1]
> 
> **提示：**
> 
>  *  `1 <= nums.length <= 105`
>  *  `k` 的取值范围是 `[1, 数组中不相同的元素的个数]`
>  *  题目数据保证答案唯一，换句话说，数组中前 `k` 个高频元素的集合是唯一的

`题解（优先队列[堆排序] + hash表）`：

class Solution {
        
        public int[] topKFrequent(int[] nums, int k) {
        
            PriorityQueue<int[]> pq = new PriorityQueue<>((a,b) -> (b[1] - a[1]));
            Map<Integer, Integer> map = new HashMap<>();
            int[] ans = new int[k];
    
            for(int num : nums){
        
                if(!map.containsKey(num)){
        
                    map.put(num,1);
                }else{
        
                    map.put(num,map.get(num).intValue() + 1);
                }
            }
    
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
        
                pq.offer(new int[]{
        entry.getKey(), entry.getValue()});
            }
    
            for(int i = 0;i < k; ++i){
        
                ans[i] = pq.poll()[0];
            }
    
            return ans;
        }
    }

--------------------

### ?LCR 159. 库存管理 III(计数排序) ###

[⚪点击跳转：LCR 159. 库存管理 III][LCR 159. _ III]

> 仓库管理员以数组 `stock` 形式记录商品库存表，其中 `stock[i]` 表示对应商品库存余量。请返回库存余量最少的 `cnt` 个商品余量，返回 **顺序不限**。
> 
> **示例 1：**
> 
>     输入：stock = [2,5,7,4], cnt = 1
>     输出：[2]
> 
> **示例 2：**
> 
>     输入：stock = [0,2,3,6], cnt = 2
>     输出：[0,2] 或 [2,0]
> 
> **提示：**
> 
>  *  `0 <= cnt <= stock.length <= 10000 0 <= stock[i] <= 10000`

`题解（计数排序）`：

class Solution {
        
        public int[] inventoryManagement(int[] stock, int cnt) {
        
            int[] help = new int[10001];
    
            for(int num : stock){
        
                help[num] += 1;
            }
    
            int[] ans = new int[cnt];
            int index = 0;
            a:for(int i = 0;i < 10001; ++i){
        
                for(int j = 0;j < help[i]; ++j){
        
                    if(index < cnt){
        
                        ans[index++] = i;
                    }else{
        
                        break a;
                    }
                }
            }
    
            return ans;
        }
    }

`题解（快速排序）`：

class Solution {
        
        public int[] getLeastNumbers(int[] arr, int k) {
        
            int[] ans = new int[k];
            qSort(arr,0,arr.length - 1);
            for(int i = 0;i < k;++i){
        
                ans[i] = arr[i];
            }
            return ans;
        }
    
        public static void qSort(int[] arr,int l,int r){
        
            if(l < r){
        
                swap(arr,r,l + (int)(Math.random() * (r - l + 1)));
                int[] p = partition(arr,l,r);
                qSort(arr,l,p[0]-1);
                qSort(arr,p[1]+1,r);
            }
        }
    
        public static int[] partition(int[] arr,int l,int r){
        
            int less = l - 1;
            int more = r;
            while(l < more){
        
                if(arr[l] < arr[r]){
        
                    swap(arr,++less,l++);
                }else if(arr[l] > arr[r]){
        
                    swap(arr,l,--more);
                }else{
        
                    ++l;
                }
            }
            swap(arr,r,more);
            return new int[]{
        less+1,more};
        }
    
        public static void swap(int[] arr,int a,int b){
        
            int temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }

--------------------

### ?LCR 170. 交易逆序对的总数 ###

[⚪点击跳转：LCR 170. 交易逆序对的总数][LCR 170.]

> 在股票交易中，如果前一天的股价高于后一天的股价，则可以认为存在一个「交易逆序对」。请设计一个程序，输入一段时间内的股票交易记录 `record`，返回其中存在的「交易逆序对」总数。
> 
> **示例 1:**
> 
>     输入：record = [9, 7, 5, 4, 6]
>     输出：8
>     解释：交易中的逆序对为 (9, 7), (9, 5), (9, 4), (9, 6), (7, 5), (7, 4), (7, 6), (5, 4)。
> 
> **限制：**
> 
>     0 <= record.length <= 50000

`归并排序 题解`：

class Solution {
        
        int ans = 0;
        public int reversePairs(int[] record) {
        
            if(record == null || record.length < 2) return ans;
            mergeSort(record, 0, record.length - 1);
            return ans;
        }
    
        public void mergeSort(int[] arr, int l, int r){
        
            if(l == r) return;
            int mid = l + ((r - l) >> 1);
            mergeSort(arr, l, mid);
            mergeSort(arr, mid + 1, r);
            merge(arr, l, mid, r);
        }
    
        public void merge(int[] arr, int l, int mid, int r){
        
            int[] help = new int[r - l + 1];
            int p1 = l;
            int p2 = mid + 1;
            int i = 0;
            while(p1 <= mid && p2 <= r){
        
                if(arr[p1] > arr[p2]){
        
                    ans += r - p2 + 1;
                    help[i++] = arr[p1++];
                }else{
        
                    help[i++] = arr[p2++];
                }
            }
            while(p1 <= mid){
        
                help[i++] = arr[p1++];
            }
            while(p2 <= r){
        
                help[i++] = arr[p2++];
            }
    
            for(i = 0;i < help.length; ++i){
        
                arr[i + l] = help[i];
            }
        }
    }

--------------------

[![在这里插入图片描述][20a7f1b58dfb4660b75d7f021c157d57.png_pic_center]][20a7f1b58dfb4660b75d7f021c157d57.png_pic_center 1]

[8d8e0d8a542946af858489a536162608.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/1dad0b955ece4cc9865c74908b576fdd.gif
[.29.]: https://blog.csdn.net/ebb29bbe?spm=1018.2226.3001.5343
[Link 1]: https://bbs.csdn.net/forums/185241f773fb401b8ca7994dc3d02333?joinKey=cyru4ex9o7wq-mz6v1koj5x-1-add3ae8dc3827dbbd4360c79af92bbbe
[be111d444fa34ccf8a39c17607ee05b7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/e57bb734e0fc4529bb49c35ba9f6ffc0.png
[912. _ - _LeetCode]: https://leetcode.cn/problems/sort-an-array/description/
[315.]: https://leetcode.cn/problems/count-of-smaller-numbers-after-self/
[561.]: https://leetcode.cn/problems/array-partition/
[1122.]: https://leetcode.cn/problems/relative-sort-array/
[268.]: https://leetcode.cn/problems/missing-number/
[215. _K]: https://leetcode.cn/problems/kth-largest-element-in-an-array/
[347. _ K]: https://leetcode.cn/problems/top-k-frequent-elements/
[LCR 159. _ III]: https://leetcode.cn/problems/zui-xiao-de-kge-shu-lcof/
[LCR 170.]: https://leetcode.cn/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
[20a7f1b58dfb4660b75d7f021c157d57.png_pic_center]: https://img-blog.csdnimg.cn/20a7f1b58dfb4660b75d7f021c157d57.png#pic_center
[20a7f1b58dfb4660b75d7f021c157d57.png_pic_center 1]: https://blog.csdn.net/ebb29bbe?type=blog