交换类排序详解及总结

交换类排序思想是通过一系列交换逆序元素进行排序的方法。本文首先介绍基于简单交换思想实现的冒泡排序法，在此基础上给出改进方法——快速排序法。

冒泡排序

【算法思想】反复扫描待排序记录序列，在扫描的过程中顺次比较相邻的两个元素的大小，若逆序就交换位置。

以升序为例，在第一趟冒泡排序中，从第一个记录开始，扫描整个待排记录序列，若相邻的两个位置逆序，则交换位置。

在扫描的过程中，不断地将相邻两个记录中关键字大的记录向后移动，最后必然将待排序记录序列中的最大关键字记录换到待排序列中的最大关键字记录换到待排序记录序列的末尾，这也是最大关键字记录应在的位置。

然后进行第二趟冒泡排序，对前n-1个记录进行同样的操作，其结果是使次大的记录被放到第n-1个记录的位置上。

然后进行第三趟冒泡排序，对前n-2个记录进行同样的操作，其结果是使第三大的记录被放到第n-2个记录的位

置上。

如此反复，每一堂冒泡排序都将一个记录排到位，直到剩下一个最小的记录。

若在某一趟冒泡排序过程中，没有发现一个逆序，则可直接结束整个排序过程，所以冒泡过程最多进行n-1趟。

void BubbleSort(int arr[], size_t size)
{
	bool flag = true;

	for (int i = 0; i 	{
		flag = false;
		for (int j = 0; j 		{
			if (arr[j] > arr[j + 1])
			{
				std::swap(arr[j], arr[j + 1]);
				flag = true;
			}
		}
	}
}

【算法分析】冒泡排序算法的最坏情况是待排序记录按关键字的逆序排列，此时，第i趟冒泡排序需进行n-i次比较，

3（n-i）次移动。经过第n-1趟冒泡排序后，总的比较次数为n（n-1）/2，总的移动次数为3n（n-1）/2次，因此该算法的时间复杂度为O(n^2),空间复杂度为O(1)。另外，冒泡排序法是一种稳定的排序方法。

快速排序

【算法改进要点】在以上讨论的冒泡排序中，由于扫描过程中只对相邻的两个元素进行比较，因此在互换两个相邻元素时只能消除一个逆序。如果能通过两个（不相邻）的元素的交换，消除待排序记录中的多个逆序，则会大大加快排序的速度。快速排序方法中的一次交换可能消除多个逆序。

【算法思想】从待排序记录序列中选一个记录（通常选取第一个记录）为枢轴，其关键字设为K1，然后将其余关键字小于K1的记录移动到前面，而将关键字大于K1的记录移到后面，结果将待排序记录序列分为两个子表，最后将关键字K1的记录插入到其分界线的位置处。将这个过程称为一趟快速排序。通过一次划分后，就以关键字K1的记录为界，将待排序序列分成了两个子表，且前面子表中所有记录的关键字均不大于K1，而后面子表中的所有记录的关键字均不小于K1。对分割后的子表继续按上述原则进行分割，直到所有子表的表长不超过1为止，此时待排序记录序列酒标成了一个有序表。

以下是三种递归方式实现的快速排序：

int partion(int arr[], int begin, int end)
{
	int key = arr[begin];
	while (begin 	{

		while (begin= key)
			end--;

		if (begin 		{
			arr[begin] = arr[end];
			begin++;
		}

		while (begin			begin++;

		if (begin 		{
			arr[end] = arr[begin];
			end--;
		}
	}
	arr[begin] = key;
	return begin;
}

int partion1(int *arr, int left, int right)
{
	int Cur = left;
	int prev = Cur - 1;
	int key = arr[right];
	while (Cur <= right)
	{
		if (arr[Cur] <= key && ++prev == Cur - 1)
			std::swap(arr[Cur], arr[prev]);
		++Cur;
	}
	return prev;

}

int partion2(int array[], int left, int right)
{
	int begin = left;
	int end = right-1;

	int key = array[right];

	while (begin 	{
		while (begin 			begin++;

		while (begin  key)
			end--;

		if (begin 		{
			swap(array[begin], array[end]);
			begin++;
		}
	}
	if (begin != right && array[begin] > array[right])
	{
		swap(array[begin], array[right]);
		return begin;
	}
	return right;
}

void QuickSort(int arr[], int left, int right)
{
	if (left 	{
		int div = partion2(arr, left, right);
		QuickSort(arr, left, div - 1);
		QuickSort(arr, div + 1, right);
	}
}

非递归方式实现的快速排序：

void QuickSortNor(int *arr, int left, int right)
{
	stack s;
	s.push(right);
	s.push(left);
	while (!s.empty())
	{
		left = s.top();
		s.pop();
		right = s.top();
		s.pop();
		if (left 		{
			int div = partion(arr, left, right);
			s.push(right);
			s.push(div + 1);
			s.push(div - 1);
			s.push(left);
		}
	}
}