术语解释

  1. 稳定排序：如果a原本在b的前面，且a==b，排序后a仍然在b前面，则为稳定排序
  2. 非稳定排序：如果a原本在b的前面，且a==b，排序后a可能不再b的前面，则为非稳定排序
  3. 原地排序：原地排序就是指在排序过程中不申请多余的存储空间，只利用原来存储待排数据的存储空间进行比较和交换的数据排序
  4. 非原地排序：需要用额外的数组来辅助排序
  5. 时间复杂度：一个算法执行所消耗的时间
  6. 空间复杂度：运行完一个算法所需的内存大小

十大排序

  • 选择排序
  • 插入排序
  • 冒泡排序
    • 非优化版本
    • 优化版本
  • 希尔排序
  • 归并排序
    • 递归式归并排序
    • 非递归式归并排序
  • 快速排序
  • 堆排序
  • 基数排序
    • 非优化版本
    • 优化版本
  • 桶排序
  • 基数排序

1.选择排序

遍历一遍数组，把最小的元素放在前面。 选择排序
性质：

  1. 时间复杂度：O(n^2)
  2. 空间复杂度：O(1)
  3. 非稳定排序
  4. 原地排序
void select(long a[],int n){
    for(int i=1;i<n;i++){
        for(int j=i+1;j<=n;j++){
            if(a[j]<a[i]){
                int temp=a[i];
                a[i]=a[j];
                a[j]=temp;
            }
        }
    }
}

2.插入排序

1、采用双层循环：时间复杂度也是O（n的平方）
（1）外层循环表示的是排序的趟数，n个数字需要n-1趟，因此，外层循环的次数是n-1次；同时也代表数的位置。
（2）内层循环表示的是每一趟排序的数字。根据插入排序的思想，第i趟排序时，有序数组中的数字就有i个，就需要进行i次比较，因此循环i次。注意采用的是从后往前进行比较。
2、从后往前扫描的时候，如果必须插入的数大于有序数组中当前位置的数，则有序数组中的数和它之后的数均往后移一个位置，否则，把插入的数插入到有序数组中。（稳定排序）

性质：

  1. 时间复杂度：O(n^2)
  2. 空间复杂度：O(1)
  3. 稳定排序
  4. 原地排序
void insert(){
    int n,x,i,k=0;
    cin>>n;
    
    for(i=0;i<n;i++){
        cin>>x;
        for(k=i;k>0;k--){
            if(x<a[k-1]){
                a[k]=a[k-1];
            }else{
                break;
            }
        }
        a[k]=x;
    }
}

3.冒泡排序

两两比较前面的比后面的大则交换。假如从开始的第一对到结尾的最后一对，相邻的元素之间都没有发生交换的操作，这意味着右边的元素总是大于等于左边的元素，此时的数组已经是有序的了，我们无需再对剩余的元素重复比较下去了。
性质：

  1. 时间复杂度：O(n^2)
  2. 空间复杂度：O(1)
  3. 稳定排序
  4. 原地排序
void bubble(int a[],n){
    for(int i=0;i<n;i++){
        int flag=1;        //判断是否进行了排序 
        for(int j=0;j<n-i-1;j++){
            if(a[j]>a[j+1]){
                flag=0;
                int temp=a[j+1];
                a[j+1]=a[j];
                a[j]=temp;
            }
        }
        if(flag){    //如果没有进行排序直接退出 
            break;
        }
    }
}

4.希尔排序（插入排序的变种）

假如有10（也就是n）个数，第一次n/2=h=5，把数组0和5、1和6等等进行比较，如果a[0]大于a[5],则进行交换，每次把h/2，当h=1时就相当于插入排序了，h=0退出。
需要注意的是，对各个分组进行插入的时候并不是先对一个组排序完了再来对另一个组排序，而是轮流对每个组进行排序。
性质：

  1. 时间复杂度：O
  2. 空间复杂度：O(1)
  3. 非稳定排序
  4. 原地排序
void xier(int a[],n){
    int i,j,gap;

    // gap为步长，每次减为原来的一半。
    for (gap = n / 2; gap > 0; gap /= 2){
        
        // 共gap个组，对每一组都执行直接插入排序
        for (i = 0 ;i < gap; i++){
            for (j = i + gap; j < n; j += gap) {
                
                // 如果a[j] < a[j-gap]，则寻找a[j]位置，并将后面数据的位置都后移。
                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;
                }
            }
        }

    }
}

5.归并排序

把无序的数组每两个放一起进行排序，然后四个进行排序，直到n/2个进行排序。
性质：

  1. 时间复杂度：O
  2. 空间复杂度：O（n）
  3. 稳定排序
  4. 非原地排序
递归代码
#include<bits/stdc++.h>
using namespace std;
int a[100010];
void merge(int a[],int L,int mid,int R){    //总是把l看成1，就大写了 
    int b[R-L+1];    //开辟一个新的数组
    for(int i=L;i<=R;i++){
        b[i-L]=a[i];
    } 
    int q=L,w=mid+1;
    for(int i=L;i<=R;i++){
        if(q>mid){
            a[i]=b[w-L];
            w++;
        }else if(w>R){
            a[i]=b[q-L];
            q++;
        }else if(b[q-L]<b[w-L]){
            a[i]=b[q-L];
            q++;
        }else{
            a[i]=b[w-L];
            w++;
        }
    }
    
}
void merge_sort(int a[],int L,int R){
    if(L>=R){
        return ;
    }
    int mid=(L+R)/2;
    merge_sort(a,L,mid);
    merge_sort(a,mid+1,R);
    merge(a,L,mid,R);
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++){
        cin>>a[i];
    }
    merge_sort(a,0,n-1);
    
    cout<<a[0];
    for(int i=1;i<n;i++){
        cout<<" "<<a[i];
    }
    return 0;
}