排序专题

    排序分为几大类：插入排序，选择排序，交换排序，归并排序，基数排序。衡量排序方法的好坏有三种标准：时间复杂度，空间复杂度，稳定性。

    在这里着重讲解一下热点排序：选择排序中的堆排序，交换排序中的冒泡和快速排序，归并排序。

    在选择排序中，有一种简单的方法叫做直接选择排序，直接选择排序的基本思想是：从待排序的数据元素中选取关键字最小的数据元素并将它与第一个数据交换位置；接着从不包括第一个位置的数据元素集合中选取关键字最小的，与第二个位置的数据交换，如此重复，直到只剩一个数据元素为止。显然，这种排序方式的时间复杂度为O(n*n)。

    在直接选择排序中，待排序的数据元素集合构成一个线性表，要从有n个数据元素的线性表中选择出一个最小的数据元素需要比较n-1次。如果能把待排序的数据元素集合构成一棵完全二叉树结构，则每次选择出一个最大（最小）的元素只需要比较log2n次，所以排序的时间复杂度就是O(n*log2n)，这就是堆排序的思想。

    堆排序的流程：

    1.将完全二叉树调整为一个最大（小）堆。

     从第一个非叶子结点开始到根节点，每次都将当前结点调整为一个最大堆，前提是当前结点的左孩子和右孩子都已经是最大堆。

    2.每次把堆顶与当前最大堆的最后一个元素交换，最大堆元素个数减1，若此时根节点不满足最大堆的定义，调整根节点使之满足最大堆的定义。

//堆排序：基于完全二叉树，是一种选择排序，不稳定。
#include <iostream>
const int MAX = 100001;
int a[MAX];
//调整非叶子结点a[h]使之满足最大堆的定义。前提：它的左孩子a[2*h+1]和右孩子a[2*h+2]均已是最大堆。
 void createHeap(int n, int h)
 {
	 int i = h;
	 int j = 2*i + 1;
	 int t = a[i];
	 bool flag = false;
	 while(j < n && !flag)
	 {
		 if(j < n-1 && a[j] < a[j+1])
			 j++;
		 if(t > a[j])
			 flag = true;
		 else
		 {
			 a[i] = a[j];
			 i = j;
			 j = 2*i + 1;
		 }
	 }
	 a[i] = t;
 }

//从第一个非叶子结点a[(n-1)/2]开始到a[0]，构造最大堆。
 void initialHeap(int n)
 {
	 for(int i = (n-1)/2; i>=0; i--)
		 createHeap(n, i);
 }

//每次将当前最大堆的堆顶a[0](最大)与最后一个元素交换。
 void heapSort(int n)
 {
	 int t;
	 initialHeap(n);
	 for(int i = n-1; i > 0; i--)
	 {
		 t = a[0];
		 a[0] = a[i];
		 a[i] = t;
		 createHeap(i,0);
	 }
 }

int main()
{
	int n;
	scanf("%d",&n);
	for(int i = 0; i < n; i++)
		scanf("%d",&a[i]);
	heapSort(n);
	printf("%d",a[n/2]);
	return 0;
}

 

    交换排序中的冒泡排序思想：依次比较相邻的两个数，如果a[i]>a[i+1]，就把i和i+1交换位置。这样，第一遍时，最大的数就排在了最后，如此反复，就可以排序。

    冒泡排序的优化：可以设置一个标志位，如果某一次循环中发现位置都没有变化，显然数组已排好序，直接退出。冒泡排序的时间复杂度为O(n*n)冒泡排序代码比较简单，在这里就不写了。

    快速排序是一种二叉树结构的交换排序方式。快速排序的思想：每次循环结束后，一反面将标准元素（通常为a[low]）放在了未来排好序的数组中的正确位置，另一方面将数组中的元素分为了两个子数组，位于标准元素左边的关键字均小于它，位于关键元素右边的关键字均大于等于它，然后对这两个子数组分别进行同样的操作，直到low=high结束。

    快速排序最坏的情况是数组已完全有序，此时二叉树将退化为单分支二叉树，深度为n。但它的平均时间复杂度为O(n*log2n)，不是一种稳定的排序方法。

#include <iostream>
const int MAX = 100000;
int a[MAX];
int n;

void myQuickSort(int low, int high)
{
	int i = low, j = high;
	int t = a[low];
	while(i < j)
	{
		while(i < j && t <= a[j]) j--;
		if(i < j)
		{
			a[i] = a[j];
			i++;
		}
		while(i < j && t > a[i]) i++;
		if(i < j)
		{
			a[j] = a[i];
			j--;
		}
	}
	a[i] = t;
	if(low < i) myQuickSort(low, i -1);
	if(i < high) myQuickSort(j + 1, high);
}

int main()
{
	int i;
	scanf("%d",&n);
	for(i = 0; i < n; i++)
		scanf("%d",&a[i]);
	myQuickSort(0, n-1);
	printf("%d\n",a[n/2]);
	return 0;
}

 

    归并排序主要是二路归并排序，采用分治的思想：对于某个数组a[n]排序，先将前半部分排序，再将后半部分排序，最后归并两部分。

   归并排序是一种稳定的排序方式，且时间复杂度为O(n*log2n)。

   归并排序还可以求一串数中的逆序数。在归并相邻的两个有序子数组：

XlowXlow+1Xlow+2...Xmid和Ymid+1Y2Y3Y4..Yhigh的过程中，令i=low,j=mid+1，其中：Xi<Xi+1,Yi<Yi+1。

若在某此比较a[i]与a[j]时，发现a[i]>a[j]，说明a[i]与a[j]是一对逆序数，并且a[i+1],a[i+2],...,a[mid]都是大于等于a[i]，说明a[i+1]与a[j],a[i+2]与a[j],...,a[mid]与a[j]都是逆序对。因此，逆序对应该加上mid-i+1。

#include <iostream>
const int MAX = 500000;
int a[MAX];
int swap[MAX];		//临时数组
int n;				//数组a的长度
__int64 result;			//数组a中的逆序数

//归并两个已经有序的段：a[low]—a[mid]和a[mid+1]—a[high]，使得a[low]—a[high]有序。
void merge(int low, int mid, int high)
{
	int i = low;
	int j = mid + 1;
	int m = 0;
	while(i <= mid && j <= high)
	{
		if(a[i] <= a[j])
		{
			swap[m++] = a[i];
			i++;
		}
		else
		{
			swap[m++] = a[j];
			j++;
			result += mid - i + 1;
		}
	}
	while(i <= mid)
	{
		swap[m++] = a[i];
		i++;
	}
	while(j <= mid)
	{
		swap[m++] = a[j];
		j++;
	}
	for(i = 0; i < m; i++)
		a[low + i] = swap[i];
}

//归并排序：对a[low]—a[high]进行归并排序。
void mergeSort(int low, int high)
{
	int mid;
	if(low < high)
	{
		mid = (low + high) >> 1;
		mergeSort(low, mid);
		mergeSort(mid + 1, high);
		merge(low, mid, high);
	}
}

int main()
{
	int i;
	while(true)
	{
		scanf("%d",&n);
		if(n == 0) break;
		result = 0;
		for(i = 0; i < n; i++)
			scanf("%d",a+i);
		mergeSort(0, n-1);
		printf("%I64d\n",result);
	}
	return 0;
}

 

参见POJ2388,2299。