排序算法

基于比较排序时间复杂度下界 $O (N l o g N)$

交换排序

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
冒泡排序	$O(n^2)$	$O(n^2)$	$O (n)$	$O (1)$	稳定
快速排序	$O (n l o g n)$	$O(n^2)$	$O (n l o g n)$	$O (l o g n)$	不稳定

冒泡排序

冒泡排序是一种简单直观的排序，比较相邻两个元素，顺序错误就调换，直至不需要调换
算法步骤
比价相邻的元素，顺序错误就交换
每对相邻元素都做同样的工作，做完以后当前最大就会到最后一位
所有元素都做上述操作，除了最后一个

持续做上面的操作直至没有需要交换的

#include<iostream>
#include<vector>
using namespace std;

void Bubble_sort(vector<int>& a) {
    for (int i = a.size() - 1; i > 0; i -- ){
    	bool flag = false;	
		for(int j = 0; j + 1 <= i; j ++ )
			if(a[j] > a[j + 1]){
				swap(a[j], a[j + 1]);
				flag = true;
			}
		if(!flag) break;
	}
}

int main(){
	
	int n;
	cin >> n;
	vector<int> a;
	for(int i = 0; i < n; i ++ ) {
		int x;
		cin >> x;
		a.push_back(x);
	}
	
	Bubble_sort(a);
	
	
	for(auto x : a) cout << x << " ";
	
	return 0;
}

快排

快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看，快速排序应该算是在冒泡排序基础上的递归分治法。

快速排序的最坏运行情况是 O(n2)，比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn)，且 O(nlogn) 记号中隐含的常数因子很小，比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以，对绝大多数顺序性较弱的随机数列而言，快速排序总是优于归并排序。

算法思路
找到分界点x,q[L],q[(L + R) / 2],q[R]
左边所有书Left ≤ x,右边所有数Right ≥ x
递归排序Left,递归排序Right

void quick_sort(int q[],int l,int r){
    if(l>=r) return;
    int i = l - 1,j = r + 1,x = q[l + r >> 1];
    
    while(i<j){ // 如果左指针一直在右指针左边或者一起的时候
        do i++;while(q[i] < x); // 如果左指针指的数小于参照的话，右移左指针
        do j--;while(q[j] > x); // 如果右指针指的数大于参照的话，左移右指针
        if(i<j) swap(q[i],q[j]); // 找到了两边位置都不对的，并且左指针在右指针左边，交换
    }

    quick_sort(q,l,j);
    quick_sort(q,j+1,r);
    //递归把两段排好序
}

插入排序

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
简单插入排序	$O(n^2)$	$O (n)$	$O(n^2)$	$O (1)$	稳定
希尔排序	$O (n l o g n)$	$O(nlog^2n)$	$O(nlog^2n)$	$O (1)$	不稳定

插入排序

原理：通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。（类似于打扑克）

算法步骤：
1.将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2.从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

#include<iostream>
#include<vector>
using namespace std;

void insert_sort(vector<int> &a){
 for(int i = 1; i < a.size(); i ++ ){
 	int tmp = a[i];
 	
 	int j = i;
 	while(j > 0 && tmp < a[j - 1]){
 		a[j] = a[j - 1];
 		j --;
 	}
 	
 	if(j != i) a[j] = tmp;
 }
}

int main(){
 int n;
 cin >> n;
 vector<int> a;
 for(int i = 0; i < n; i ++ ){
 	int x;
 	cin >> x;
 	a.push_back(x);	
 } 
 
 insert_sort(a);
 
 for(auto x : a) cout << x << " ";
 return 0;
}

希尔排序

也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法
希尔排序是基于插入排序的两点性质改进的
① ：插入排序对于基本有序的数据操作时，更高效
② ：但是一般来说插入排序是低效的，因为插入排序每次只能将数据移动一位
基本思路：先将整个数组分割成若干子序列，待整个序列中的记录基本有序时，再对全体记录进行依次插入
算法步骤：

分成若干序列
2.组内排序，序列长度减半
3.直到序列长度为1

#include<iostream>
#include<vector>
using namespace std;

void xier_sort(vector<int> &a){
 int gap = 1;
 while(gap < a.size()/ 2 ) gap = gap * 2;
 
 while(gap > 0){
 	for(int i = gap; i < (a.size()); i ++ ){
 		int tmp = a[i];
 		int j = i - gap;
 		while(j >= 0 && a[j] > tmp){
 			a[j + gap] = a[j];
 			j -= gap;
 		}
 		a[j + gap] = tmp;
 	}
 	gap = gap / 2;
 }
}

int main(){
 int n;
 cin >> n;
 vector<int> a;
 for(int i = 0; i < n; i ++ ){
 	int x;
 	cin >> x;
 	a.push_back(x);	
 } 
 
 xier_sort(a);
 
 for(auto x : a) cout << x << " ";
 
 return 0;
}

选择排序

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
简单选择排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	不稳定
堆排序	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$	$O (1)$	不稳定

选择排序

选择排序无论什么数据进去都是 $O(n^2)$ 的时间复杂度，所以数据规模越小越好，好处是不用额外内存
算法步骤：
遍历找到最小的放到起始位置
在剩余未排序元素中继续找出最小袁旭，放到已排序序列的后面

重复第二步，直至排序完毕

#include<iostream>
#include<vector>
using namespace std;

void select_sort(vector<int>& a) {
    for (int i = 0; i < a.size(); i++) 
        for (int j = i + 1; j < a.size(); j++)
            if (a[i] > a[j])
            	swap(a[i], a[j]);
}

int main(){
	int n;
	cin >> n;
	vector<int> a;
	for(int i = 0; i < n; i ++ ) {
		int x;
		cin >> x;
		a.push_back(x);
	}
	
	select_sort(a);
	
	
	for(auto x : a) cout << x << " ";
	
	return 0;
}

堆排序

堆排序近似完全二叉树
- 大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
- 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
算法思路：
按大根堆或小根堆构建
2.把堆首（最大值）和堆尾互换
3.size -1，down(1);
重复

/* 
堆的功能

1. 插入一个数        heap[++size] = x;up(size);
2.求集合当中的最小值 heap[1]
3.删除最小值		 用最后一个元素覆盖第一个  然后再down一下 
					 heap[1] = heap[size]; size --; down(1);
  删除尾结点         size--； 
4.删除任意一个元素   heap[k] = heap[size]; siez --; down(k); up(k);
5. 修改任意一个元素  heap[k] = x;  down(k); up(k);

小根堆 每一个点都 <= 左右儿子
堆的存储 用一个一维数组：根节点是 x, x的左儿子是 2x, x的右儿子是2x+1 

堆的基本操作 down(x), up(x)
*/ 

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010;

int n, m;
int h[N], cnt;

void down(int u){
    int t = u;
    if (u * 2 <= cnt && h[u * 2] < h[t]) t = u * 2;
    if (u * 2 + 1 <= cnt && h[u * 2 + 1] < h[t]) t = u * 2 + 1;
    if (u != t)
    {
        swap(h[u], h[t]);
        down(t);
    }
}

int main(){
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ ) scanf("%d", &h[i]);
    cnt = n;

    for (int i = n / 2; i; i -- ) down(i);

    while (m -- ){
        printf("%d ", h[1]);
        h[1] = h[cnt -- ];
        down(1);
    }

    puts("");

    return 0;
}

归并排序（分治）

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
二路归并	$O (n l o g n)$	$O (n l o g n)$	$O (n l o g n)$	$O (n)$	稳定

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法的一个非常典型的应用
算法步骤：
找到分界点

递归排序左右两边
3.归并，合二为一

// 归并排序
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++]; // 比大小放进tmp
       else tmp[k++] = q[j++];
   while(i <= mid) tmp[k++] = q[i++]; 
   // 判断哪段没完事，接到tmp后面去
   while(j <= r) tmp[k++] = q[j++];
   
   for(i = l,j = 0;i<=r;i++,j++) q[i] = tmp[j]; // 放回q中
   
}

排序方法	时间复杂度（平均）	时间复杂度（最坏）	时间复杂度（最好）	空间复杂度	稳定性
计数排序	$O (n + k)$	$O (n + k)$	$O (n + k)$	$O (k)$	稳定
桶排序	$O (n + k)$	$O(n^2)$	$O (n + k)$	$O (n + k)$	稳定
基数排序	$O (n ? k)$	$O (n ? k)$	$O (n ? k)$	$O (n + k)$	稳定

计数排序
a. 计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
① 在额外空间充足的情况下，尽量增大桶的数量
② 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。