$$排序算法$$

排序算法（英语：Sorting algorithm）是一种将一组特定的数据按某种顺序进行排列的算法.

一.快速排序:

时间复杂度为$O(logn)$

快速排序主要思想：

1.确定分界点:一般是 q[l], q[(l + r ) >> 1], q[r]
2.调整区间：对于原来某个数 falg, 使得小于等于 x 的数都在左边， 大于等于 x 的数都在右边
3.递归处理左右两端

代码实现:

const int N = 1e6 + 2;
int n, q[N];

// 快速排序 暴力做法(将小于等于x和大于等于falg的数分放到新数组左右两边中)
int a[N];
void quick_sort_1(int q[], int l, int r){
    if(l >= r) return ;

    int falg = q[l + r >> 1], x = l, y = r;

    for(int i = l; i <= r; i++){
        if(q[i] < falg) a[x ++] = q[i];
        if(q[i] > falg) a[y --] = q[i];
    }

    //现在 a[l, x - 1]都是比 falg 小, a[y + 1, r] 都比 falg 大
    for(int i = l; i < x; i ++) q[i] = a[i];
    for(int i = r; i > y; i --) q[i] = a[i];
    for(int i = x; i <= y; i ++) q[i] = falg;

    //[p,q]是falg不用再排序了
    quick_sort_1(q, l, x - 1);
    quick_sort_1(q, y + 1, r);
}

// 快速排序 优化做法(利用指针i,j使得 i 左边的数字小于等于falg, j 右边的数字大于等于falg)
void quick_sort_2(int q[], int l, int r){
    if(l >= r) return ;

    int falg = q[l + r >> 1], i = l, j = r;
    while(i <= j){
        while(q[i] < falg) i ++; // 一直找到 q[i] >= falg
        while(q[j] > falg) j --; // 一直找到 q[i] <= falg
        if(i <= j)  swap(q[i ++], q[j --]); // 交换完后记得把指针移动
    }

    quick_sort_2(q, l, j);
    quick_sort_2(q, i, r);
} 

二.归并排序:

时间复杂度为$O(logn)$

归并排序主要思想(分治)：

1.确定分界点
2.递归排序l, r
3.归并，合二为一

代码实现:

int tmp[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 k = 0, i = l, j = mid + 1;

    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(int i = l, j = 0; i <= r; i ++, j ++) q[i] = tmp[j];
}

三.其他排序:

(1).选择排序

时间复杂度为$O(n ^ 2)$

// 选择排序:每次将序列最小值放到序列最前面
void selection_sort(int a[], int n){
    for(int i = 0; i < n; i++){
        int k = i;
        for(int j = i + 1; j < n; j++)
            if(a[j] < a[k])
                k = j;
        swap(a[i], a[k]);
    }
}

(2).冒泡排序

时间复杂度为$O(n ^ 2)$

// 冒泡排序:每次将序列最大值放到最后面
void bubble_sort(int a[], int n){
    for(int i = n - 1; i > 0; i --){
        int k = i;
        for(int j = 0; j <= i; j ++)
            if(a[j] > a[k]) 
                k = j;
        swap(a[i], a[k]);
    }
}

(3).插入排序

时间复杂度最优$o(n)$,最坏$o(n^2)$

// 插入排序:像打牌一样，每次把一个新的数放到已排好序的数组种
void insertion_sort(int a[], int n){
    for(int i = 2; i < n; i++){
        int k = a[i];
        int j = i - 1;
        while(j >= 0 && a[j] > k){
            a[j + 1] = a[j];
            j --;
        }
        a[j + 1] = k;
    }
}

(4).桶排序

时间复杂度$o(n)$,但是一般内存占用较大

// 桶排序适用于没有负数下标并且最大数不会超过数组大小的情况。
void Bucket_sort(int a[], int n){
    int vis[N];

    for(int i = 0; i < n; i++)
        vis[a[i]] ++;

    for(int i = 0; i < N; i ++)
        while(vis[i]){
            cout << i << ' ';
            vis[i] -- ;
        }
}