Tracy's Studio.

排序算法

算法
字数统计: 4.1k阅读时长: 17 min
2019/08/29 Share

排序算法

排序算法的稳定性：两个相等的数据前后顺序不发生改变。

冒泡排序

每次排序能够确定最后一个元素的位置（将最大的元素移到最后一个位置）
算法思想

冒泡排序原理

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void Bubble_sort(int *A, int n) {
	int flag = 0;
	for (int i = n - 1; i >= 0; i--) {
		for (int j = 0; j < i; j++) {
			if (A[j] > A[j + 1]) {
				int temp = A[j];
				A[j] = A[j + 1];
				A[j + 1] = temp;
			}
			flag = 1;//进行了交换
		}
		if (flag == 0)
			break;//当某一轮没有交换的时候，说明顺序表已经有序了
	}
}

改进

① 传统冒泡排序中每一趟排序操作只能找到一个最大值或最小值,我们考虑利用在每趟排序中进行正向和反向两遍冒泡的方法一次可以得到两个最终值(最大者和最小者) , 从而使排序趟数几乎减少了一半。

② 设置一标志性变量pos, 用于记录每趟排序中最后一次进行交换的位置。由于pos位置之后的记录均已交换到位,故在进行下一趟排序时只要扫描到pos位置即可。

1
2
3
4
5
6
7
8
9
10
11
12
void Bubble_1(int r[], int n) {
	int i = n - 1;  //初始时,最后位置保持不变  
	while (i> 0) {
		int pos = 0; //每趟开始时,无记录交换  
		for (int j = 0; j< i; j++)
			if (r[j]> r[j + 1]) {
				pos = j; //记录交换的位置   
				int tmp = r[j]; r[j] = r[j + 1]; r[j + 1] = tmp;
			}
		i = pos; //为下一趟排序作准备  
	}
}

插入排序

简单插入排序

类似于抓牌，每次都认为第i个元素之前的元素全部就位。
基本思想
将一个记录插入到已排序好的有序表中，从而得到一个新记录数增1的有序表。即：先将序列的第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
#include <iostream>
using namespace std;

void Print(int *A, int n, int i) {
	cout << i << ":";
	for (int j = 0; j < n; j++) {
		cout << A[j] << " ";
	}
	cout << endl;
}


void Insert_Sort(int *A,int n){
	int j;
	for (int i = 1; i < n; i++) {
		int temp = A[i];
		for (j = i; j > 0&&A[j-1]>temp; j--) {//！！条件很重要
			A[j] = A[j - 1];
		}
		A[j] = temp;
		Print(A, n, i);
	}
}
int main() {
	int a[8] = { 3,1,5,7,2,4,9,6 };
	Insert_Sort(a, 8);           //直接插入排序  
	Print(a, 8, 8);
}

希尔排序

希尔排序是1959 年由D.L.Shell 提出来的，相对直接排序有较大的改进。希尔排序又叫缩小增量排序可以看成是插入排序的升级版本。

基本思想：
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

操作方法

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列个数k，对序列进行k 趟排序；
  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

希尔排序的示例

希尔排序

算法实现：

  • 我们简单处理增量序列：增量序列d = {n/2 ,n/4, n/8 …..1} n为要排序数的个数

  • 即：先将要排序的一组记录按某个增量d（n/2,n为要排序数的个数）分成若干组子序列，每组中记录的下标相差d.对每组中全部元素进行直接插入排序，然后再用一个较小的增量（d/2）对它进行分组，在每组中再进行直接插入排序。继续不断缩小增量直至为1，最后使用直接插入排序完成排序。

代码示例

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>
using namespace std;

void Print(int *A, int n, int i) {
	cout << i << ":";
	for (int j = 0; j < n; j++) {
		cout << A[j] << " ";
	}
	cout << endl;
}


void ShellInsert_Sort(int *A,int n,int dk){
	int j;
	for (int i = dk; i < n; i++) {
		int temp = A[i];
		for (j = i; j > 0&&A[j-dk]>temp; j-=dk) {//！！条件很重要
			A[j] = A[j - dk];
		}
		A[j] = temp;
		Print(A, n, i);
	}
}
void Shell_Sort(int *A,int n) {
	int dk = n/2;
	while (dk>=1) {
		ShellInsert_Sort(A, n, dk);
		dk /= 2;
	}
}
int main() {
	int a[8] = { 3,1,5,7,2,4,9,6 };
	Shell_Sort(a, 8);           //直接插入排序  
	Print(a, 8, 8);
}

结果

希尔排序结果

总结

希尔排序时效分析很难，关键码的比较次数与记录移动次数依赖于增量因子序列d的选取，特定情况下可以准确估算出关键码的比较次数和记录的移动次数。目前还没有人给出选取最好的增量因子序列的方法。增量因子序列可以有各种取法，有取奇数的，也有取质数的，但需要注意：增量因子中除1 外没有公因子，且最后一个增量因子必须为1。希尔排序方法是一个不稳定的排序方法。

逆序对

满足条件：iA[j]

任意N个不同元素的组成的序列平均有N(N-1)/4个逆序对，所以任意建立在交换相邻两元素基础上的排序算法的时间复杂度为$ \Omega(N^{2})$

因此目标：每次交换能消掉好几个逆序对。

选择排序

堆排序

堆排序是一种树形选择排序，是对直接选择排序的有效改进。
基本思想：
堆的定义如下：具有n个元素的序列（k1,k2,…,kn),当且仅当满足：

堆

时称之为堆，即当子女节点均小于（/大于）父结点的时候，可以构成最大（/小）堆，由堆的定义可以看出，堆顶元素（即第一个元素）必为最小项（小顶堆）。

若以一维数组存储一个堆，则堆对应一棵完全二叉树，且所有非叶结点的值均不大于(或不小于)其子女的值，根结点（堆顶元素）的值是最小(或最大)的。如：
（a）大顶堆序列：（96, 83,27,38,11,09)
（b）小顶堆序列：（12，36，24，85，47，30，53，91）

堆2

初始时把要排序的n个数的序列看作是一棵顺序存储的二叉树（一维数组存储二叉树），调整它们的存储序，使之成为一个堆，将堆顶元素输出，得到n 个元素中最小(或最大)的元素，这时堆的根节点的数最小（或者最大）。然后对前面(n-1)个元素重新调整使之成为堆，输出堆顶元素，得到n 个元素中次小(或次大)的元素。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。称这个过程为堆排序。

因此，实现堆排序需解决两个问题：
① 如何将n 个待排序的数建成堆；
建堆方法：对初始序列建堆的过程，就是一个反复进行筛选的过程。
n 个结点的完全二叉树，则最后一个结点是第1 个结点的子树；筛选从第 2个结点为根的子树开始，该子树成为堆；之后向前依次对各结点为根的子树进行筛选，使之成为堆，直到根结点。

如图为建最小堆初始过程：无序序列：（49，38，65，97，76，13，27，49）

3

② 输出堆顶元素后，怎样调整剩余n-1 个元素，使其成为一个新堆。
设有m 个元素的堆，输出堆顶元素后，剩下m-1 个元素。将堆底元素送入堆顶（（最后一个元素与堆顶进行交换），堆被破坏，其原因仅是根结点不满足堆的性质。
将根结点与左、右子树中较小元素的进行交换。
若与左子树交换：如果左子树堆被破坏，即左子树的根结点不满足堆的性质，则重复方法 （2）.
若与右子树交换，如果右子树堆被破坏，即右子树的根结点不满足堆的性质。则重复方法 （2）.
继续对不满足堆性质的子树进行上述交换操作，直到叶子结点，堆被建成。
称这个自根结点到叶子结点的调整过程为筛选。如图：

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
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
/*
	建立一个大顶堆，每次把最大的元素放到最后
*/
#include <iostream>
using namespace std;


void print(int a[], int n) {
	for (int j = 0; j<n; j++) {
		cout << a[j] << "  ";
	}
	cout << endl;
}

/**
* 已知H[s…m]除了H[s] 外均满足堆的定义
* 调整H[s],使其成为大顶堆.即将对第s个结点为根的子树筛选,
*
* @param H是待调整的堆数组
* @param s是待调整的数组元素的位置
* @param length是数组的长度
*
*/
void HeapAdjust(int H[], int s, int length)
{
	int tmp = H[s];
	int child = 2 * s + 1; //左孩子结点的位置。(i+1 为当前调整结点的右孩子结点的位置)  
	while (child < length) {//当树是完美二叉树的时候，是没有左孩子的，所以要对于元素进行判断
		if (child + 1 <length && H[child]<H[child + 1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)  
			++child;
		}
		if (H[s]<H[child]) {  // 如果较大的子结点大于父结点  
			H[s] = H[child]; // 那么把较大的子结点往上移动，替换它的父结点  
			s = child;       // 重新设置s ,即待调整的下一个结点的位置  
			child = 2 * s + 1;
		}
		else {            // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出  
			break;
		}
		H[s] = tmp;         // 当前待调整的结点放到比其大的孩子结点位置上  
	}
	print(H, length);
}


/**
* 初始堆进行调整
* 将H[0..length-1]建成堆
* 调整完之后第一个元素是序列的最小的元素
*/
void BuildingHeap(int H[], int length)
{
	//最后一个有孩子的节点的位置 i=  (length -1) / 2  
	for (int i = (length - 1) / 2; i >= 0; --i) {
		cout << "建立堆:";
		HeapAdjust(H, i, length);
	}
}
/**
* 堆排序算法
*/
void HeapSort(int H[], int length)
{
	//初始堆  
	BuildingHeap(H, length);
	//从最后一个元素开始对序列进行调整  
	for (int i = length - 1; i > 0; --i)
	{
		//交换堆顶元素H[0]和堆中最后一个元素  
		int temp = H[i]; H[i] = H[0]; H[0] = temp;
		//每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整  
		cout << "调整堆:";
		HeapAdjust(H, 0, i);
	}
}

int main() {
	int H[10] = { 3,1,5,7,2,4,9,6,10,8 };
	cout << "初始值：";
	print(H, 10);
	HeapSort(H, 10);
	//selectSort(a, 8);  
	cout << "结果：";
	print(H, 10);
}

结果

5

简单选择排序

基本思想：
在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。
简单选择排序的示例

简单选择排序

操作方法：
第一趟，从n 个记录中找出关键码最小的记录与第一个记录交换；
第二趟，从第二个记录开始的n-1 个记录中再选出关键码最小的记录与第二个记录交换；
以此类推…..
第i 趟，则从第i 个记录开始的n-i+1 个记录中选出关键码最小的记录与第i 个记录交换，
直到整个序列按关键码有序。
算法实现
寻找第i个元素之后最小的元素
交换位置

代码

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

void Print(int *A, int n, int i) {
	cout << i << ":";
	for (int j = 0; j < n; j++) {
		cout << A[j] << " ";
	}
	cout << endl;
}

//找到i位置之后最小的元素，放到当前某个位置
int Selectminkey(int *A, int n, int i) {
	int k = i;
	for (int j = i + 1; j < n; j++)
		if (A[k] > A[j])
			k = j;
	return k;
}
void Select_Sort(int *A,int n){
	for(int i=0;i<n-1;i++){
		int k= Selectminkey(A, n, i);
		if (k != i) {
			//交换第i个和第maxidex个
			int tmp = A[k];
			A[k] = A[i];
			A[i] = tmp;
		}
		Print(A, 8, i);
	}
}

int main() {
	int a[8] = { 3,1,5,7,2,4,9,6 };
	Select_Sort(a, 8);           //直接插入排序  
	Print(a, 8, 8);
}

结果

简单选择结果

改进的选择排序——二元选择排序

每次循环确定最大值和最小值的位置。

快速排序

基本思想：
选择一个基准元素,通常选择第一个元素或者最后一个元素,
通过一趟排序将待排序的记录分割成独立的两部分，其中一部分记录的元素值均比基准元素值小。另一部分记录的 元素值比基准值大。
此时基准元素在其排好序后的正确位置
然后分别对这两部分记录用同样的方法继续进行排序，直到整个序列有序。
坏处
调用递归，对于小规模数据浪费了时间。
快速排序的示例：
一趟排序的过程：

快排

排序的全过程：

kp过程

评价

快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。为改进之，通常以“三者取中法”来选取基准记录，即将排序区间的两个端点与中点三个记录关键码居中的调整为支点记录。快速排序是一个不稳定的排序方法。对于大规模的随机数据表现出色。每一次调整后，主元的位置都会放在正确的位置上。

6

最好情况：每次正好中分。
选主元：最坏情况是序列本来就是有序的，O(N^2)
取头、中、尾的中位数。

7

代码实现

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


void print(int a[], int n) {
	for (int j = 0; j<n; j++) {
		cout << a[j] << "  ";
	}
	cout << endl;
}
void swap(int *a, int *b) {
	int temp = *a;//int *temp=*a会报错
	*a = *b;
	*b = temp;
}

int Median3(int *A, int left, int right) {
	int center = (left + right) / 2;
	if (A[left] > A[center]) {
		swap(&A[left], &A[center]);
	}
	if (A[right] < A[left]) {
		swap(&A[right], &A[left]);
	}
	if (A[right] < A[center]) {
		swap(&A[right], &A[center]);
	}
	/*A[left]<=A[center]<=A[right]*/
	//问题：当right<0的时候，地址会泄露
	swap(&A[center], &A[right - 1]);/*将pivot藏到右边*/
	return A[right - 1];
}

void Quicksort(int *A, int left, int right) {
	int pivot = Median3(A, left, right);
	int low = left, high = right - 1;
	while (low < high) {
		while (A[++low] < pivot) {}
		while (A[--high] > pivot) {}
		if (low < high)
			swap(&A[low], &A[high]);
		else
			break;
	}
	swap(&A[low], &A[right - 1]);//把主元放到正确的位置
	cout << pivot << ":";
	print(A, 10);

	if (low>0) {
		if(left<=low-1)
			Quicksort(A, left, low - 1);
		if (low+1 <= right)
			Quicksort(A, low + 1, right);
	}
}
void Quick_sort(int *A, int n) {
	Quicksort(A, 0, n - 1);
}

int main() {
	int H[10] = { 3,1,5,7,2,6,8,0,4,9 };
	cout << "初始状态:";
	print(H, 10);
	Quick_sort(H, 10);
	print(H, 10);
}

结果
找不到文件

原文作者：Tracy

原文链接：http://tracywoo.cn/2019/08/29/排序算法/

发表日期：August 29th 2019, 3:04:13 pm

更新日期：March 29th 2022, 9:21:09 am

版权声明：本文采用知识共享署名-非商业性使用4.0国际许可协议进行许可

CATALOG
  1. 1. 排序算法
    1. 1.1. 冒泡排序
    2. 1.2. 插入排序
      1. 1.2.1. 简单插入排序
      2. 1.2.2. 希尔排序
      3. 1.2.3. 逆序对
    3. 1.3. 选择排序
      1. 1.3.1. 堆排序
      2. 1.3.2. 简单选择排序
      3. 1.3.3. 快速排序
Total : 20
2022
2021
2020
2019
CRL others hexo MOEA ML git node markdown 算法 写论文小技巧 PGM pgm
博客 ML MOEA