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;
}
各大演算法時間與空間複雜度對比
