文章目录
一、常用的排序算法
1.1、快速排序
快速排序是一种不稳定的排序算法。首先设置三个指针，first 指向区间左端，last 指向区间右端，key 为当前的分界值。从待排序的数据元素中选取一个（通常为第一个）作为基准值元素 key，设置双指针 first 指向区间左端，last 指向区间右端。
- 首先用
num[last]与key进行比较，如果num[last] >= key，则移动右指针last--；直到当num[last] < key时，则将num[first] = num[last]。 - 查找上述条件并完成交换后，转向左边部分，用
num[first]与key进行比较，如果num[first] <= key, 则first++，然后继续进行比较，直至num[first] > key，则将num[last] = num[first]。 - 重复上述一二步骤。
class Solution {
public void quick_sort(int[] nums, int l, int r) {
if (l + 1 >= r) {
return;
}
int first = l, last = r - 1, key = nums[first];
while (first < last) {
while (first < last && nums[last] >= key) {
last--;
}
nums[first] = nums[last];
while (first < last && nums[first] <= key) {
first++;
}
nums[last] = nums[first];
}
nums[first] = key;
quick_sort(nums, l, first);
quick_sort(nums, first + 1, r);
}
}
复杂度分析
- 时间复杂度：平均时间复杂度为 O(nlogn)，其中 n 是数组 nums 的长度。在最坏的情况下，待排序的数组时正序或倒序，比较次数为
n + (n-1) + (n-2) + (n-3) + … +1 = n*(n + 1)/2，因此时间复杂度为O(n2)。 - 空间复杂度：O(logn)。快速排序使用的空间是O(1)的，也就是常数级，而真正消耗空间的就是递归调用。在最坏的情况下，空间复杂度是O(n)。
1.2、归并排序
归并排序是一种稳定的排序算法。当我们要排序这样一个数组的时候，首先将这个数组从中间分成两个子数组，一直递归地把子数组划分成更小的子数组，直到子数组里面只有一个元素。接下来依次按照递归的返回顺序，不断地合并排好序的子数组，直到最后把整个数组的顺序排好。
class Solution {
public void mergeSort(int[] nums, int l, int r, int[] temp) {
if (l + 1 >= r) {
return;
}
int m = l + (r - l) / 2;
mergeSort(nums, l, m, temp);
mergeSort(nums, m, r, temp);
int p = l, q = m, i = l;
while (p < m || q < r) {
if (q >= r || (p < m && nums[p] <= nums[q])) {
temp[i++] = nums[p++];
} else {
temp[i++] = nums[q++];
}
}
System.arraycopy(temp, l, nums, l, r - l);
}
}
复杂度分析
- 时间复杂度：O(nlogn)，其中 n 是数组 nums 的长度。与快速排序不同，归并排序任何情况下都是 O(nlogn)。
- 空间复杂度：O(logn)。在最坏的情况下，空间复杂度是O(n)。
1.3、插入排序
插入排序是一种稳定的排序算法。顾名思义，就是把一个新的元素插入已排好序的数组形成一个新的已排好序的数组。从第一个元素开始，取下一个元素进行比较实现排序，形成新的数组， 再取第三个元素与该数组比较， 比较时从该数组的最后一位开始比较， 若新元素比与其比较的元素小，则将该比较的元素后移一位， 直到新元素比该数组左边找到其应该插入的位置。
class Solution {
public void insertionSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--) {
int temp = nums[j - 1];
nums[j - 1] = nums[j];
nums[j] = temp;
}
}
}
}
复杂度分析
- 时间复杂度：平均时间复杂度为 O(n2)，其中 n 是数组 nums 的长度。在最好的情况下，即排序之前的序列本身就是有序的，那么每两个元素仅需对比一次，时间复杂度是O(n)。
- 空间复杂度：O(1)。
1.4、冒泡排序
冒泡排序是一种稳定排序算法。其实现原理是重复扫描待排序序列，并比较每一对相邻的元素，当该对元素顺序不正确时进行交换。一直重复这个过程，直到没有任何两个相邻元素可以交换，就表明完成了排序。
class Solution {
public void bubbleSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
for (int j = 0; j < nums.length - i - 1; j++) {
if (nums[j] > nums[j + 1]) {
int temp = nums[j];
nums[j] = nums[j + 1];
nums[j + 1] = temp;
}
}
}
}
}
复杂度分析
- 时间复杂度：O(n2)，其中 n 是数组 nums 的长度。冒泡排序一共要进行
(n-1)次循环，每一次循环都要进行当前n-1次比较，一共需比较(n-1) + (n-2) + (n-3) + … + 1 = n*(n - 1)/2次，所以时间复杂度为O(n2)。 - 空间复杂度：O(1)。
1.5、选择排序
选择排序是一种不稳定排序算法。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾，重复第二步，直到所有元素均排序完毕。
class Solution {
public void selectionSort(int[] nums) {
for (int i = 0; i < nums.length; i++) {
int index = i;
for (int j = i; j < nums.length; j++) {
if (nums[index] > nums[j]) {
index = j;
}
}
int temp = nums[i];
nums[i] = nums[index];
nums[index] = temp;
}
}
}
复杂度分析
- 时间复杂度： O(n2)，其中 n 是数组 nums 的长度，这里也是使用了双层循环，时间复杂度和冒泡排序的一样。
- 空间复杂度：O(1)。
二、快速选择
2.1、数组中的第K个最大元素
2.1.1、题目描述
215. 数组中的第K个最大元素
给定整数数组nums和整数k，请返回数组中第k个最大的元素。
请注意，你需要找的是数组排序后的第k个最大的元素，而不是第k个不同的元素。
2.1.2、输入输出示例
示例1：
输入： [3, 2, 1, 5, 6, 4] 和 k = 2
输出： 5
示例2：
输入： [3, 2, 3, 1, 2, 4, 5, 5, 6] 和 k = 4
输出： 4
2.1.3、题解
快速选择一般用于求解 k-th Element 问题，可以在 O(n) 时间复杂度， O(1) 空间复杂度完成求解工作。快速选择的实现和快速排序相似，不过只需要找到第 k 大的位置即可，不需要对其左右再进行排序。
class Solution {
public int findKthLargest(int[] nums, int k) {
int l = 0, r = nums.length - 1, target = nums.length - k;
while (l < r) {
int index = quickSelection(nums, l, r);
if (index < target) {
l = index + 1;
} else if (index > target) {
r = index - 1;
} else {
return nums[index];
}
}
return nums[l];
}
private int quickSelection(int[] nums, int l, int r) {
int i = l + 1, j = r;
while (true) {
while (i < r && nums[i] <= nums[l]) {
i++;
}
while (j > l && nums[j] >= nums[l]) {
j--;
}
if (i >= j) {
break;
}
swap(nums, i, j);
}
swap(nums, l, j);
return j;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
复杂度分析
- 时间复杂度： O(n)，其中 n 是数组 nums 的长度。
- 空间复杂度：O(1)。
三、桶排序
3.1、前 K 个高频元素
3.1.1、题目描述
347. 前 K 个高频元素
给你一个整数数组nums和一个整数k，请你返回其中出现频率前k高的元素。你可以按 任意顺序 返回答案。
3.1.2、输入输出示例
示例1：
输入： nums = [1, 1, 1, 2, 2, 3], k = 2
输出： [1, 2]
示例2：
输入： nums = [1], k = 1
输出： [1]
3.1.3、题解
顾名思义， 桶排序的意思是为每个值设立一个桶，桶内记录这个值出现的次数（或其它属性），然后对桶进行排序。针对示例1来说，我们先通过桶排序得到三个桶 [1, 2, 3]，它们的值分别为 [3, 2, 1]，表示每个数字出现的次数。
紧接着，我们对桶的频次进行排序，前 k 大个桶即是前 k 个频繁的数。这里维护 k 个新桶，然后遍历旧桶，如果新桶数量个数小于 k，就可以直接插入新桶中；如果新桶的元素个数等于 k，则检查堆顶与当前出现次数的大小，如果堆顶更大，说明至少有 k 个数字的出现次数比当前值大，故舍弃当前值；否则，就弹出堆顶，并将当前值插入堆中。
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}
PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
if (queue.size() == k) {
if (queue.peek().getValue() < entry.getValue()) {
queue.poll();
queue.offer(entry);
}
} else {
queue.offer(entry);
}
}
int[] ans = new int[k];
for (int i = k - 1; i >= 0; i--) {
ans[i] = queue.poll().getKey();
}
return ans;
}
}
复杂度分析
- 时间复杂度： O(nlogk)，其中 n 为数组的长度。我们首先遍历原数组，并使用哈希表记录出现次数，每个元素需要 O(1) 的时间，共需 O(n) 的时间。随后我们遍历「出现次数数组」，由于堆的大小至多为 k，因此每次堆操作需要 O(logk) 的时间，共需 O(nlogk) 的时间。二者之和为 O(nlogk)。
- 空间复杂度：O(n)，哈希表的大小为 O(n)，而堆的大小为 O(k)，共计为 O(n)。
四、练习
4.1、基础难度
4.1.1、根据字符出现频率排序
4.1.1.1、题目描述
451. 根据字符出现频率排序
给定一个字符串s，根据字符出现的 频率 对其进行 降序排序 。一个字符出现的 频率 是它出现在字符串中的次数。
返回 已排序的字符串 。如果有多个答案，返回其中任何一个。
4.1.1.2、输入输出示例
示例2：
输入： s = “tree”
输出： “eert”
解释： 'e’出现两次，'r’和’t’都只出现一次。
因此’e’必须出现在’r’和’t’之前。此外，"eetr"也是一个有效的答案。
示例2：
输入： s = “cccaaa”
输出： “cccaaa”
解释： 'c’和’a’都出现三次。此外，"aaaccc"也是有效的答案。
注意"cacaca"是不正确的，因为相同的字母必须放在一起。
示例3：
输入： s = “Aabb”
输出： “bbAa”
解释： 此外，"bbaA"也是一个有效的答案，但"Aabb"是不正确的。
注意’A’和’a’被认为是两种不同的字符。
4.1.1.3、题解
可以使用哈希表记录每个字符出现的频率，将字符去重后存入列表，再将列表中的字符按照频率降序排序。生成排序后的字符串时，遍历列表中的每个字符，则遍历顺序为字符按照频率递减的顺序。对于每个字符，将该字符按照出现频率拼接到排序后的字符串。
class Solution {
public String frequencySort(String s) {
HashMap<Character, Integer> map = new HashMap<>();
for (int i = 0; i < s.length(); i++) {
map.put(s.charAt(i), map.getOrDefault(s.charAt(i), 0) + 1);
}
List<Character> list = new ArrayList<>(map.keySet());
list.sort((a, b) -> map.get(b) - map.get(a));
StringBuilder builder = new StringBuilder();
for(Character character : list) {
Integer count = map.get(character);
while (count-- > 0) {
builder.append(character);
}
}
return builder.toString();
}
}
复杂度分析
- 时间复杂度： O(n+klogk)，其中 n 是字符串 s 的长度，k 是字符串 s 包含的不同字符的个数，这道题中 s 只包含大写字母、小写字母和数字，因此 k=26+26+10=62。遍历字符串统计每个字符出现的频率需要 O(n) 的时间。
将字符按照出现频率排序需要 O(klogk) 的时间。
生成排序后的字符串，需要遍历 k 个不同字符，需要 O(k) 的时间，拼接字符串需要 O(n) 的时间。
因此总时间复杂度是 O(n+klogk+k+n)=O(n+klogk)。 - 空间复杂度：O(n+k)，其中 n 是字符串 s 的长度，k 是字符串 s 包含的不同字符的个数。空间复杂度主要取决于哈希表、列表和生成的排序后的字符串。
4.2、进阶难度
4.2.1、颜色分类
4.2.1.1、题目描述
75. 颜色分类
给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。
我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。
必须在不使用库的sort函数的情况下解决这个问题。
4.2.1.2、输入输出示例
示例1：
输入：nums = [2, 0, 2, 1, 1, 0]
输出：[0, 0, 1, 1, 2, 2]
示例2：
输入：nums = [2, 0, 1]
输出：[0, 1, 2]
4.2.1.3、题解
可以用两个指针分别用来交换 p0 和 p1，即从左向右遍历整个数组，如果是 0 的话，那么将其与 nums[p0] 进行交换并将 p0 向后移动一个位置，若该位置与 p1 重复，也将 p1 向后移动一个位置；再接着比较是否为 1，是的话那么将其与 nums[p1] 进行交换，并将 p1 向后移动一个位置。
class Solution {
public void sortColors(int[] nums) {
int p0 = 0, p1 = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == 0) {
swap(nums, i, p0);
if (p0 == p1) {
p1++;
}
p0++;
}
if (nums[i] == 1) {
swap(nums, i, p1++);
}
}
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
复杂度分析
- 时间复杂度： O(n)，其中 n 是数组 nums 的长度。
- 空间复杂度：O(1)。