文章包括:冒泡/地精/奇偶/梳子/快速/选择/锦标赛/堆/插入/希尔/耐心/归并排序,使用C++编写
Exchange sorts
冒泡排序 (Bubble sort)
稳定性:稳定
时间复杂度:O(n2)
void mysort(int* a,int n){
for(int i=n-1;i>0;i--){
for(int j=0;j<i;j++){
if(a[j]>a[j+1])swap(a[j],a[j+1]);
}
}
}
地精排序 (Gnome sort)
稳定性:稳定
时间复杂度:O(n2)
void mysort(int* a,int n) {
int i=0;
while(i<n-1){
//找到第一个逆序的元素
if(i==-1 || a[i]<=a[i+1])i++;
//放到前面合适的位置
else {swap(a[i],a[i+1]);i--;}
}
}
奇偶排序 (Odd-Even sort)
稳定性:稳定
时间复杂度:O (n2)
void mysort(int* a,int n) {
bool sorted = false;
while(!sorted){
sorted = true;
for(int i=0;i<n-1;i+=2){
if(a[i]>a[i+1]){sorted=false;swap(a[i],a[i+1]);}
}
for(int i=1;i<n-1;i+=2){
if(a[i]>a[i+1]){sorted=false;swap(a[i],a[i+1]);}
}
}
}
举例:
- 3 4 -1 0 9 6 5
- 3 4 -1 0 6 9 5
- 3 -1 4 0 6 5 9
- -1 3 0 4 5 6 9
- -1 0 3 4 5 6 9
梳子排序 (Comb sort)
稳定性:不稳定
时间复杂度:O (nlogn)
void mysort(int* a,int n) {
int gap = n;
bool swapped = true;
while(gap>1 || swapped){
swapped = false;
gap = gap>1?(gap/1.25):gap;
for(int i=0;i+gap<n;i++){
if(a[i]>a[i+gap]){swap(a[i],a[i+gap]);swapped=true;}
}
}
}
快速排序 (Quick sort)
稳定性:不稳定
平均时间复杂度:O(nlogn)
最差时间复杂度:O(n2)
void qksort(int* a,int n)
{
int i=0,j=n-1;
const int s = (a[0]+a[n-1])/2;
while(i<=j)
{
while(a[i]<s)i++;
while(a[j]>s)j--;
if(i<=j)swap(a[i++],a[j--]);
}
if(j>0)qksort(a,j+1);
if(i<n-1)qksort(&a[i],n-i);
}
Selection sorts
选择排序 (Selection sort)
稳定性:不稳定
时间复杂度:O(n2)
void mysort(int* a,int n)
{
for(int i=0;i<n-1;i++){
int min = i;
for(int j=i+1;j<=n-1;j++){
if(a[j]<a[min])min=j;
}
swap(a[i],a[min]);
}
}
锦标赛排序 (Tournament sort)
稳定性:不稳定
时间复杂度:O(nlogn)
#define INF 2147483647;
int n;int* tmp;
//返回较小数的索引
int winner(int i,int j){
int u = i >= n ? i : tmp[i];
int v = j >= n ? j : tmp[j];
return tmp[u] <= tmp[v] ? u : v;
}
//右侧存初始数据,左侧存右侧数据的索引
void create_tree(const int* a){
for(int i=0;i<n;i++) tmp[n+i]=a[i];
for(int i=n-1;i>0;i--) tmp[i]= winner(2*i+1,2*i);
}
void recreat(){
int i = tmp[1];
while(i>1){
if(i%2==0) tmp[i/2]=winner(i,i+1);
else tmp[i/2]=winner(i,i-1);
i/=2;
}
}
void mysort(int* a,int num)
{
if(num<=1)return;
n = num;
tmp = new int[2*n];
create_tree(a);
for(int i=0;i<n;i++){
a[i]=tmp[tmp[1]];
tmp[tmp[1]]=INF;
recreat();
}
delete[] tmp;
tmp=NULL;
}
堆排序 (Heap sort)
稳定性:不稳定
时间复杂度:O(nlogn)
//维护,时间复杂度O(logn),i是待维护节点
void heapify(int* tree,int n,int i){
int lson = i * 2 + 1;
int rson = i * 2 + 2;
int max = i;
if(lson < n && tree[max]<tree[lson]) max = lson;
if(rson < n && tree[max]<tree[rson]) max = rson;
if(max != i){
swap(tree[max],tree[i]);
heapify(tree,n,max);
}
}
void heap_sort(int* arr, int n){
//建堆,时间复杂度O(n)
for(int i = n/2-1;i>=0;i--){
heapify(arr,n,i);
}
//排序
for(int i=n-1;i>0;i--){
swap(arr[0],arr[i]);
heapify(arr,i,0);
}
}
Insertion sorts
插入排序 (Insertion sort)
稳定性:稳定
时间复杂度:O(n2)
void mysort(int* a,int n){
int i,j;
for(i=1;i<n;i++){
if(a[i]>=a[i-1])continue;
int tmp = a[i];
for(j=i;j>0 && tmp<a[j-1];j--) a[j]=a[j-1];
a[j] = tmp;
}
}
希尔排序 (Shell sort)
稳定性:不稳定
void shell_sort(int* a,int n){
int gap = 1;
while(gap < n/3){
gap = gap * 3 + 1;
}
int i,j;
while(gap>=1) {
for (i=gap;i<n;i++) {
if(a[i]>=a[i-gap])continue;
int tmp = a[i];
for (j=i;j>=gap && tmp<a[j-gap];j-=gap)a[j]=a[j-gap];
a[j] = tmp;
}
gap = (gap-1)/3;
}
}
耐心排序 (Patience sort)
稳定性:稳定
//重载一个运算符以便于拼接数组
vector<int>& operator+=(vector<int> &a1, const vector<int>& a2){
int j(0),k(a1.size());
a1.resize(a1.size()+a2.size());
for(auto i : a2) a1[k+j++]=i;
return a1;
}
//反转数组
void reverse(vector<int> &a){
for(int i=0;i<a.size()-i-1;i++)swap(a[i],a[a.size()-i-1]);
}
void patience_sort(vector<int> &a){
int n = a.size();if(n<2)return;
vector<vector<int>> pile;
//入桶
int pileNum(0);
for(int i=0;i<n;i++) {
int j(0);
for(j=0;j<pileNum;j++)
if(a[i]<pile[j][0]) {pile[j].push_back(a[i]);break;}
if(j==pileNum) {pile.push_back({a[i]});pileNum++;}
}
//出桶
a.clear();
for(auto& i : pile){
reverse(i);
patience_sort(i);
a+=i;
}
}
Merge sorts
 
归并排序 (Merge sort)
稳定性:稳定
时间复杂度:O(nlogn)
void mgsort(int* a, int n){
if(n<2)return;
int mid = n/2;
mgsort(a,mid);
mgsort(&a[mid],n-mid);
int i(0),j(mid),k(0); int *tmp = new int[n];
while(i<mid && j<n) tmp[k++] = (a[i]<=a[j]) ? a[i++] : a[j++];
j = k-1;
while(i<mid) a[k++] = a[i++];
for(;j>=0;j--) a[j]=tmp[j];
delete[] tmp; tmp = NULL;
}