- 稳定排序：冒泡排序、归并排序、插入排序
- 不稳定排序：选择排序、希尔排序、快速排序
冒泡排序
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000
int a[MAXN], n;
void BubbleSort(int a[], int n){
//n-1趟排序
for(int i = 1; i < n; i++){
bool ans = false;
for(int j = n; j > i; j--){
//交换相邻位置逆序数，将最小数冒泡到未排序序列的最前方
if(a[j] < a[j-1]){
swap(a[j],a[j-1]);
ans = true;
}
}
//无交换发生，已经有序，直接结束
if(ans == false){
return;
}
}
}
int main()
{
cin >>n;
for(int i = 1; i <= n; i++){
cin >>a[i];
}
BubbleSort(a,n);
for(int i = 1; i <= n; i++){
cout <<a[i] <<" ";
}
return 0;
}
选择排序
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000
int a[MAXN], n;
void SelectSort(int a[], int n){
for(int i = 1; i < n; i++){
//取出未排序序列中的最小数
int minnum = 0x3ff, minn = 0;
for(int j = i; j <= n; j++){
if(a[j] < minnum){
minnum = a[j];
minn = j;
}
}
//将选出的数放到合适位置
swap(a[i],a[minn]);
}
}
int main()
{
cin >>n;
for(int i = 1; i <= n; i++){
cin >>a[i];
}
SelectSort(a,n);
for(int i = 1; i <= n; i++){
cout <<a[i] <<" ";
}
return 0;
}
插入排序
直接插入排序
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000
int a[MAXN], n;
void InsertSort(int a[], int n){
int i, j, temp;
for(i = 2; i <= n; i++){
//寻找未排序的第一个逆序数
if(a[i-1] > a[i]){
//拿出该数
temp = a[i];
//给即将插入的数腾出对应的位置
for(j = i; (j>1) && (a[j-1]>temp); j--){
a[j] = a[j-1];
}
//插入该数
a[j] = temp;
}
}
}
int main()
{
cin >>n;
for(int i = 1; i <= n; i++){
cin >>a[i];
}
InsertSort(a,n);
for(int i = 1; i <= n; i++){
cout <<a[i] <<" ";
}
return 0;
}
折半插入排序
#include<bits/stdc++.h>
using namespace std;
int a[100001], n;
void InsertSort(int a[], int n){
int i, j, l, r, mid;
for(i = 2; i <= n; i++){
a[0] = a[i];
l = 1, r = i-1;
while(l <= r){
mid = (l + r) / 2;
if(a[mid] > a[0]) r = mid - 1;
else l = mid + 1;
}
for(j = i - 1; j >= r+1; j--){
a[j+1] = a[j];
}
a[r+1] = a[0];
}
}
int main(){
cin >>n;
for(int i = 1; i <= n; i++){
cin >>a[i];
}
InsertSort(a,n);
for(int i = 1; i <= n; i++){
cout <<a[i] <<" ";
}
}
希尔排序
#include<bits/stdc++.h>
using namespace std;
#define MAXN 1000
int a[MAXN], n;
void ShellSort(int a[], int n){
int i, j, temp;
//对半式增量
for(int mid = n/2; mid > 0; mid/=2){
//插入排序
for(i = mid; i <= n; i++){
temp = a[i];
for(j = i; j > mid; j -= mid){
if(a[j-mid] > temp){
a[j] = a[j-mid];
}else{
break;
}
}
a[j] = temp;
}
}
}
int main()
{
cin >>n;
for(int i = 1; i <= n; i++){
cin >>a[i];
}
ShellSort(a,n);
for(int i = 1; i <= n; i++){
cout <<a[i] <<" ";
}
return 0;
}
快速排序
- 最优时间复杂度：O(nlogn)
- 最坏时间复杂度：O(n2)
#include<bits/stdc++.h>
using namespace std;
int a[100001], n;
int part(int a[], int low, int high){
int l = low, r = high, pivot = a[l];
while(l < r){
while(l < r && pivot < a[r]) r--;
if(l < r){
swap(a[l],a[r]);
l++;
}
while(l < r && pivot > a[l]) l++;
if(l < r){
swap(a[l],a[r]);
r--;
}
}
//返回基准点所在位置
return l;
}
void QuickSort(int a[], int low, int high){
int mid;
if(low < high){
//将比基准点大的数放到右边，比基准点小的数放到左边，并返回基准点位置
mid = part(a, low, high);
//递归左边
QuickSort(a, low, mid-1);
//递归右边
QuickSort(a, mid+1, high);
}
}
int main(){
cin >>n;
for(int i = 1; i <= n; i++){
cin >>a[i];
}
QuickSort(a,1,n);
for(int i = 1; i <= n; i++){
cout <<a[i] <<" ";
}
}
归并排序
- 时间复杂度：O(nlogn) (
最好=最坏=平均)
#include<bits/stdc++.h>
using namespace std;
int a[100001], n;
void MergeSort(int a[], int l, int r){
int b[100001];
//递归到只有一个元素，直接返回
if(l == r) return;
int mid = (l+r)/2;
MergeSort(a,l,mid);
MergeSort(a,mid+1,r);
//合并序列
int p = l, q = mid + 1;
for(int i = l; i <= r; i++){
if(q > r || (p <= mid && a[p] <= a[q])){
b[i] = a[p++];
}else{
b[i] = a[q++];
}
}
//还原到a数组里
for(int i = l; i <= r; i++) a[i] = b[i];
}
int main(){
cin >>n;
for(int i = 1; i <= n; i++){
cin >>a[i];
}
MergeSort(a,1,n);
for(int i = 1; i <= n; i++){
cout <<a[i] <<" ";
}
}