题解 | #排序# C++常用的七种排序算法
排序
http://www.nowcoder.com/practice/2baf799ea0594abd974d37139de27896
1.冒泡排序
时间复杂度O(n^2) 空间复杂度O(1) 稳定
class Solution {
public:
//冒泡排序
void BubbleSort(vector<int>& a)
{
for(int i=0;i<a.size()-1;i++)
for(int j=1;j<a.size()-i;j++)
if(a[j-1]>a[j])
swap(a[j-1],a[j]);
}
vector<int> MySort(vector<int>& arr) {
BubbleSort(arr);
return arr;
}
};
2.直接选择排序
时间复杂度O(n^2) 空间复杂度O(1) 不稳定
class Solution {
public:
//直接选择排序
void SelectSort(vector<int>& a)
{
for(int i=0;i<a.size();i++)
{
int min=i;
for(int j=i;j<a.size();j++)
if(a[j]<a[min])
min=j;
swap(a[i],a[min]);
}
}
vector<int> MySort(vector<int>& arr) {
SelectSort(arr);
return arr;
}
};
3.插入排序
时间复杂度O(n^2) 空间复杂度O(1) 稳定
class Solution {
public:
//插入排序
void InsertSort(vector<int>& a)
{
for(int i=1;i<a.size();i++)
{
if(a[i]<a[i-1])
{
int tmp=a[i];
int j=i;
while(tmp<a[j-1])
{
a[j]=a[j-1];
j--;
}
a[j]=tmp;
}
}
}
vector<int> MySort(vector<int>& arr) {
InsertSort(arr);
return arr;
}
};
4.希尔排序
时间复杂度O(n^1.3) 空间复杂度O(1) 不稳定
class Solution {
public:
//Shell排序
void ShellSort(vector<int>& a)
{
int h=1;
while(h<a.size()/3)
h=3*h+1;
while(h>=1)
{
for(int i=h;i<a.size();i++)
for(int j=i;j>=h&&a[j]<a[j-h];j-=h)
swap(a[j],a[j-h]);
h/=3;
}
}
vector<int> MySort(vector<int>& arr) {
ShellSort(arr);
return arr;
}
};
5.快速排序
时间复杂度O(nlogn) 空间复杂度O(nlogn) 不稳定
class Solution {
public:
//快速排序
void QuickSort(vector<int>& a,int l,int r)
{
if(l>=r) return;
int i=l,j=r,temp=a[i];
while(i<j)
{
while(i<j&&a[j]>=temp)
j--;
if(i<j)
{
a[i]=a[j];
i++;
}
while(i<j&&a[i]<temp)
i++;
if(i<j)
{
a[j]=a[i];
j--;
}
}
a[i]=temp;
QuickSort(a,l,i-1);
QuickSort(a,i+1,r);
}
vector<int> MySort(vector<int>& arr) {
QuickSort(arr,0,arr.size()-1);
return arr;
}
};
6.归并排序
时间复杂度O(nlogn) 空间复杂度O(1) 稳定
class Solution {
public:
//归并排序
void Merge(vector<int>& a,int l,int r)
{
if(l>=r)
return;
int m=(l+r)/2;
Merge(a,l,m);
Merge(a,m+1,r);
MergeSort(a,l,m,r);
}
void MergeSort(vector<int>& a,int l,int m,int r)
{
vector<int>temp;
int left=l,right=m+1;
while(left<=m&&right<=r)
temp.emplace_back(a[left]<=a[right]?a[left++]:a[right++]);
while(left<=m)
temp.emplace_back(a[left++]);
while(right<=r)
temp.emplace_back(a[right++]);
for(int j=0;j<temp.size();j++)
a[l+j]=temp[j];
}
vector<int> MySort(vector<int>& arr) {
Merge(arr,0,arr.size()-1);
return arr;
}
};
7.堆排序
时间复杂度O(nlogn) 空间复杂度O(1) 不稳定
class Solution {
public:
//堆排序
void MaxHeapify(vector<int>& a,int start,int end)
{
int dad=start;
int son=dad*2+1;
while(son<=end)
{
if(son+1<=end&&a[son+1]>a[son])
son++;
if(a[dad]>a[son])
return;
else
{
swap(a[dad],a[son]);
dad=son;
son=dad*2+1;
}
}
}
void HeapSort(vector<int>& a)
{
for(int i=a.size()/2-1;i>=0;i--)
MaxHeapify(a,i,a.size()-1);
for(int i=a.size()-1;i>0;i--)
{
swap(a[0],a[i]);
MaxHeapify(a,0,i-1);
}
}
vector<int> MySort(vector<int>& arr) {
HeapSort(arr);
return arr;
}
};
好有价值！
