1 交换排序

基本思想就是：两两进行比较，如果发生逆序则进行交换，直到所有的记录都排好为止。
常见的交换排序方法：

• 冒泡排序$O(n^2)$
• 快速排序$O(nlo{g}_{2}n)$

1.1 冒泡排序

冒泡排序就是基于简单的交换思想。每趟不断将记录两两比较，并按前小后大规则交换。

一些结论：

• $n$个记录，总共需要$n-1$趟
• 第$m$趟需要比较$n-m$次

1.1.1 冒泡排序算法

void bubble_sort(SqList &L)//冒泡排序算法
{
	int m,i,j;
	RedType x;//交换时临时存储
	for(m=1; m<=n-1; ++m)//总共需要m趟
	{
		for(j=1; j<=n-m; ++j)//交换需要n-m次
		{
			if (L.r[j].key > L.r[j+1].key)
			//两个相邻元素进行比较
			//发生逆序
			{
				x = L.r[j];
				L.r[j] = L.r[j+1];
				L.r[j+1] = x;//交换
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

已经排好序后，就无需做无用的交换了。

算法的改进：

void bubble_sort(SqList &L)//冒泡排序算法
{
	int m,i,j;flag = 1;//flag作为是否交换的标记
	RedType x;//交换时临时存储
	for(m=1; m<=n-1 && flag==1; ++m)//总共需要m趟
	{
		flag = 0;
		for(j=1; j<=n-m; ++j)//交换需要n-m次
		{
			if (L.r[j].key > L.r[j+1].key)
			//两个相邻元素进行比较
			//发生逆序
			{
				flag = 1;//发生交换，flag置为1
				x = L.r[j];
				L.r[j] = L.r[j+1];
				L.r[j+1] = x;//交换
			}
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

1.1.2 性能分析

1.2 快速排序

基本思想：任意取一个元素，如第一个元素，为中心。

采用递归的思想，结束条件是子表只剩一个元素。

• 基本思想： 通过一趟排序，将待排序记录分割成独立的两部分，其中一部分记录的关键字均比另一部分记录的关键字小，则可分别对这两部分记录进行排序，以达到整个序列有序。

• 具体实现： 选定一个中间数作为参考，所有元素与之比较，小的调到其左边，大的调到其右边。

• (枢轴)中间数： 可以是第一个数、最后一个数、最中间一个数、任选一个数等。

1.2.1 快排的算法

1.2.2 性能分析

1.2.3 快排的特点

1. 每一趟的子表的形成是采用从两头向中间交替式逼近法
2. 由于每趟中对各子表的操作都相似，可采用递归算法
3. 快排是个不稳定的算法

2 简单选择排序

示意图：

2.1 简单排序算法

2.1.1 性能分析

2.2 堆排序

堆的实质是完全二叉树。
小根堆就是每一个根节点都比左右孩子来的小；大根堆就是每一个根节点都比左右孩子来的大。即一个根是最大值，一个根是最小值，就可以用来排序。

2.2.1 堆的调整

大根堆就找大的数值。

可以看出：
对一个无序序列反复“筛选”就可以得到一个堆；
即：从一个无序序列建堆的过程就是一个反复“筛选”的过程。

显然：
单结点的二叉树是堆；在完全二叉树中所有以叶子结点（序号$ⅰ>/2$）为根的子树是堆。

由于堆实质上是一个线形表，那么我们可以顺序存储一个堆。

2.2.2 筛选过程算法

2.2.3 堆的建立算法

2.2.4 性能分析

3 归并排序

基本思想：将两个或两个以上的有序子序列归并为一个有序序列。

两个两个来。（或两个以上）

总共需要$lo{g}_{2}n$趟。

线性表，双指针，即可比较合并。

现在两个子序列是相邻的。也是两个指针。

3.1 性能分析

4 基数排序

不需要比较，思想就是分配和收集。也叫桶排序或箱序：设置若干个箱子，将关键字为k的记录放入第k个箱子，然后在按序号将非空的连接。

基数排序： 数字是有范围的，均由0-9这十个数字组成，则只需设置十个箱子，相继按个、十、百.…进行排序。

以上就个位就有序了。之后按十位分：
十位有序，按照百位分：

发现排序完成。

4.1 性能分析

5 各种排序算法的比较