一、冒泡排序
O
(
n
2
)
O(n^2)
O
(
n
2
)
#include<iostream>
using namespace std;
const int N = 100010;
int n;
int nums[N];
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> nums[i];
for(int i = 0; i < n - 1; i++)
for(int j = i + 1; j < n; j++)
if(nums[i] > nums[j]) swap(nums[i], nums[j]);
for(int i = 0; i < n; i++) cout << nums[i] << ' ';
return 0;
}
二、快速排序
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
#include<iostream>
using namespace std;
const int N = 100010;
int n;
int nums[N];
void quick_sort(int l,int r){
if(l >= r) return;
int x = nums[(l+r) / 2],i = l-1,j = r+1;
while(i < j){
do i++; while(nums[i] < x);
do j--; while(nums[j] > x);
if(i < j) swap(nums[i], nums[j]);
}
quick_sort(l,j);
quick_sort(j+1,r);
}
int main(){
cin >> n;
for(int i = 0; i< n; i++) cin >> nums[i];
quick_sort(0,n-1);
for(int i = 0; i< n; i++) cout << nums[i] << ' ';
return 0;
}
三、归并排序
O
(
n
l
o
g
n
)
O(nlogn)
O
(
n
l
o
g
n
)
#include<iostream>
using namespace std;
const int N = 100010;
int n;
int q[N],tmp[N];
void merge_sort(int q[],int l,int r){
if(l >= r) return;
int mid = (l+r) >> 1;
merge_sort(q,l,mid),merge_sort(q,mid+1,r);
int k = 0,i = l,j = mid+1;
while(i <= mid && j <= r){
if(q[i] <= q[j]) tmp[k++] = q[i++];
else tmp[k++] = q[j++];
}
while(i <= mid) tmp[k++] = q[i++];
while(j <= r) tmp[k++] = q[j++];
for(i = l,j = 0; i <= r; i++,j++) q[i] = tmp[j];
}
int main(){
cin >> n;
for(int i = 0; i < n; i++) cin >> q[i];
merge_sort(q,0,n-1);
for(int i = 0; i < n; i++) cout << q[i] << ' ';
return 0;
}
版权声明:本文为qq_40595933原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。