C++|十大排序算法C++实现

十大排序算法实在是太过于经典了，因此，这篇博客将对十大排序算法进行总结，以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;
}

各大算法时间与空间复杂度对比