今天，我们来谈谈众多的排序算法特征以及代码实现，让大家饱饱眼福

==========我是 O(n²) 分隔线==========
一、冒泡排序（Bubble Sort）
最基本的排序算法，其原理是依次比较两个数，顺序不对就交换两个数，越大的数就会被“冒”到越后面去。但是，这种算法能让你等到菊花都谢了，被网友疯狂地吐槽……
代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,arr[1000005];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	for(int i=n-1;i>=1;i--){
		for(int j=1;j<=i;j++){
			if(arr[j]>arr[j+1]){
				swap(arr[j],arr[j+1]);
			}
		}
	}
	for(int i=1;i<=n;i++){
		cout<<arr[i]<<" ";
	}
	return 0;
}

二、选择排序（Selection Sort）
选择排序就是每次选一个最小的数，与前面的数交换，越小的数就会排到越前面。这种算法一样能让你等到菊花凋谢
代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,arr[1000005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	for(int i=1;i<n;i++){
		int mi=i;
		for(int j=i+1;j<=n;j++){
			if(arr[j]<arr[mi]){
				mi=j;
			}
		}
		swap(arr[i],arr[mi]);
	}
	for(int i=1;i<=n;i++){
		cout<<arr[i]<<" ";
	}
	return 0;
} 

三、插入排序（Insertion Sort）
这个大概算是O(n²)中比较好的了，一般不会像前两个那样磨叽半天，而且在基本有序的时候它的效率一点也不比那些效率高的排序差。
代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,arr[1000005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
    for(int i=2;i<=n;i++){
        int temp=arr[i];
        int j=i-1;
        while(j>=1&&arr[j]>temp){
            arr[j+1]=arr[j];
            j--;
        }
        arr[j+1]=temp;
    }
    for(int i=1;i<=n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

四、地精排序（Gnome Sort）
地精排序思想简单，只用一个循环，首次被提出是曾被叫做“Stupid Sort”，后来，有人形象地描述了这种排序，因为主角是地精（Gnome），所以名叫：地精排序。这种排序算法思想是：相邻两个数之间，如果顺序对了，就前进一步；如果顺序不对，就后退一步。
代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,arr[1000005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	int i=2;
    while(i<=n){
        if(arr[i-1]<=arr[i]){
            i++;
        }else{
            swap(arr[i],arr[i-1]); 
            i--;
        }
    }
    for(int i=1;i<=n;i++){
    	cout<<arr[i]<<" ";
	}
	return 0;
} 

五、鸡尾酒排序（Cocktail Shaker Sort）
鸡尾酒排序即双向冒泡排序，是冒泡排序的改进版，但是仍不能逃出O(n²)的魔掌……
代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,arr[1000005];
int main(){
	int n;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	int l=1,r=n;
	while(l<=r){
		for(int i=1;i<r;i++){
			if(arr[i]>arr[i+1]){
				swap(arr[i],arr[i+1]);
			}
		}
		r--;
		if(l>r){
			break;
		}
		for(int i=r;i>1;i--){
			if(arr[i]<arr[i-1]){
				swap(arr[i],arr[i-1]);
			}
		}
		l++;
	}
	for(int i=1;i<=n;i++){
		cout<<arr[i]<<" ";
	}
	return 0;
}

==========我是 O(n log n) 分隔线==========
一、快速排序（Quick Sort）
快速排序使用分治法，每次选一个基准数，把小于基准数的数放左边，大于基准数的放右边，递归实现。 代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,arr[1000005];
void QuickSort(int nums[], int start, int end) {
	if (start > end)return; 
	int st = start,ed = end;
	int mid = (start + end) / 2;
	int temp = nums[mid]; 
	if (mid == end)return;
	if (mid == start) {
		if (nums[start] > nums[end])swap(nums[start], nums[end]);
		return;
	}
	while (end > start) {
		while (nums[start] < temp)start++;
		while (end>=start&&nums[end]>=temp)end--; 
		if (end > start) {
			swap(nums[start], nums[end]);
			if (mid == start)mid = end;
		}
		if (end <= start) {
			swap(nums[mid], nums[start]);
			mid = start;
		}
	}
	QuickSort(nums, st, mid - 1);
	QuickSort(nums, mid + 1, ed);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	QuickSort(arr,1,n);
	for(int i=1;i<=n;i++){
		cout<<arr[i]<<" ";
	}
	return 0;
}

二、归并排序（Merge Sort）
归并排序使用分治法，先分成多个最小单元，然后不断合并有序子序列，直到最终合为一体为止，递归实现。
代码实现：

#include<bits/stdc++.h>
using namespace std;
int arr[1000005],n;
void Merge(int a[], int l, int q, int r){
    int n=r-l+1;
    int* tmp=new int[n];
    int i=0;
    int left=l;
    int right=q+1;
    while(left<=q && right<=r)
        tmp[i++] = a[left]<= a[right]?a[left++]:a[right++];
    while(left<=q)
        tmp[i++]=a[left++];
    while(right<=r)
        tmp[i++]=a[right++];
    for(int j=0;j<n;++j)
        a[l+j]=tmp[j];
    delete [] tmp;
}
void MergeSort(int a[], int l, int r){
    if(l==r)
        return;
    int q = (l + r)/2;
    MergeSort(a, l, q);
    MergeSort(a, q + 1, r);
    Merge(a, l, q, r);
}
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
    MergeSort(arr,1,n);
    for(int i=1;i<=n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

三、堆排序（Heap Sort）
选择排序就是每次选出最小数，把它放到前面去。这种算法虽然思维简单，但是效率很低（上面说过）。于是有人想到了：用一种叫堆的数据结构（即父结点永远不小于子结点的二叉树，也叫优先队列）来改进选择排序，结果效率一下子提升了好多倍。
代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,arr[1000005];
void adjust(int arr[], int len, int index){
    int left = 2*index + 1;
    int right = 2*index + 2;
    int maxIdx = index;
    if(left<len && arr[left] > arr[maxIdx]) maxIdx = left;
    if(right<len && arr[right] > arr[maxIdx]) maxIdx = right; 
    if(maxIdx != index){
        swap(arr[maxIdx], arr[index]);
        adjust(arr, len, maxIdx); 
    }
}
void heapSort(int arr[], int size){
    for(int i=size/2 - 1; i >= 0; i--){
        adjust(arr, size, i);
    }
    for(int i = size - 1; i >= 1; i--){
        swap(arr[0], arr[i]); 
        adjust(arr, i, 0); 
    }
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
    heapSort(arr,n);
    for(int i=0;i<n;i++){
        cout<<arr[i]<<" ";
    }
    return 0;
}

四、梳排序（Comb Sort）
梳排序是冒泡排序的改进版，但比上面提到的鸡尾酒排序快了很多。先设定一个变量x为数组长度，然后不断将这个变量缩水到原来的9/10并向下取整，比较arr[i]与arr[i+x]，顺序不对就交换，直到x变为0为止。
代码实现：

#include<bits/stdc++.h>
using namespace std;
int n;
long long arr[1000005];
int main(){
	cin>>n;
	for(long long i=1;i<=n;i++){
		cin>>arr[i];
	}
	int tmp=n*0.9;
	while(tmp>0){
		for(long long i=1;i<=n-tmp;i++){
			if(arr[i]>arr[i+tmp]){
				swap(arr[i],arr[i+tmp]);
			}
		}
		tmp*=0.9;
	}
	for(long long i=1;i<=n;i++){
		cout<<arr[i]<<" ";
	}
	return 0;
}

==========前方高能！！！==========
一、桶排序（Bucket Sort）
超简单超快的排序，把每个数放在对应编号的桶里，在从左到右依次把它们取出来，就是悠着点儿，小心闻到显卡的香味
代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,bucket[100000005],arr[1000005];
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
		bucket[arr[i]]++;
	}
	for(int i=0;i<=1000000;i++){
		for(int j=1;j<=bucket[i];j++){
			cout<<i<<" ";
		}
	}
	return 0;
}

二、计数排序（Counting Sort）
计数排序是将每个数在另一个数组中计数，然后依次递加，可以确定这些数的位置。 代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,arr[1000005];
bool ctsort(int A[],int size){
    if(NULL==A||size<0)
        return false;
    int k = A[0];
    for(int i=1;i<size;i++)
        if(A[i]>k)k=A[i];
    k++;
    int* counts = new int[k];
    int* tmp = new int[size];
    for(int i=0;i<k;i++)
        counts[i]=0;
    for(int i=0;i<size;i++)
        counts[A[i]] = counts[A[i]]+1;
    for(int i=1;i<k;i++)
        counts[i] = counts[i] + counts[i-1];
    for(int i=size-1;i>=0;i--){
        tmp[counts[A[i]]-1] = A[i];
        counts[A[i]] = counts[A[i]] -1;
    }
    memcpy(A,tmp,size*sizeof(int));
    delete[] counts;
    delete[] tmp;
    return true;
}
int main(){
	cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	}
    ctsort(arr,n);
    for(int i=0;i<n;i++)
        cout<<arr[i]<<" ";
}

==========等等，还有我！！！==========
希尔排序（Shell Sort）！！！
即插入排序的改进版。分成若干个子序列，进行插入排序，可有效地提高效率。
代码实现：

#include<bits/stdc++.h>
using namespace std;
int n,arr[1000005];
void print(int a[], int n)
{  
    for(int j= 0; j<n; j++)
	{  
           cout<<a[j] <<" ";  
        }  
    cout<<endl;  
}
 
void shellSort(int a[], int n) 
{
    int i,j,gap;
    for (gap = n / 2; gap > 0; gap /= 2)
    {
        for (i = 0 ;i < gap; i++)
        {
            for (j = i + gap; j < n; j += gap) 
            { 
                if (a[j] < a[j - gap])
                {
                    int tmp = a[j];
                    int k = j - gap;
                    while (k >= 0 && a[k] > tmp)
                    {
                        a[k + gap] = a[k];
                        k -= gap;
                    }
                    a[k + gap] = tmp;
                }
            }
        }
    }
}
 
int main()
{  
    cin>>n;
	for(int i=0;i<n;i++){
		cin>>arr[i];
	} 
    shellSort(arr,n);  
    print(arr,n);  
    return 0;
} 

好了，结束了
本人是个小蒟蒻，说明及大部分代码是自己写的，其他的来自其他网站，希望大家能支持一下小蒟蒻！