冒泡排序

时间复杂度：O(n²)

代码：

#include <iostream> #include <algorithm> #include <cstring> using namespace std; const int N = 1010; void bubble_sort(int a[],int len) //核心代码 { for(int i = 0;i < len - 1;i++) for(int j = 0;j < len - 1 - i;j++) if(a[j] > a[j+1]) swap(a[j],a[j+1]); } int main() { int n; int a[N]; cin >> n; for(int i = 0;i <= n;i++) cin >> a[i]; bubble_sort(a,n); for(int i = 0;i < n;i++) cout << a[i] << ' '; return 0; }

---

快速排序

时间复杂度：O(nlogn)

代码：

#include <iostream> #include <cstdio> typedef long long ll; using namespace std; const int N=1e6+10; int a[N]; int n; void quick_sort(int a[],int l,int r) { if(l >= r) return ; int x = a[(r+l)/2],i = l-1,j = r+1; while(i < j) { do i++; while(a[i] < x); do j--; while(a[j] > x); if(i < j) swap(a[i],a[j]); } quick_sort(a,l,j); quick_sort(a,j+1,r); } int main() { scanf("%d",&n); for(int i=0; i<n; i++) scanf("%d",&a[i]); quick_sort(a,0,n-1); for(int i=0; i<n; i++) printf("%d ",a[i]); return 0; }

---

归并排序

时间复杂度：O（nlogn）

代码：

#include <iostream> #include <cstdio> typedef long long ll; using namespace std; const int N = 1e6+10; int q[N],tmp[N]; int 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 i = l,j = mid + 1,k = 0; 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() { scanf("%d",&n); for(int i=0; i<n; i++) scanf("%d",&q[i]); merge_sort(q,0,n-1); for(int i=0; i<n; i++) printf("%d ",q[i]); return 0; }