排序数组
数组
C++
Java
Python
前言
本题你可以选择直接调用库函数来对序列进行排序，但意义不大。由于排序算法有很多，本文只介绍三种常见的基于比较的复杂度较低的排序。
方法一：快速排序
思路和算法
快速排序的主要思想是通过划分将待排序的序列分成前后两部分，其中前一部分的数据都比后一部分的数据要小，然后再递归调用函数对两部分的序列分别进行快速排序，以此使整个序列达到有序。
我们定义函数 randomized_quicksort(nums, l, r) 为对 nums 数组里
那么核心就是划分函数的实现了，划分函数一开始需要确定一个分界值（我们称之为主元 pivot)，然后再进行划分。而主元的选取有很多种方式，这里我们采用随机的方式，对当前划分区间
整个划分函数 partition 主要涉及两个指针
我们每次移动指针
当
如下的动图展示了一次划分的过程，刚开始随机选了
C++
Java
class Solution {
int partition(vector<int>& nums, int l, int r) {
int pivot = nums[r];
int i = l - 1;
for (int j = l; j <= r - 1; ++j) {
if (nums[j] <= pivot) {
i = i + 1;
swap(nums[i], nums[j]);
}
}
swap(nums[i + 1], nums[r]);
return i + 1;
}
int randomized_partition(vector<int>& nums, int l, int r) {
int i = rand() % (r - l + 1) + l; // 随机选一个作为我们的主元
swap(nums[r], nums[i]);
return partition(nums, l, r);
}
void randomized_quicksort(vector<int>& nums, int l, int r) {
if (l < r) {
int pos = randomized_partition(nums, l, r);
randomized_quicksort(nums, l, pos - 1);
randomized_quicksort(nums, pos + 1, r);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
srand((unsigned)time(NULL));
randomized_quicksort(nums, 0, (int)nums.size() - 1);
return nums;
}
};
复杂度分析
- 时间复杂度：基于随机选取主元的快速排序时间复杂度为期望
- 空间复杂度：
方法二：堆排序
预备知识
- 堆
思路和算法
堆排序的思想就是先将待排序的序列建成大根堆，使得每个父节点的元素大于等于它的子节点。此时整个序列最大值即为堆顶元素，我们将其与末尾元素交换，使末尾元素为最大值，然后再调整堆顶元素使得剩下的
如下两个动图展示了对 [4, 6, 8, 5, 9] 这个数组堆排序的过程：
C++
Java
Python3
class Solution {
void maxHeapify(vector<int>& nums, int i, int len) {
for (; (i << 1) + 1 <= len;) {
int lson = (i << 1) + 1;
int rson = (i << 1) + 2;
int large;
if (lson <= len && nums[lson] > nums[i]) {
large = lson;
} else {
large = i;
}
if (rson <= len && nums[rson] > nums[large]) {
large = rson;
}
if (large != i) {
swap(nums[i], nums[large]);
i = large;
} else {
break;
}
}
}
void buildMaxHeap(vector<int>& nums, int len) {
for (int i = len / 2; i >= 0; --i) {
maxHeapify(nums, i, len);
}
}
void heapSort(vector<int>& nums) {
int len = (int)nums.size() - 1;
buildMaxHeap(nums, len);
for (int i = len; i >= 1; --i) {
swap(nums[i], nums[0]);
len -= 1;
maxHeapify(nums, 0, len);
}
}
public:
vector<int> sortArray(vector<int>& nums) {
heapSort(nums);
return nums;
}
};
复杂度分析
- 时间复杂度：
- 空间复杂度：
方法三：归并排序
思路
归并排序利用了分治的思想来对序列进行排序。对一个长为
算法
定义 mergeSort(nums, l, r) 函数表示对 nums 数组里
- 递归调用函数
mergeSort(nums, l, mid)对nums数组里 - 递归调用函数
mergeSort(nums, mid + 1, r)对nums数组里 - 此时
nums数组里
线性归并的过程并不难理解，由于两个区间均有序，所以我们维护两个指针
如果nums[i] <= nums[j]，那么我们就将
这样能保证我们每次都是让两个区间中较小的数加入临时数组里，那么整个归并过程结束后
如下的动图展示了两个有序数组线性归并的过程：
函数递归调用的入口为 mergeSort(nums, 0, nums.length - 1)，递归结束当且仅当 l >= r。
C++
Java
Python3
class Solution {
vector<int> tmp;
void mergeSort(vector<int>& nums, int l, int r) {
if (l >= r) return;
int mid = (l + r) >> 1;
mergeSort(nums, l, mid);
mergeSort(nums, mid + 1, r);
int i = l, j = mid + 1;
int cnt = 0;
while (i <= mid && j <= r) {
if (nums[i] <= nums[j]) {
tmp[cnt++] = nums[i++];
}
else {
tmp[cnt++] = nums[j++];
}
}
while (i <= mid) {
tmp[cnt++] = nums[i++];
}
while (j <= r) {
tmp[cnt++] = nums[j++];
}
for (int i = 0; i < r - l + 1; ++i) {
nums[i + l] = tmp[i];
}
}
public:
vector<int> sortArray(vector<int>& nums) {
tmp.resize((int)nums.size(), 0);
mergeSort(nums, 0, (int)nums.size() - 1);
return nums;
}
};
复杂度分析
- 时间复杂度：
根据主定理我们可以得出归并排序的时间复杂度为
- 空间复杂度：
class Solution:
def merge_sort(self, nums, l, r):
if l == r:
return
mid = (l + r) // 2
self.merge_sort(nums, l, mid)
self.merge_sort(nums, mid + 1, r)
tmp = []
i, j = l, mid + 1
while i <= mid or j <= r:
if i > mid or (j <= r and nums[j] < nums[i]):
tmp.append(nums[j])
j += 1
else:
tmp.append(nums[i])
i += 1
nums[l: r + 1] = tmp
def sortArray(self, nums: List[int]) -> List[int]:
self.merge_sort(nums, 0, len(nums) - 1)
return nums
链接：https://leetcode.cn/problems/sort-an-array/solutions/178305/pai-xu-shu-zu-by-leetcode-solution/
class Solution:
def max_heapify(self, heap, root, heap_len):
p = root
while p * 2 + 1 < heap_len:
l, r = p * 2 + 1, p * 2 + 2
if heap_len <= r or heap[r] < heap[l]:
nex = l
else:
nex = r
if heap[p] < heap[nex]:
heap[p], heap[nex] = heap[nex], heap[p]
p = nex
else:
break
def build_heap(self, heap):
for i in range(len(heap) - 1, -1, -1):
self.max_heapify(heap, i, len(heap))
def heap_sort(self, nums):
self.build_heap(nums)
for i in range(len(nums) - 1, -1, -1):
nums[i], nums[0] = nums[0], nums[i]
self.max_heapify(nums, 0, i)
def sortArray(self, nums: List[int]) -> List[int]:
self.heap_sort(nums)
return nums
链接：https://leetcode.cn/problems/sort-an-array/solutions/178305/pai-xu-shu-zu-by-leetcode-solution/
给你一个整数数组 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