交换排序

交换排序的基本思想是：两两比较待排序记录的关键字，一旦发现两个记录不满足次序要求时则进行交换。下面先学习比较简单的冒泡排序。

冒泡排序

冒泡排序（Bubble Sort）通过两两比较相邻记录的关键字，如果发生逆序，则进行交换。那么为什么叫冒泡呢？这个问题就比较…难回答（还是那句老话，书上这么说的）。当然我们不能通过冒泡去联想到交换排序，而是应该通过交换排序去联想到冒泡（义正言辞）。

算法分析：

冒泡排序的算法还是比较简单的，说白了就是每一趟排序的结果就是使得关键字最大的记录被放在最后一个记录的位置上。

一般是将第一个记录的关键和第二个记录的关键字比较，若第一个大于第二个，则交换，相当于一直把大的往后送，第一趟排序结束后，最后一个记录的位置的关键最大。此时再进行第二趟排序，将余下含有最大关键字的记录交换到倒数第二个位置上，然后以此类推。直到在某一趟排序过程中没有进行过交换记录的操作，说明序列已全部达到排序要求，至此排序完成。

我们还需要注意的是，某一趟排序没有交换说明已排好，那么应该有一个标志来标记每一趟是否交换过记录。

具体代码：

#define MAXSIZE 20

typedef struct					//顺序表
{
	int r[MAXSIZE+1];
	int length;
}SqList;

void BubbleSort(SqList *L)
{
	int m,flag=1,t;
	m=L->length-1;					//减1是因为后一元素用j+1来表示的
	while(m>0 && flag==1)
	{
		flag=0;
		for(int j=1;j<=m;j++)
			if(L->[j] > L->r[j+1])
			{
				flag=1;
				t=L->r[j];
				L->r[j]=L->r[j+1];
				L->r[j+1]=t;
			}
			m--;					//每一趟都会排好一个记录
	}
}
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

冒泡排序的时间复杂度为$O(n^2)$，空间复杂度为$O(1)$。

快速排序

快速排序（Quick Sort）是由冒泡排序改进而得的。在冒泡排序中，只能对两个相邻的记录进行比较，因此每次交换两个相邻记录时只能消除一个逆序。如果能通过两个（不相邻）记录的一次交换，消除多个逆序，则会大大加快排序的速度。于是，快速排序法方法中的一次交换可能消除多个逆序。

下面就来学习快速排序是如何做到这一点的。

首先，它是借用了折半的概念，在待排序的所有记录中任取一个记录（不过一般都取得第一个记录）作为枢轴，设这个记录的关键字为$pivotkey$。再设两个指针$low、high$分别指向第一个记录和最后一个记录。经过一趟排序后，把所有关键字小于$pivotkey$的记录交换到前面，所有关键字大于$pivotkey$的记录交换到后面。一趟排序的结果就是$pivotkey$将这个序列分成两个子表，左边记录的关键字一定都小于$pivotkey$，右边记录的关键字一定都大于$pivotkey$。然后对左右子表重复上述过程，直至每一子表都只有一个记录时，排序完成。

一趟排序的具体过程：

1. 选择序列的第一个记录作为枢轴，将枢轴记录存在r[0]。$low=1,high=L.length$
2. 从表的最右侧开始向左搜索，当$low<high$时，只要$high$所指记录的关键字大于等于$pivotkey$，则向左移动指针$high$；否则将$high$所指记录与枢轴记录交换
3. 再从表的最左侧开始向右搜索，当$low<high$时，只要$low$所指记录的关键字小于等于$pivotkey$，则向右移动指针$low$；否则将$low$所指记录与枢轴交换
4. 重复步骤2、3，直至$low=high$为止。

例如：
具体代码：

//对一张表进行一趟排序
int Partition(SqList *L,int low,int high)
{
	//用子表中的第一个记录做枢轴记录
	L->r[0]=L->r[low];
	pivotkey=L->r[low];
	while(low<high)
	{
		while(low<high && L->r[high] >= pivotkey)
			high--;
		L->r[low]=L->r[high];
		while(low<high && L->r[low] <= pivotkey)
			low++;
		L->r[high]=L->r[low];
	}
	L->r[low]=L->r[0];								//枢轴记录到high=low的位置
	return low;										//返回枢轴位置
}

//对序列进行快速排序
void QSort(SqList *L,int low,int high)
{
	if(low<high)
	{
		pivotkey=Partition(&L,low,high);
		QSort(&L,low,pivotkey-1);
		QSort(&L,pivotkey+1,high);
	}
}
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

对于上述代码，刚开始的时候我有以下几个疑问：

1. 为什么$pivotkey$没有跟着指针$low、high$移动？
2. 为什么循环结束了才进行交换？
3. 交换时只是单纯的覆盖，比如$r[high]$赋值给$r[low]$，而这时第二个循环就会将$r[low]$赋值给上一个赋值给$r[low]$的$r[high]$，但是始终会少一个$r[low]$的值，哪里去了呢？

首先，对于第一个问题，$pivptkey$是一个值，用来表示枢轴这个枢轴将原序列划分为两个表，意思就是在原序列中任选一个记录作为枢轴后，这个枢轴的值肯定是不变的，只能说最后才能直到枢轴的位置在哪。

对于第二个问题，首先循环结束的条件是$low>=high$，或者$r[low]、r[high]$的值大于$pivotkey$，第一个结束条件可以理解为$high--,low++$都是在向枢轴靠。再一个就是每一趟快速排序的目的就是使左表里所有的关键字都小于等于$pivotkey$，而右表所有的关键全都大于等于$pivotkey$，所以当在左表遇到了大于$pivotkey$的值就结束循环进行交换…

对于第三个问题，在上面代码我们可以看到，$r[0]$暂存第一个记录的关键字，也就是$r[0]=r[low]=pivotkey$，只需在$low=high$的时候将$r[0]$赋值给它们就行了。

在平均情况下，快速排序的时间复杂度为$O(nlo{g}_{2}n)$
最好情况下的空间复杂度为$O(lo{g}_{2}n)$，最坏情况下空间复杂度为$O(n)$。

总结

学习了两种交换排序，分别是冒泡排序和快速排序，其中快速排序是基于冒泡排序改进的。交换排序的目的主要就是通过不停地两两交换数据元素，来使一个无序的序列变得有序。就算法的时间复杂度来说，快速排序是要比冒泡排序更快的，不然也不会叫“快速”了，但是空间复杂度较冒泡排序来说是更大了，所以快速排序就是以空间换时间，来提高排序的效率。冒泡排序是稳定的排序方法，也可以用于链式存储结构，但不适用于$n$较大的情况。而快速排序则是不稳定的排序，因为它的移动是非顺次的。因为它有$low、high$指针分别指向表头和表尾，所以只适用于顺序结构，但它适合$n$较大的情况。