-
329. 矩阵中的最长递增路径 - 力扣（LeetCode）
见上篇 2024-09-30 - 简书 (jianshu.com) -
面试题 04.06. 后继者 - 力扣（LeetCode）
见上篇 2024-09-30 - 简书 (jianshu.com) -
912. 排序数组 - 力扣（LeetCode）
排序一：冒泡排序==稳定==n^2==1
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
return bubbleSort(nums);
}
private:
vector<int> bubbleSort(vector<int>& nums) {
int n = nums.size();
for (int i = 0; i < n - 1; i++) {
bool flag = false;
for (int j = 0; j < n - 1 - i; j++) {
if (nums[j] > nums[j + 1]) {
swap(nums[j], nums[j + 1]); // 稳定
flag = true;
}
}
if (flag == false) break;
}
return nums;
}
};
排序二：选择排序==不稳定==n^2==1
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
return selectSort(nums);
}
private:
vector<int> selectSort(vector<int> &nums) {
int n = nums.size();
for (int i = 0; i < n - 1; ++i) {
int minIndex = i;
for (int j = i + 1; j < n; ++j)
if (nums[j] < nums[minIndex])
minIndex = j;
swap(nums[i], nums[minIndex]); // 不稳定
}
return nums;
}
};
排序三：插入排序==稳定==n^2==1
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
return insertSort(nums);
}
private:
vector<int> insertSort(vector<int>& nums) {
int n = nums.size();
for (int i = 1; i < n; i++)
for (int j = i; j > 0; j--)
if (nums[j - 1] > nums[j]) // 稳定
swap(nums[j - 1], nums[j]);
else break; // !!!
return nums;
}
};
排序四：希尔排序==不稳定==nlogn和n^2之间==1
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
return shellSort(nums);
}
private:
vector<int> shellSort(vector<int>& nums) {
int n = nums.size();
for (int gap = n / 2; gap > 0; gap /= 2)
for (int i = gap; i < n; i++)
for (int j = i; j - gap >= 0; j -= gap)
if (nums[j - gap] > nums[j])
swap(nums[j - gap], nums[j]); // 不稳定
else break; // !!!
return nums;
}
};
排序五：归并排序==稳定==nlogn==n
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int left = 0, right = nums.size() - 1;
mergeSort(nums, left, right);
return nums;
}
private:
void mergeSort(vector<int>& nums, int left, int right) {
if (left >= right) return;
int mid = (left + right) / 2;
mergeSort(nums, left, mid);
mergeSort(nums, mid + 1, right);
merge(nums, left, mid, right);
}
void merge(vector<int>& nums, int left, int mid, int right) {
// nums[left...mid] nums[mid+1...right]
int size = right - left + 1;
vector<int> temp(size);
int i = left, j = mid + 1, k = 0;
for (; k < size; k++)
if (j > right || (i <= mid && nums[i] <= nums[j])) // 稳定
temp[k] = nums[i++];
else
temp[k] = nums[j++];
for (k = 0; k < size; k++)
nums[left + k] = temp[k];
}
};
排序六：堆排序-不稳定-nlogn-1
法一：优先队列
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
heapSort(nums);
return nums;
}
private:
void heapSort(vector<int>& nums) {
int n = nums.size();
priority_queue<int> q;
for (int i = 0; i < n; i++) q.push(-nums[i]);
for (int i = 0; i < n; i++) {
nums[i] = -q.top();
q.pop();
}
}
};
法二：自实现二叉堆
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
heapSort(nums);
return nums;
}
private:
void heapSort(vector<int>& nums) {
int n = nums.size();
for (int i = n / 2 - 1; i >= 0; i--)
heapifyDown(nums, i, n);
for (int i = n - 1; i >= 0; i--) {
swap(nums[0], nums[i]); // 不稳定
heapifyDown(nums, 0, i);
}
}
void heapifyDown(vector<int>& nums, int index, int size) {
int left = index * 2 + 1, right = index * 2 + 2;
int max = index;
if (left < size && nums[left] > nums[max])
max = left;
if (right < size && nums[right] > nums[max])
max = right;
if (max != index) {
swap(nums[max], nums[index]);
heapifyDown(nums, max, size);
}
}
};
排序七：快速排序==不稳定==nlogn==logn
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
quickSort(nums, 0, nums.size() - 1);
return nums;
}
private:
void quickSort(vector<int>& nums, int left, int right) {
if (left >= right) return;
int pivot = partition(nums, left, right);
quickSort(nums, left, pivot); // A
quickSort(nums, pivot + 1, right);
}
int partition(vector<int>& nums, int left, int right) {
int pivot = left + rand() % (right - left + 1);
int pivotVal = nums[pivot];
while (left <= right) {
while (nums[left] < pivotVal) left++; // 此处代入pivotVal一起排序，所以为<，A处同理
while (nums[right] > pivotVal) right--;
if (left < right) {
swap(nums[left], nums[right]);
left++; right--;
}
else break;
}
return right;
}
};
排序八：计数排序==稳定==(n+k)==(k)
k=maxNum-minNum+1
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
int minVal = INT_MAX, maxVal = INT_MIN;
for (int num : nums) {
minVal = min(minVal, num);
maxVal = max(maxVal, num);
}
vector<int> temp(maxVal - minVal + 1);
for (int num : nums) temp[num - minVal]++;
int k = 0;
for (int i = 0; i < temp.size(); i++)
while (temp[i] > 0) {
nums[k++] = minVal + i;
temp[i]--;
}
return nums;
}
};
