冒泡排序
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
for(int i = nums.size()-1;i > 0;i--)
{
for(int j = 0;j < i;j++)
if(nums[j] > nums[j+1])
swap(nums[j],nums[j+1]);
}
return nums;
}
};
执行结果:
Time Limit Exceeded
Details
Last executed input
[5864,-12333,4151,-6239,-10306,10866,-7013,13195,-8855,1150,-560,3227,10387,-2329,5169,-19527,2689,597,4255,-13697,12495,19719,15995,8991,-12859,5601,8195,3943,16216,-19677,15590,10316,-4255,45,-6508,-5416,4993,15278,-6015,-18843,-8400,-6994,3608,-7695,-14698,-2684,8753,18019,3266,-10860,-14354,8708,19037,-16188,4932,1403,-10571,18368,-9786,13410,1686,-17352,-13827,6647,16747,2664,-15830,13673,-10248,2115,-19074,-919,4382,18718,-7449,-16031,333,-14066,-2505,-9975,-226,-18986,17487,-3498,-17203,-3506,8462,-191,10563,10160,12627,-8306,9439,-16640,4586,-12067,-19904,-5607,-15989,15651,-18358,-850,-850,3472,8969,13113,1269,4808,123,16848,9857,17099,14566,4854,-19826,957,-10325,-8686,11542,-10343,-16353,-9446,-18914,3242,5897,-19881,-16532,14827,-5840,2873,-10823,-4545,5028,-4985,15482,-8196,14376,-11370,4044,-18929,15051,5562,15969,-4135,13438,12928,-5472,10521,11392,-16511,461,12535,12429,13353,5861,6523,2158,16888,8264,580,-18042,-10113,-809,3072,14636,-12239,-18102,8235,14993,-15364,-19
View All
选择排序
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
//选择排序
for(int i = 0;i < nums.size() - 1;i++)
{
int loc = i;
for(int j = i;j < nums.size();j++)
if(nums[j] < nums[loc])
loc = j;
swap(nums[i],nums[loc]);
}
return nums;
}
};
运行结果Time Limit Exceeded,我们发现O(n2)复杂度的算法是行不通的。
快速排序
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;
}
};
运行效率:
执行用时:80 ms, 在所有 C++ 提交中击败了29.01%的用户
内存消耗:27.8 MB, 在所有 C++ 提交中击败了28.64%的用户
归并排序
youtube上有个up主讲解的非常清晰,归并排序
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
merge_sort(nums,0,nums.size() - 1);
return nums;
}
private:
void merge_sort(vector<int>& nums,int l,int r)
{
if(l >= r) return;
int m = l + (r - l)/2;
merge_sort(nums,l,m);
merge_sort(nums,m + 1,r);
merge(nums,l,m,r);
}
void merge(vector<int>& nums,int l,int m,int r)
{
vector<int> tmp(r-l+1);
int p = l,q = m + 1,loc = 0;
while(p <= m && q <= r)
{
if(nums[p] <= nums[q])
tmp[loc++] = nums[p++];
else
tmp[loc++] = nums[q++];
}
while(p <= m) tmp[loc++] = nums[p++];
while(q <= r) tmp[loc++] = nums[q++];
for(int i = 0;i < loc;i++)
nums[l + i] = tmp[i];
}
};
归并排序运行效率:
执行用时:240 ms, 在所有 C++ 提交中击败了5.02%的用户
内存消耗:70.4 MB, 在所有 C++ 提交中击败了5.03%的用户
在力扣提交代码后看到提交榜击败100%的一个大佬提交的代码:
class Solution {
public:
// 插入
void Insertion_Sort(vector<int>& nums)
{
for (int i = 1; i < nums.size(); i++)
{
int t = nums[i];
int j = i - 1;
for (; j >= 0 && nums[j] > t; j--)
{
nums[j + 1] = nums[j];
}
nums[j + 1] = t;
}
}
// 冒泡
void Bubble_Sort(vector<int>& nums)
{
for (int i = 0; i < nums.size(); i++)
{
bool flag = false;
for (int j = nums.size() - 1; j > i; j--)
{
if (nums[j - 1] > nums[j])
{
swap(nums[j - 1], nums[j]);
flag = true;
}
}
if (!flag)
{
return;
}
}
}
// 选择
void Selection_Sort(vector<int>& nums)
{
for (int i = 0; i < nums.size(); i++)
{
int minIndex = i;
for (int j = i + 1; j < nums.size(); j++)
{
if (nums[minIndex] > nums[j])
{
minIndex = j;
}
}
swap(nums[i], nums[minIndex]);
}
}
// 希尔
void Shell_Sort(vector<int>& nums)
{
for (int gap = nums.size() / 2; gap > 0; gap /= 2)
{
for (int i = gap; i < nums.size(); i++)
{
int t = nums[i];
int j = i - gap;
for (; j >= 0 && nums[j] > t; j -= gap)
{
nums[j + gap] = nums[j];
}
nums[j + gap] = t;
}
}
}
// 堆
void Adjust(vector<int>& nums, int n, int i)
{
int maxn = i, l = i * 2 + 1, r = i * 2 + 2;
if (l < n && nums[maxn] < nums[l])
{
maxn = l;
}
if (r < n && nums[maxn] < nums[r])
{
maxn = r;
}
if (maxn != i)
{
swap(nums[i], nums[maxn]);
Adjust(nums, n, maxn);
}
}
void Heap_Sort(vector<int>& nums)
{
int n = nums.size();
for (int i = n / 2 - 1; i >= 0; i--)
{
Adjust(nums, n, i);
}
for (int i = n - 1; i >= 0; i--)
{
swap(nums[0], nums[i]);
Adjust(nums, i, 0);
}
}
// 归并
void Merge_Sort(vector<int>& nums, vector<int>& T, int l, int r)
{
if (r - l < 2)
{
return;
}
int m = l + (r - l) / 2;
Merge_Sort(nums, T, l, m);
Merge_Sort(nums, T, m, r);
int p = l, q = m, i = l;
while (p < m || q < r)
{
if (q >= r || p < m && nums[p] <= nums[q])
{
T[i++] = nums[p++];
}
else
{
T[i++] = nums[q++];
}
}
for (i = l; i < r; i++)
{
nums[i] = T[i];
}
}
// 快速
void Quick_Sort(vector<int>& nums, int l, int r)
{
if (l + 1 >= r)
{
return;
}
int i = l, j = r - 1, pivot = nums[l];
while (i < j)
{
while (i < j && pivot <= nums[j])
{
j--;
}
nums[i] = nums[j];
while (i < j && pivot >= nums[i])
{
i++;
}
nums[j] = nums[i];
}
nums[i] = pivot;
Quick_Sort(nums, l, i);
Quick_Sort(nums, i + 1, r);
}
// 计数
void Count_Sort(vector<int>& nums)
{
int minn = *min_element(nums.begin(), nums.end());
int maxn = *max_element(nums.begin(), nums.end());
vector<int> cnt(maxn - minn + 1, 0);
for (int& num : nums)
{
cnt[num - minn]++;
}
int cur = 0;
for (int i = 0; i < cnt.size(); i++)
{
while(cnt[i] > 0)
{
nums[cur++] = i + minn;
cnt[i]--;
}
}
}
vector<int> sortArray(vector<int>& nums) {
// Insertion_Sort(nums);
// Bubble_Sort(nums);
// Selection_Sort(nums);
// Shell_Sort(nums);
// vector<int> T(nums);
// Merge_Sort(nums, T, 0, nums.size());
// Quick_Sort(nums, 0, nums.size());
// Heap_Sort(nums);
Count_Sort(nums);
return nums;
}
};
这里我们重点介绍下计数排序:
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
Count_Sort(nums);
return nums;
}
private:
void Count_Sort(vector<int>& nums) {
int min = *min_element(nums.begin(),nums.end());
int max = *max_element(nums.begin(),nums.end());
int loc = 0;
vector<int> count(max-min+1,0);
for(auto num:nums) {
count[num - min]++;
}
for(int i = 0;i < count.size();i++) {
while(count[i] > 0)
{
nums[loc++] = i + min;
count[i]--;
}
}
}
};
运行效率:
执行用时:56 ms, 在所有 C++ 提交中击败了49.69%的用户
内存消耗:28.5 MB, 在所有 C++ 提交中击败了11.42%的用户
堆排序实现:
class Solution {
public:
vector<int> sortArray(vector<int>& nums) {
Heap_Sort(nums);
return nums;
}
private:
// 堆
void Adjust(vector<int>& nums, int n, int i)
{
int maxn = i,l = 2 * i + 1,r = l + 1;
if(l < n && nums[l] > nums[maxn])
maxn = l;
if(r < n && nums[r] > nums[maxn])
maxn = r;
if(maxn != i)
{
swap(nums[maxn],nums[i]);
Adjust(nums,n,maxn);
}
}
void Heap_Sort(vector<int>& nums)
{
int n = nums.size();
//从最后一个结点的父结点开始调整
for (int i = (n-2)/2; i >= 0; i--)
{
Adjust(nums, n, i);
}
for (int i = n - 1; i >= 0; i--)
{
//nums[0](最大值与最后一个元素交换)
swap(nums[0], nums[i]);
//重新调整,元素个数变为i
Adjust(nums, i, 0);
}
}
};
运行效率:
执行用时:96 ms, 在所有 C++ 提交中击败了18.26%的用户
内存消耗:27.7 MB, 在所有 C++ 提交中击败了45.79%的用户