经典排序算法

发表于 更新于 分类于

排序算法

常说的十大排序算法为：冒泡、选择、插入、希尔、归并、快速、堆、计数、桶、基数

冒泡排序

冒泡排序的本质在于交换，即每次通过交换的方式把当前剩余元素的最大值移动到一端。而当剩余元素减少为0时，排序结束。这个算法名字的由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

算法步骤

  1. 比较相邻的元素。如果第一个比第二个大，就交换他们两个。
  2. 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
  3. 针对所有的元素重复以上的步骤，除了最后一个。
  4. 持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

动图演示：

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
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n;//元素个数
	int m;//输入元素大小
	cin >> n;
	vector<int> a;//动态数组
	for (int i = 0; i < n; i++)
	{
		cin >> m;
		a.push_back(m);
	}
//冒泡排序	
	for (int i = 1; i < a.size(); i++)
	{
		for (int j = 0; j < a.size() - i; j++)
		{
			if (a[j] > a[j + 1])
			{
				int temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
	for (int i = 0; i < n; i++)
	{
		cout << a[i] << endl;
	}
	return 0;

}

选择排序

选择排序是指，对一个序列A中的元素A[1]~A[n]，令i从1到n枚举，进行n趟操作，每趟从待排序部分[i，n]中选择最小的元素，令其与待排序部分的第一个元素A[i]进行交换，这样元素A[i]就会与当前有序区间[1，i-1]形成新的有序区间[1，i]形成。于是在n趟操作后，所有元素就会是有序的。时间复杂度是O(n²)

算法步骤：

  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
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n;//元素个数
	int m;//输入元素大小
	cin >> n;
	vector<int> a;//动态数组
	for (int i = 0; i < n; i++)
	{
		cin >> m;
		a.push_back(m);
	}
	//选择排序，
	for (int i = 0; i < a.size()-1; i++)
	{
		int min = i;
		for (int j = i+1; j < a.size(); j++)
		{
			if (a[j] < a[min])
				min = j;//记录目前能找到的最小值元素的下标
		}

		if(i!= min)//将找到的最小值和i进行交换
		{
			int temp = a[i];
			a[i] = a[min];
			a[min] = temp;
		}
		
	}

	for (int i = 0; i < n; i++)
	{
		cout << a[i] << endl;
	}
	return 0;

}

插入排序

插入排序是将待插入元素一个个插入初始已有序部分中的过程，而插入位置的选择遵循了使插入后仍然保持有序的原则，具体的做法一般是从后往前枚举已有序部分来确定插入位置。

算法步骤：

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

动图演示：

动图演示

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
#include <iostream>
#include <vector>
using namespace std;

int main()
{
	int n;//元素个数
	int m;//输入元素大小
	cin >> n;
	vector<int> a;//动态数组
	for (int i = 0; i < n; i++)
	{
		cin >> m;
		a.push_back(m);
	}
	//插入排序
	for (int i = 1; i < a.size(); i++)
	{
		int temp = a[i];//待插入的数据
		int j = i;
		while (j > 1 && temp < a[j - 1])
		{
			a[j] = a[j - 1];//将待插入的数据不停的比较，向左移动
			j--;
		}
		if (i != j)
		{
			a[j] = temp;//插入数据
		}
	}

	for (int i = 0; i < n; i++)
	{
		cout << a[i] << endl;
	}
	return 0;

}

快速排序

快速排序是排序算法中平均时间复杂度为O（nlogn）的一种算法，其实现需要先解决这样一个问题：对一个序列A[0]、A[1]、…、A[n-1]，调整序列中元素的位置，使得A[0]（原序列的A[1]，下同）的左侧所有元素都不超过A[1]、右侧所有元素都大于A[1]。例如对序列{5，3，9，6，4，1}来说，可以调整序列中元素的位置，形成序列{3，1，4，5，9，6}，这样就让A[0]=5左侧的所有元素都不超过它、右侧的所有元素都大于它。

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

算法步骤：

  1. 从数列中挑出一个元素，称为 “基准”
  2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作；
  3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序；

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会退出，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

也就是:

①先将A[0]存至某个临时变量temp，并令两个下标left、right分别指向序列首尾（如令left=0、right=n-1）。
②只要right 指向的元素A[right]大于temp，就将right 不断左移；当某个时候A[right]
≤temp时，将元素A[right]挪到left指向的元素A[left]处。
③只要left指向的元素A[left]不超过temp，就将left不断右移；当某个时候A[left]>temp时，将元素A[left]挪到right指向的元素A[right]处。
④重复②③，直到left与right相遇，把temp（也即原A[0]）放到相遇的地方。

动图演示：

动图演示

代码：

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
61
62
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1000;

int partition(int a[], int left, int right)
{
	int temp = a[left];
	while (left < right) {
		while (left < right && temp < a[right]) right--;
		a[left] = a[right];
		while (left < right && temp >= a[left]) left++;
		a[right] = a[left];
		
	}

	a[left] = temp;
	return left;
}

void quicksort(int a[], int left, int right)
{
	if (left < right) {
		int pos = partition(a, left, right);
		quicksort(a, left, pos - 1);
		quicksort(a, pos + 1, right);
	}
}

int main()
{
	int n;//元素个数
	int m;//输入元素大小
	cin >> n;
	//vector<int> a;//动态数组
	int a[maxn];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		//a.push_back(m);
	}
	//希尔排序
	/*for (int gap = a.size() / 2; gap > 0; gap /= 2) {
		for (int i = gap; i < a.size(); i++) {
			int key = a[i];
			int j;
			for (j = i - gap; j > 0 && a[j] > key; j = j - gap)
				a[j + gap] = a[j];
				a[j + gap] = key;
		}
	}*/
	quicksort(a, 0, n-1);


	for (int i = 0; i < n; i++)
	{
		cout << a[i] << endl;
	}
	return 0;

}

归并排序

两路归并排序代码：

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
61
62
63
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 100;


//2路归并排序
void merge(int a[], int L1, int R1, int L2, int  R2)
{
	int i = L1;
	int j = L2;
	int temp[maxn], index = 0;
	while (i <= R1 && j <= R2) {
		if (a[i] <= a[j])
		{
			temp[index++] = a[i++];
		}
		else {
			temp[index++] = a[j++];
		}
	}
	while (i <= R1) {
		temp[index++] = a[i++];
	}
	while (j <= R2) {
		temp[index++] = a[j++];
	}
	//合并后的序列赋值回数组a
	for (int i = 0; i < index; i++)
		a[i + L1] = temp[i];
}

void mergesort(int a[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		mergesort(a, left, mid);
		mergesort(a, mid + 1, right);
		merge(a, left, mid, mid + 1, right);//两个有序的子区间合并
	}
}

int main()
{
	int n;//元素个数
	//int m;//输入元素大小
	cin >> n;
	//vector<int> a;//动态数组
	int a[maxn];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		//a.push_back(m);
	}
	mergesort(a, 0, n - 1);

	for (int i = 0; i < n; i++)
	{
		cout << a[i] << endl;
	}
	return 0;

}
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
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
// sort.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//
#pragma
//#include "pch.h"
#include <iostream>
#include <vector>
#include <cstring>
using namespace std;
const int maxn = 1000;

/* int partition(int a[], int left, int right)
{
	int temp = a[left];
	while (left < right) {
		while (left < right && temp < a[right]) right--;
		a[left] = a[right];
		while (left < right && temp >= a[left]) left++;
		a[right] = a[left];		
	}

	a[left] = temp;
	return left;
} */

//2路归并排序
void merge(int a[], int L1, int R1, int L2, int  R2)
{
	int i = L1;
	int j = L2;
	int temp[maxn], index = 0;
	while (i <= R1 && j <= R2) {
		if (a[i] <= a[j])
		{
			temp[index++] = a[i++];
		}
		else {
			temp[index++] = a[j++];
		}
	}
	while (i <= R1) {
		temp[index++] = a[i++];
	}
	while (j < R2) {
		temp[index++] = a[j++];
	}
	//合并后的序列赋值回数组a
	for (int i = 0; i < index; i++)
		a[i + L1] = temp[i];
}

void mergesort(int a[], int left, int right) {
	if (left < right) {
		int mid = (left + right) / 2;
		mergesort(a, left, mid);
		mergesort(a, mid + 1, right);
		merge(a, left, mid, mid + 1, right);//两个有序的子区间合并
	}
}

int main()
{
	int n;//元素个数
	//int m;//输入元素大小
	cin >> n;
	//vector<int> a;//动态数组
	int a[maxn];
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		//a.push_back(m);
	}
	mergesort(a, 0, n - 1);

	for (int i = 0; i < n; i++)
	{
		cout << a[i] << endl;
	}
	return 0;

}


// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门提示: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件