解题思路:
注意事项: 法一 分治法注意事项 内循环的while(i<j&&nums[j]>=key)和while(i<j&&nums[i]<=key) 必须加等号
法二 挖坑填数法注意事项 最后是 nums[i]=key;
参考代码:
法一 分治法:
#include<iostream>
#include<algorithm>
#include<vector>
using namespace std;
//利用基于范围的for循环可以快速打印容器元素
void print(vector<int> nums)
{
for(auto i:nums)
{
cout<<i<<" ";
}
}
void quickSort(vector<int>&nums,int left,int right)
{
if(left>=right) return;
int i=left;
int j=right,key=nums[left];
while(i!=j)
{
while(i<j&&nums[j]>=key)
{
j--;
}
while(i<j&&nums[i]<=key)
{
i++;
}
swap(nums[i],nums[j]);
}
nums[left]=nums[i];
nums[i]=key;
quickSort(nums,left,i-1);
quickSort(nums,i+1,right);
}
法二 挖坑填数法:
void quickSort2(vector<int>&nums,int left,int right)
{
if(left>=right) return;
int i=left,j=right,key=nums[left];
while(i<j)
{
while(i<j&&nums[j]>=key)
{
j--;
}
if(i<j)
{
nums[i]=nums[j];
i++;
}
while(i<j&&nums[i]<key)
{
i++;
}
if(i<j)
{
nums[j]=nums[i];
j--;
}
}
nums[i]=key;
quickSort2(nums,left,i-1);
quickSort2(nums,i+1,right);
}
int main()
{
vector<int>nums;
int n,x;
cin>>n;
while(n--)
{
cin>>x;
nums.push_back(x);
}
quickSort(nums,0,nums.size()-1);
print(nums);
return 0;
}
0.0分
0 人评分
C语言程序设计教程(第三版)课后习题6.3 (C语言代码)浏览:516 |
矩阵乘法 (C++代码)浏览:1461 |
C语言程序设计教程(第三版)课后习题6.4 (C语言代码)浏览:603 |
C语言程序设计教程(第三版)课后习题4.9 (C语言代码)浏览:600 |
WU-字符串比较 (C++代码)浏览:756 |
简单的a+b (C语言代码)浏览:816 |
1013题解浏览:560 |
A+B for Input-Output Practice (VI) (C语言代码)浏览:558 |
C语言程序设计教程(第三版)课后习题7.3 (C语言代码)浏览:533 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:2166 |