因着整理算法知识的契机，产生了把排序算法实践了一下的想法。原本是打算按照力扣曾经发布的题单来刷，但是看完题之后有点失望😬，就自己小小的整理了这篇针对于排序算法实践。后续有需要应该还会完善，欢迎在评论区共同讨论～
十大内部排序算法
| 排序算法 | 适用的数据结构 | 最好时间复杂度 | 最坏时间复杂度 | 平均时间复杂度 | 空间复杂度 | 排序方式 | 稳定性 |
|---|---|---|---|---|---|---|---|
| 冒泡排序(Bubble sort) | 数组 | O(n) | O(n^2) | O(n^2) | O(1) | In-place | 稳定 |
| 插入排序(Insertion sort) | 数组、链表 | O(n) | O(n^2) | O(n^2) | O(1) | In-place | 稳定 |
| 选择排序(Selection sort) | 数组、链表 | O(n^2) | O(n^2) | O(n^2) | O(1) | In-place | 不稳定 |
| 快速排序(Quick sort) | 数组 | O(n log n) | O(n log n) | O(n log n) | O(n log n) | In-place | 不稳定 |
| 堆排序(Heap sort) | 数组 | O(n log n) | O(n log n) | O(n log n) | O(1) | In-place | 不稳定 |
| 希尔排序(Shell sort) | 数组 | O(n log n) | O(n^2) | O(n log n) | O(1) | In-place | 不稳定 |
| 归并排序(Merge sort) | 数组、链表 | O(n log n) | O(n log n) | O(n log n) | O(n) | Out-place | 稳定 |
| 计数排序(Counting sort) | 数组、链表 | O(n+k) | O(n+k) | O(n+k) | O(k) | Out-place | 稳定 |
| 桶排序(Bucket sort) | 数组、链表 | O(n+k) | O(n+k) | O(n^2) | O(n+k) | Out-place | 稳定 |
| 基数排序(Radix sort) | 数组、链表 | O(n×k) | O(n×k) | O(n×k) | O(n+k) | Out-place | 稳定 |
*注：
①n为数组长度或链表节点数，k为等待排序元素的最大位数
②归并排序中内部使用到插入排序
③基数排序中内部使用到计数排序或者桶排序
④基数排序需要经过处理才可以对负数元素排序
冒泡排序
🟢283. 移动零
给定一个数组
nums，编写一个函数将所有0移动到数组的末尾，同时保持非零元素的相对顺序。请注意 ，必须在不复制数组的情况下原地对数组进行操作。
示例 1:
输入: nums = [0,1,0,3,12] 输出: [1,3,12,0,0]示例 2:
输入: nums = [0] 输出: [0]提示:
1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1**进阶：**你能尽量减少完成的操作次数吗？
Related Topics
数组
双指针
class Solution {
public void moveZeroes(int[] nums) {
int len= nums.length;
for (int i = 0; i < len-1; i++) {
for (int j = 1; j < len-i; j++) {
if(nums[j-1]==0){
int temp=nums[j];
nums[j]=nums[j-1];
nums[j-1]=temp;
}
}
}
}
}-
time:O(n^2^)
-
space:O(1)
插入排序
🟡147. 对链表进行插入排序
给定单个链表的头
head，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。插入排序 算法的步骤:
- 插入排序是迭代的，每次只移动一个元素，直到所有元素可以形成一个有序的输出列表。
- 每次迭代中，插入排序只从输入数据中移除一个待排序的元素，找到它在序列中适当的位置，并将其插入。
- 重复直到所有输入数据插入完为止。
下面是插入排序算法的一个图形示例。部分排序的列表(黑色)最初只包含列表中的第一个元素。每次迭代时，从输入数据中删除一个元素(红色)，并就地插入已排序的列表中。
对链表进行插入排序。
示例 1：
输入: head = [4,2,1,3] 输出: [1,2,3,4]示例 2：
输入: head = [-1,5,3,4,0] 输出: [-1,0,3,4,5]提示：
- 列表中的节点数在
[1, 5000]范围内-5000 <= Node.val <= 5000Related Topics
链表
排序
class Solution {
public ListNode insertionSortList(ListNode head) {
ListNode dummy = new ListNode(0);
ListNode ptr = head;
while (ptr != null) {
ListNode slow = dummy;
ListNode fast = slow.next;
while (fast != null && fast.val <= ptr.val) {
slow = fast;
fast = fast.next;
}
ListNode next = ptr.next;
ptr.next = fast;
slow.next = ptr;
ptr = next;
}
return dummy.next;
}
}-
time:O(n^2^)
-
space:O(1)
选择排序
🟡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] <= 10000Related Topics
数组
分治
快速选择
排序
堆（优先队列）
class Solution {
public int[] inventoryManagement(int[] stock, int cnt) {
int len=stock.length;
for (int i = 0; i < len; i++) {
for (int j = i+1; j < len; j++) {
if(stock[j]<stock[i]){
int temp=stock[i];
stock[i]=stock[j];
stock[j]=temp;
}
}
}
int[]res=new int[cnt];
for (int i = 0; i < cnt; i++) {
res[i]=stock[i];
}
return res;
}
}-
time:O(n^2^)
-
space:O(cnt)
快速排序
🟡912. 排序数组
给你一个整数数组
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 * 104Related Topics
数组
分治
桶排序
计数排序
基数排序
排序
堆（优先队列）
归并排序
class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
quickSort(nums, 0, len - 1);
return nums;
}
void quickSort(int[] nums, int l, int r) {
if (l >= r) {
return;
}
int i = l;
int j = r;
int x = nums[i];
while (i < j) {
while (i < j && nums[j] > x) {
j--;
}
if (i < j) {
nums[i++] = nums[j];
}
while (i < j && nums[i] < x) {
i++;
}
if (i < j) {
nums[j--] = nums[i];
}
}
nums[i] = x;
quickSort(nums, l, i - 1);
quickSort(nums, i + 1, r);
}
}-
time:O(nlogn)
-
space:O(1)
堆排序
🟡912. 排序数组
给你一个整数数组
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 * 104Related Topics
数组
分治
桶排序
计数排序
基数排序
排序
堆（优先队列）
归并排序
class Solution {
public int[] sortArray(int[] nums) {
int len = nums.length;
Queue<Integer> heap = new PriorityQueue<>();
for (int i = 0; i < len; i++) {
heap.offer(nums[i]);
}
for (int i = 0; i < len; i++) {
nums[i] = heap.poll();
}
return nums;
}
}-
time:O(nlogn)
-
space:O(n)
🟡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] <= 104Related Topics
数组
分治
快速选择
排序
堆（优先队列）
class Solution {
public int findKthLargest(int[] nums, int k) {
int len = nums.length;
Queue<Integer> heap = new PriorityQueue<>(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
for (int i = 0; i < len; i++) {
heap.offer(nums[i]);
}
for (int i = 0; i < k - 1; i++) {
heap.poll();
}
return heap.poll();
}
}-
time:O(nlogn)
-
space:O(n)
🟡面试题 17.14. 最小K个数
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例：
输入： arr = [1,3,5,7,2,4,6,8], k = 4 输出： [1,2,3,4]提示：
0 <= len(arr) <= 1000000 <= k <= min(100000, len(arr))Related Topics
数组
分治
快速选择
排序
堆（优先队列）
class Solution {
public int[] smallestK(int[] arr, int k) {
int len = arr.length;
Queue<Integer> heap = new PriorityQueue<>();
for (int i = 0; i < len; i++) {
heap.offer(arr[i]);
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = heap.poll();
}
return res;
}
}-
time:O(nlogn)
-
space:O(n)
🟡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个高频元素的集合是唯一的**进阶：**你所设计算法的时间复杂度 必须 优于
O(n log n)，其中n是数组大小。Related Topics
数组
哈希表
分治
桶排序
计数
快速选择
排序
堆（优先队列）
import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int key = nums[i];
map.put(key, map.getOrDefault(key, 0) + 1);
}
Queue<Map.Entry<Integer, Integer>> heap = new PriorityQueue<>(new Comparator<Map.Entry<Integer, Integer>>() {
@Override
public int compare(Map.Entry<Integer, Integer> o1, Map.Entry<Integer, Integer> o2) {
return o2.getValue() - o1.getValue();
}
});
for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
heap.offer(entry);
}
int[] res = new int[k];
for (int i = 0; i < k; i++) {
res[i] = heap.poll().getKey();
}
return res;
}
}-
time:O(nlogn)
-
space:O(n)
🟡692. 前K个高频单词
给定一个单词列表
words和一个整数k，返回前k个出现次数最多的单词。返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率， 按字典顺序 排序。
示例 1：
输入: words = ["i", "love", "leetcode", "i", "love", "coding"], k = 2 输出: ["i", "love"] 解析: "i" 和 "love" 为出现次数最多的两个单词，均为2次。 注意，按字母顺序 "i" 在 "love" 之前。示例 2：
输入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4 输出: ["the", "is", "sunny", "day"] 解析: "the", "is", "sunny" 和 "day" 是出现次数最多的四个单词， 出现次数依次为 4, 3, 2 和 1 次。注意：
1 <= words.length <= 500
1 <= words[i] <= 10
words[i]由小写英文字母组成。
k的取值范围是[1, **不同** words[i] 的数量]**进阶：**尝试以
O(n log k)时间复杂度和O(n)空间复杂度解决。Related Topics
字典树
哈希表
字符串
桶排序
计数
排序
堆（优先队列）
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> map = new HashMap<>();
for (int i = 0; i < words.length; i++) {
String key = words[i];
map.put(key, map.getOrDefault(key, 0) + 1);
}
Queue<Map.Entry<String, Integer>> heap = new PriorityQueue<>(new Comparator<Map.Entry<String, Integer>>() {
@Override
public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
if (o1.getValue() != o2.getValue()) {
return o2.getValue() - o1.getValue();
} else {
return o1.getKey().compareTo(o2.getKey());
}
}
});
for (Map.Entry<String, Integer> entry : map.entrySet()) {
heap.offer(entry);
}
List<String> res = new ArrayList<>();
for (int i = 0; i < k; i++) {
res.add(heap.poll().getKey());
}
return res;
}
}-
time:O(nlogn)
-
space:O(n)
🔴23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6示例 2：
输入：lists = [] 输出：[]示例 3：
输入：lists = [[]] 输出：[]提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4Related Topics
链表
分治
堆（优先队列）
归并排序
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
Queue<Integer> heap = new PriorityQueue<>();
for (int i = 0; i < lists.length; i++) {
ListNode ptr = lists[i];
while (ptr != null) {
heap.offer(ptr.val);
ptr = ptr.next;
}
}
ListNode dummy = new ListNode(0);
ListNode ptr = dummy;
while (!heap.isEmpty()) {
ListNode node = new ListNode(heap.poll());
ptr.next = node;
ptr = ptr.next;
}
return dummy.next;
}
}-
time:O(nlogn)
-
space:O(n)
希尔排序
🟡912. 排序数组
给你一个整数数组
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 * 104Related Topics
数组
分治
桶排序
计数排序
基数排序
排序
堆（优先队列）
归并排序
class Solution{
public int[] sortArray(int[] nums){
int len= nums.length;
for (int gap = len / 2; gap > 0; gap /= 2) {
// 共gap个组，对每一组都执行直接插入排序
for (int i = 0 ;i < gap; i++) {
for (int j = i + gap; j < len; j += gap) {
// 如果nums[j] < nums[j-gap]，则寻找nums[j]位置，并将后面数据的位置都后移。
if (nums[j] < nums[j - gap]) {
int tmp = nums[j];
int k = j - gap;
while (k >= 0 && nums[k] > tmp) {
nums[k + gap] = nums[k];
k -= gap;
}
nums[k + gap] = tmp;
}
}
}
}
return nums;
}
}-
time:O(nlogn~O(n^2^))
-
space:O(n)
归并排序
🟡912. 排序数组
给你一个整数数组
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 * 104Related Topics
数组
分治
桶排序
计数排序
基数排序
排序
堆（优先队列）
归并排序
class Solution{
public int[] sortArray(int[] nums){
int len = nums.length;
mergeSort(nums,0,len-1);
return nums;
}
void mergeSort(int[] arr, int start, int end) {
//分治的结束条件
if (start >= end) {
return;
}
//保证不溢出取start和end的中位数
int mid = start + ((end - start) >> 1);
//递归排序并且合并
mergeSort(arr, start, mid);
mergeSort(arr, mid + 1, end);
merge(arr, start, mid, end);
}
void merge(int[] arr, int start, int mid, int end) {
int[] temp = new int[end - start + 1];
int p1 = start;
int p2 = mid + 1;
int p = 0;
while (p1 <= mid && p2 <= end) {
if (arr[p1] > arr[p2]) {
temp[p++] = arr[p2++];
} else {
temp[p++] = arr[p1++];
}
}
while (p1 <= mid) {
temp[p++] = arr[p1++];
}
while (p2 <= end) {
temp[p++] = arr[p2++];
}
for (int i = 0; i < temp.length; i++) {
arr[i + start] = temp[i];
}
}
}-
time:O(nlogn)
-
space:O(n)
🟡148. 排序链表
给你链表的头结点
head，请将其按 升序 排列并返回 排序后的链表 。示例 1：
输入：head = [4,2,1,3] 输出：[1,2,3,4]示例 2：
输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]示例 3：
输入：head = [] 输出：[]提示：
链表中节点的数目在范围
[0, 5 * 104]内
-105 <= Node.val <= 105**进阶：**你可以在
O(n log n)时间复杂度和常数级空间复杂度下，对链表进行排序吗？Related Topics
链表
双指针
分治
排序
归并排序
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode mid = getMiddle(head);
ListNode left = sortList(head);
ListNode right = sortList(mid);
return merge(left, right);
}
ListNode getMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while (fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
ListNode mid = slow.next;
slow.next = null;
return mid;
}
ListNode merge(ListNode l1, ListNode l2) {
ListNode res = new ListNode(0);
ListNode p = res;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null) {
p.next = l1;
}
if (l2 != null) {
p.next = l2;
}
return res.next;
}
}-
time:O(nlogn)
-
space:O(n)
🔴23. 合并 K 个升序链表
给你一个链表数组，每个链表都已经按升序排列。
请你将所有链表合并到一个升序链表中，返回合并后的链表。
示例 1：
输入：lists = [[1,4,5],[1,3,4],[2,6]] 输出：[1,1,2,3,4,4,5,6] 解释：链表数组如下： [ 1->4->5, 1->3->4, 2->6 ] 将它们合并到一个有序链表中得到。 1->1->2->3->4->4->5->6示例 2：
输入：lists = [] 输出：[]示例 3：
输入：lists = [[]] 输出：[]提示：
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500-10^4 <= lists[i][j] <= 10^4lists[i]按 升序 排列lists[i].length的总和不超过10^4Related Topics
链表
分治
堆（优先队列）
归并排序
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
int len= lists.length;
if(len==0){
return null;
}
return biaryMerge(lists,0,len-1);
}
ListNode biaryMerge(ListNode[] lists,int i,int j){
if(i>j){
return null;
} else if (i==j) {
return lists[i];
}
int mid=(i+j)/2;
return merge(biaryMerge(lists,i,mid),biaryMerge(lists,mid+1,j));
}
ListNode merge(ListNode l1, ListNode l2) {
ListNode res = new ListNode(0);
ListNode p = res;
while (l1 != null && l2 != null) {
if (l1.val < l2.val) {
p.next = l1;
l1 = l1.next;
} else {
p.next = l2;
l2 = l2.next;
}
p = p.next;
}
if (l1 != null) {
p.next = l1;
}
if (l2 != null) {
p.next = l2;
}
return res.next;
}
}-
time:O(nlogk)
-
space:O(n + log(k))
计数排序
🟡912. 排序数组
给你一个整数数组
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 * 104Related Topics
数组
分治
桶排序
计数排序
基数排序
排序
堆（优先队列）
归并排序
class Solution {
public int[] sortArray(int[] nums) {
// 找到数组中的最大值和最小值
int min = Arrays.stream(nums).min().getAsInt();
int max = Arrays.stream(nums).max().getAsInt();
// 计算计数数组的长度
int length = max - min + 1;
int[] count = new int[length];
// 统计每个元素的出现次数
for (int num : nums) {
count[num - min]++;
}
// 将计数数组转换为前缀和数组
for (int i = 1; i < length; i++) {
count[i] += count[i - 1];
}
// 创建临时数组存储排序后的结果
int[] res = new int[nums.length];
// 将元素按照计数数组的前缀和分配到临时数组
for (int i = nums.length - 1; i >= 0; i--) {
int index = count[nums[i] - min] - 1;
res[index] = nums[i];
count[nums[i] - min]--;
}
return res;
}
}-
time:O(n)
-
space:O(n)
🟡75. 颜色分类
给定一个包含红色、白色和蓝色、共
n个元素的数组nums，**原地**对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。我们使用整数
0、1和2分别表示红色、白色和蓝色。必须在不使用库内置的 sort 函数的情况下解决这个问题。
示例 1：
输入：nums = [2,0,2,1,1,0] 输出：[0,0,1,1,2,2]示例 2：
输入：nums = [2,0,1] 输出：[0,1,2]提示：
n == nums.length
1 <= n <= 300
nums[i]为0、1或2进阶：
- 你能想出一个仅使用常数空间的一趟扫描算法吗？
Related Topics
数组
双指针
排序
class Solution {
public void sortColors(int[] nums) {
int len= nums.length;
int num0=0,num1=0;
for (int i = 0; i < len; i++) {
int num=nums[i];
nums[i]=2;
if(num<2){
nums[num1++]=1;
}
if(num<1){
nums[num0++]=0;
}
}
}
}-
time:O(n)
-
space:O(1)
桶排序
🟡912. 排序数组
给你一个整数数组
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 * 104Related Topics
数组
分治
桶排序
计数排序
基数排序
排序
堆（优先队列）
归并排序
class Solution{
public int[]sortArray(int[]nums){
int len=nums.length;
int MAX=200000;
int HALF=50001;
int min=nums[0]+HALF;
int max=nums[0]+HALF;
int[]bucket=new int[MAX];
for (int i = 0; i < len; i++) {
bucket[nums[i]+HALF]++;
min=Math.min(min,nums[i]+HALF);
max=Math.max(max,nums[i]+HALF);
}
int index=0;
for (int i = min; i <= max; i++) {
for (int j = 0; j < bucket[i]; j++) {
nums[index++]=i-HALF;
}
}
return nums;
}
}-
time:O(n)
-
space:O(1)
小小改良版
class Solution{
public int[] sortArray(int[] nums){
int len = nums.length;
int min = nums[0];
int max = nums[0];
for (int i = 0; i < len; i++) {
min = Math.min(min, nums[i]);
max = Math.max(max, nums[i]);
}
int range = max - min + 1;
int[] bucket = new int[range];
for (int i = 0; i < len; i++) {
bucket[nums[i] - min]++;
}
int index = 0;
for (int i = 0; i < range; i++) {
for (int j = 0; j < bucket[i]; j++) {
nums[index++] = i + min;
}
}
return nums;
}
}-
time:O(n+range)
-
space:O(range)
🟡148. 排序链表
给你链表的头结点
head，请将其按 升序 排列并返回 排序后的链表 。示例 1：
输入：head = [4,2,1,3] 输出：[1,2,3,4]示例 2：
输入：head = [-1,5,3,4,0] 输出：[-1,0,3,4,5]示例 3：
输入：head = [] 输出：[]提示：
链表中节点的数目在范围
[0, 5 * 104]内
-105 <= Node.val <= 105**进阶：**你可以在
O(n log n)时间复杂度和常数级空间复杂度下，对链表进行排序吗？Related Topics
链表
双指针
分治
排序
归并排序
class Solution {
public ListNode sortList(ListNode head) {
if (head == null || head.next == null) {
return head;
}
ListNode ptr=head;
int max=head.val;
int min=head.val;
while (ptr!=null){
max=Math.max(max,ptr.val);
min=Math.min(min,ptr.val);
ptr=ptr.next;
}
int range = max - min + 1;
int[] bucket = new int[range];
ptr=head;
while (ptr!=null){
bucket[ptr.val - min]++;
ptr=ptr.next;
}
ptr=head;
for (int i = 0; i < range; i++) {
for (int j = 0; j < bucket[i]; j++) {
ptr.val=i+min;
ptr=ptr.next;
}
}
return head;
}
}- time:O(n+range)
- space:O(range)
基数排序
🟡912. 排序数组
给你一个整数数组
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 * 104Related Topics
数组
分治
桶排序
计数排序
基数排序
排序
堆（优先队列）
归并排序
class Solution{
public int[] sortArray(int[] nums){
// 找到数组中的最小值
int min = Arrays.stream(nums).min().getAsInt();
if(min<0){
for (int i = 0; i < nums.length; i++) {
nums[i]-=min;
}
}
// 找到数组中的最大值
int max = Arrays.stream(nums).max().getAsInt();
// 计算最大值的位数
int digits = String.valueOf(max).length();
// 进行 digits 轮计数排序
for (int i = 0; i < digits; i++) {
nums = countingSort(nums, i);
}
if(min<0){
for (int i = 0; i < nums.length; i++) {
nums[i]+=min;
}
}
return nums;
}
private int[] countingSort(int[] nums, int digit) {
// 创建计数数组
int[] count = new int[10];
// 统计每个数字的出现次数
for (int num : nums) {
int d = (int)(num / Math.pow(10, digit)) % 10;
count[d]++;
}
// 将计数数组转换为前缀和数组
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1];
}
// 创建临时数组存储排序后的结果
int[] res = new int[nums.length];
// 将元素按照计数数组的前缀和分配到临时数组
for (int i = nums.length - 1; i >= 0; i--) {
int d = (int)(nums[i] / Math.pow(10, digit)) % 10;
int index = count[d] - 1;
res[index] = nums[i];
count[d]--;
}
return res;
}
}- time:O(n+digits)
- space:O(1)
特别排序
🟡179. 最大数
给定一组非负整数
nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。**注意：**输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入：nums = [10,2] 输出："210"示例 2：
输入：nums = [3,30,34,5,9] 输出："9534330"提示：
1 <= nums.length <= 1000 <= nums[i] <= 109Related Topics
贪心
数组
字符串
排序
class Solution {
public String largestNumber(int[] nums) {
Comparator<Integer> comparator = new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
String sa = String.valueOf(o1);
String sb = String.valueOf(o2);
return (sb + sa).compareTo(sa + sb);
}
};
Integer[] numbers = new Integer[nums.length];
for (int i = 0; i < nums.length; i++) {
numbers[i] = nums[i];
}
Arrays.sort(numbers, comparator);
StringBuilder sb=new StringBuilder();
int flag=0;
for (int i = 0; i < numbers.length; i++) {
if(numbers[i]!=0||flag==1){
flag=1;
sb.append(numbers[i]);
}
}
if(sb.isEmpty()){
return "0";
}else{
return sb.toString();
}
}
}- time:*O(n·m·logn)*m为两个数字的位数之和
- space:O(n)
评论 (0)
