C++实现常见的排序算法
这篇博客主要是对常见的排序算法做一总结如下：
快速排序
平均时间复杂度为：O(nlogn)；空间复杂度为O(nlogn)。不稳定排序。n大的时候，性能更加优越。
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
//划分的过程，因为快排是分治思想的，所以需要划分。
int partition(vector<int> & vec,int start,int end){
int point=vec[start];
int i=start;
int j=end;
while(i<j){
while(i<j && vec[j]>=point) j--;
vec[i]=vec[j];
while(i<j && vec[i]<point) i++;
vec[j]=vec[i];
}
vec[i]=point;
return i;
}
//快排的结构
void quick_sort(vector<int> &vec,int start,int end){
if(start>end) return;
int j=partition(vec,start,end);
quick_sort(vec,start,j-1);
quick_sort(vec,j+1,end);
}
int main(){
int n;
scanf("%d",&n);
vector<int > vec;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
vec.push_back(x);
}
quick_sort(vec,0,n-1);
for(int i=0;i<n;i++){
printf("%d ",vec[i]);
}
return 0;
}
冒泡排序
**平均时间复杂度为：O(n^2)；空间复杂度为O(1)。**稳定排序。
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;
void bubble_sort(vector<int> &vec){
int size=vec.size();
for(int i=0;i<size-1;i++){//这一轮循环是要比较的元素，也就睡还没有排好序的元素，最初有n个，但是其实只要比较n-1个元素就可以，因为最后一个元素不用比较。
for(int j=0;j<size-i-1;j++){
if(vec[j]>vec[j+1]) swap(vec[j],vec[j+1]);
}
}
}
int main(){
int n;
scanf("%d",&n);
vector<int > vec;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
vec.push_back(x);
}
bubble_sort(vec);
for(int i=0;i<n;i++){
cout<<vec[i]<<" ";
}
return 0;
}
归并排序
平均时间复杂度为：O(nlogn)；空间复杂度为O(nlogn)。稳定排序。n大的时候，性能更加优越。
#include<stdio.h>
#include<string.h>
#include<math.h>
#include<vector>
using namespace std;
void merge(vector<int> & vec,int low,int mid,int high){
vector<int> temp(high-low+1,0);
int left_low=low;
int left_high=mid;
int right_low=mid+1;
int right_high=high;
int i=0;
for(i=0;left_low<=left_high && right_low<=right_high;i++){
if(vec[left_low]<=vec[right_low]){
temp[i]=vec[left_low];
left_low++;
}
else{
temp[i]=vec[right_low];
right_low++;
}
}
if(left_low<=left_high){
while(left_low<=left_high){
temp[i]=vec[left_low];
i++;
left_low++;
}
}
if(right_low<=right_high){
while(right_low<=right_high){
temp[i]=vec[right_low];
i++;
right_low++;
}
}
for(int j=0;j<(high-low+1);j++){
vec[low+j]=temp[j];
}
return ;
}
void merge_sort(vector<int> &vec,int start,int end){
if(start>=end) return;
int mid=start+(end-start)/2;
merge_sort(vec,start,mid);
merge_sort(vec,mid+1,end);
merge(vec,start,mid,end);
return;
}
int main(){
int n;
scanf("%d",&n);
vector<int > vec;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
vec.push_back(x);
}
merge_sort(vec,0,n-1);
for(int i=0;i<n;i++){
printf("%d ",vec[i]);
}
return 0;
}
堆排序
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
//要建成最小堆，首先是要建成最大堆，然后调整为最小堆！
//调整成最大堆
void adjust_heap(vector<int> &vec,int size,int index){
int left=2*index+1;
int right=2*index+2;
int max_index=index;
if(left<size && vec[left]>vec[max_index]) max_index=left;
if(right<size && vec[right]>vec[max_index]) max_index=right;
if(max_index!=index){
swap(vec[max_index],vec[index]);
adjust_heap(vec,size,max_index);
}
}
void heap_sort(vector<int> &vec,int size){
//建立堆
for(int i=size/2-1;i>=0;i--){
adjust_heap(vec,size,i);
}
//调整为最小堆
for(int i=size-1;i>=1;i--){
swap(vec[0],vec[i]);
adjust_heap(vec,i,0);
}
}
int main(){
int n;
scanf("%d",&n);
vector<int > vec;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
vec.push_back(x);
}
heap_sort(vec,vec.size());
for(int i=0;i<n;i++){
printf("%d ",vec[i]);
}
return 0;
}
计数排序
平均时间复杂度为：O(n+k)；空间复杂度为O(n+k)。稳定排序，其中，k表示序列中最大值。所以，计数排序使用与最大值不是很大的序列。
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
void count_sort(vector<int> & vec){
if(vec.size()==0) return ;
int maxvalue=0,minvalue=0;
for(int i=0;i<vec.size();i++){
maxvalue=max(maxvalue,vec[i]);
minvalue=min(minvalue,vec[i]);
}
int range=maxvalue-minvalue+1;
vector<int> temp(range,0);
for(int i=0;i<vec.size();i++){
temp[vec[i]-minvalue]+=1;
}
int j=0;
for(int i=0;i<range;i++){
while(temp[i]!=0){
vec[j]=i+minvalue;
temp[i]--;
j++;
}
}
}
int main(){
int n;
scanf("%d",&n);
vector<int > vec;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
vec.push_back(x);
}
count_sort(vec);
for(int i=0;i<n;i++){
printf("%d ",vec[i]);
}
return 0;
}
选择排序
平均时间复杂度为：O(n^2)；空间复杂度为O(1)。**不稳定排序。
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
//选择排序与冒泡排序非常的类似，选择排序是选择一个最小的放在序列前面，而冒泡排序是选择一个最大的元素放在序列后面。
void select_sort(vector<int> &vec){
int i=0;
for(i=0;i<vec.size()-1;i++){//同样，只用比较n-1个元素
for(int j=i+1;j<vec.size();j++){
if(vec[j]<vec[i]) swap(vec[j],vec[i]);
}
}
}
int main(){
int n;
scanf("%d",&n);
vector<int > vec;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
vec.push_back(x);
}
select_sort(vec);
for(int i=0;i<n;i++){
printf("%d ",vec[i]);
}
return 0;
}
插入排序
平均时间复杂度为：O(n^2)；空间复杂度为O(1)。**稳定排序。
#include<stdio.h>
#include<string.h>
#include<string>
#include<vector>
#include<algorithm>
using namespace std;
void insert_sort(vector<int> &vec){
if(vec.size()==0) return;
for(int i=1;i<vec.size();i++){
int temp=vec[i];
int j=i;
while(j>0 && temp<vec[j-1]){
vec[j]=vec[j-1];
j--;
}
vec[j]=temp;
}
}
int main(){
int n;
scanf("%d",&n);
vector<int > vec;
for(int i=0;i<n;i++){
int x;
scanf("%d",&x);
vec.push_back(x);
}
insert_sort(vec);
for(int i=0;i<n;i++){
printf("%d ",vec[i]);
}
return 0;
}
各大算法时间与空间复杂度对比
