排序汇总

冒泡排序

稳定排序，时间复杂度O(n2)

排序算法-冒泡排序 - 武培轩 - 博客园 (cnblogs.com)

冒泡 
1
2
3
4
5
6
7
8
9
10
//Bubble_sort(冒泡排序)
void Bubble_sort(int ori[], int s, int e) {
	for (int i = 0 ; i < e - s ; i++) { //一共总次数-1 =（e-s+1)-1 = e-s次
		for (int j = s ; j < e - i ; j ++) {
			if (ori[j] > ori[j + 1]) {
                swap(ori[j],ori[j+1]);
			}
		}
	}
}

C++：

1
2
3
4
5
6
7
8
9
10
void bubbleSort(vector<int > & v){
	int n = v.size();
	for(int i = 0 ; i < n ; i ++){
		for(int j = 0 ; j < i ; j ++){
			if(v[j] > v[j+1]){
				swap(v[j], v[j+1]);
			}
		}
	}
}

选择排序

稳定排序，时间复杂度O(n2)

排序算法-选择排序 - 武培轩 - 博客园 (cnblogs.com)

选择 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
//Selection_sort(选择排序)
void Selection_sort(int ori[], int s, int e) {
	for (int i = s ; i < e ; i ++) {
		int min_ = ori[i]; //每次都找到[i,e]内的最小值ori[f]
		int f = i;
		for (int j = i + 1; j <= e ; j ++) {
			if (ori[j] < min_) {
				min_ = ori[j];
				f = j;
			}
		}
		swap(ori[f],ori[i]);//交换ori[f]和ori[i]
	}
}

C++：

1
2
3
4
5
6
7
8
9
10
11
12
void selectSort(vector<int > & v){
	int n = v.size();
	for(int i = 0 ; i < n ; i ++){
		int f = i;
		for(int j = i+1 ; j < n ; j ++){
			if(v[j] < v[f]){
				f = j;
			}
		}
		swap(v[f], v[i]);
	}
}

插入排序

不稳定排序，最佳n(已经排好序)，最差n2（完全相反）

排序算法-插入排序 - 武培轩 - 博客园 (cnblogs.com)

插入 
1
2
3
4
5
6
7
8
9
10
11
12
//Insert_sort插入排序（扑克牌排序）
void Insert_sort(int ori[], int s, int e) {
	for (int i = s + 1 ; i <= e; i ++) {
		int val = ori[i];
		int j = i - 1;
		while(j >= s && ori[j] >= val) {
			ori[j + 1] = ori[j]; //数组往后退
            j--;
		}
		ori[j + 1] = val; //插入
	}
}

C++：

1
2
3
4
5
6
7
8
9
10
11
12
void insertSort(vector<int > & v){
	int n = v.size();
	for(int i = 1 ; i < n ; i ++){
		int t = v[i];
		int j = i-1;
		while(j >= 0 && v[j] > t){
			v[j+1] = v[j];
			j--;
		}
		v[j+1] = t;
	}
}

归并排序

较为稳定，复杂度与原始数据无关；时间复杂度：O(n*log n)

缺点是要申请一个等大的数组tmp；

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
void merge(int ori[], int s, int e, int tmp[]) {
	int m = s + (e - s) / 2;
	int pt = 0;
	int p1 = s, p2 = m + 1;

	while (p1 <= m && p2 <= e) { //把已经排好序的数组，合并
		if (ori[p1] < ori[p2]) tmp[pt++] = ori[p1++];
		else tmp[pt++] = ori[p2++];
	}
	while (p1 <= m) tmp[pt++] = ori[p1++];
	while (p2 <= e) tmp[pt++] = ori[p2++];

	for (int i = 0 ; i < pt ; i ++)
		ori[s + i] = tmp[i];
}

void merge_sort(int ori[], int s, int e, int tmp[]) {
	int m = s + (e - s) / 2;
	if (e > s) { //终止条件
		merge_sort(ori, s, m, tmp); //切成两半，分别排序；
		merge_sort(ori, m + 1, e, tmp);
		merge(ori, s, e, tmp); //合并排序好的两半
	} else return;
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
void merge(vector<int > & v, vector<int > & tep, int s, int e){
	if(s >= e) return;
	int mid = (s+e)/2;
	int i = s;
	int j = mid+1;
	int k = 0;
	while(i <= mid && j <= e){
		if(v[i] < v[j]) tep[k++] = v[i++];
		else tep[k++] = v[j++];
	}
	while(i <= mid) tep[k++] = v[i++];
	while(j <= e) tep[k++] = v[j++];
	
	int p = s;
	for(int i = 0 ; i < k ; i ++){
		v[p++] = tep[i];
	}
}

void mergeSort(vector<int > & v, vector<int > & tep,int s, int e){
	if(s >= e) return;
	int mid = (s+e)/2;
	mergeSort(v, tep, s, mid);
	mergeSort(v, tep, mid+1, e);
	merge(v, tep, s, e);
}

快速排序

时间复杂度取决于原数组的有序程度，完全有序时恶化到\(n^2\)

最好是\(O(nlogn)\)，最差是\(O(n^2)\)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void quick_sort(int ori[],int s,int e)
{
	if(s >= e) return;
	int k = ori[s];
	int i = s;
	int j = e;
	while(i != j)
	{
		while(i < j && ori[j] >= k) j--;
		swap(ori[i],ori[j]);
		while(i < j && ori[i] <= k) i++;
        swap(ori[i],ori[j]);
	}
	quick_sort(ori,s,i-1);
	quick_sort(ori,i+1,e);
}

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void quickSort(vector<int > & v, int s, int e){
	if(s >= e) return;
	int k = v[s];
	int i = s;
	int j = e;
	while(i != j){
		while(j > i && v[j] >= k) j--;
		swap(v[j], v[i]);
		while(i < j && v[i] <= k) i++;
		swap(v[i], v[j]);
	}
	quickSort(v, s, i-1);
	quickSort(v, i+1, e);
}

堆排序

图解排序算法(三)之堆排序 - dreamcatcher-cx - 博客园 (cnblogs.com)

模板题：P3378 【模板】堆 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

堆的定义：一棵完全二叉树，每个节点的值总是 >= 或 <= 其父节点的值

堆排序的时间复杂度：\(O(nlogn)\)

img img

大顶堆：\(arr[i] >= arr[2i+1]\) && \(arr[i] >= arr[2i+2]\)

小顶堆：\(arr[i] <= arr[2i+1]\) && \(arr[i] <= arr[2i+2]\)

堆排序的基本思路：

1.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;

2.将堆顶元素与末尾元素交换，将最大元素"沉"到数组末端;

3.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。

手写堆

以小根堆为例：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
//从某点（坐标）向下调整
void justDown(int p){
	int now = p;
	while(now <= siz){
		int t = now;
		if(2*now <= siz && heap[2*now] < heap[t]) t = 2*now;
		if(2*now+1 <= siz && heap[2*now+1] < heap[t]) t = 2*now+1;
		if(t != now){
			swap(heap[t], heap[now]);
			now = t;
		}else break;
	}
}

//从某点（坐标）向上调整
void justUp(int p){
	int now = p;
	while(now >= 1){
		int f = now/2;
		if(f >= 1 && heap[f] >= heap[now]){
			swap(heap[now], heap[f]);
			now = f;
		}else break;
	}
}

//直接建堆
//读入无序数组
//从n/2(最后一个非根节点)开始，逐个向上调整
void create(int n){
	siz = n;
	for(int i = 1 ; i <= n ; i ++){
		cin>>heap[i];
	}
	for(int i = n/2 ; i >= 1 ; i --){
		justDown(i);
	}
}

//插入操作
//插入一个元素到堆末，从新位置向上调整
void push(int x){
	heap[++siz] = x;
	justUp(siz);
}

//得到最小值，即heap[1]
int top(){
	if(siz >= 1) return heap[1];
	else return -1;
}

//删除最小值
//删除后需要将heap[1]置换为堆末元素，并向下调整
void pop(){
	if(siz){
		heap[1] = heap[siz--];
		justDown(1);
	}
}

STL：priority_queue

一般情况下用STL的pq就可以实现堆

缺点：只能删除堆顶元素

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
priority_queue<int> pq; //默认大根堆
priority_queue <int,vector<int>,less<int> > pq; //大根堆
priority_queue<int, vector<int>, greater<int> > pq; //小根堆;

q.top()//取得堆顶元素，并不会弹出
q.pop()//弹出堆顶元素
q.push()//往堆里面插入一个元素
q.empty()//查询堆是否为空，为空则返回1否则返回0
q.size()//查询堆内元素数量

//存储结构体
struct point{    
    int x,y;    
    int times;    
    friend bool operator < (point a, point b){    
        return a.times > b.times;    //重载小于号使得小的先出队列    
    }
}priority_queue<point> q;

判断堆

1147 Heaps - PAT (Advanced Level) Practice (pintia.cn)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int judge(){
    // 1 - 大根堆，2 - 小根堆，3 - 非堆
	bool ma,mi;
	ma = mi = true;
	for(int i = 0 ; i < n ; i ++){
		int l = i*2 + 1;
		int r = i*2 + 2;
		if((l < n && layer[l] > layer[i]) || (r < n && layer[r] > layer[i])){
			ma = false;
			break;
		}
	}
	if(ma) return 1;
	for(int i = 0 ; i < n ; i ++){
		int l = i*2 + 1;
		int r = i*2 + 2;
		if((l < n && layer[l] < layer[i]) || (r < n && layer[r] < layer[i])){
			mi = false;
			break;
		}
	}
	if(mi) return 2;
	return 3;
}
笔记 > 模拟
#排序
排序汇总
https://czwcugb.github.io/算法/未分类/排序汇总/
作者
ChenZhiwei
发布于
2025年1月13日
许可协议