1. 冒泡排序 (Bubble Sort)  [1]

1.1 算法描述

冒泡排序过程中， 从前往后依次扫描每一对相邻元素， 一旦发现逆序即交换二者的位置。  这一过程称作一趟扫描交换。

以此类推， 最多进行n-1趟扫描交换， 整个序列就排序完成了。

算法的平均时间复杂度为O(n^2)， 空间复杂度O(1)， 是稳定排序算法。

1.2 代码实现

void bubble_sort(int a[], int n)
{
	bool sorted;
	int i;

	while (!sorted)
	{
		sorted = true;
		for (i = 1; i < n; i++)
		{
			if (a[i-1] > a[i])
			{
				int tmp = a[i-1];
				a[i-1] = a[i];
				a[i] = tmp;

				sorted = false;
			}
		}
		n--;
	}
}

2. 插入排序 (Insertion Sort)  [2]

2.1 算法描述

该算法将序列划分为两部分， 左侧的已排序部分和剩下的待排序部分， 一开始已排序部分为空， 待排序部分为整个序列。 

把待排序部分的第一个元素和已排序部分的元素从后往前依次进行比较， 直到找到合适的位置并插入进去。

如此重复直至待排序部分为空……

该算法平均时间复杂度为O(n^2)， 空间复杂度O(1), 是稳定排序算法。

2.2 代码实现

void insert_sort(int a[], int n)
{
	int i, j, temp;

	for (i = 1; i < n; i++) 
	{
		temp = a[i];
		for (j = i - 1; j >= 0 && temp < a[j]; j--)
			a[j+1] = a[j];

		a[j+1] = temp;
	}
}

3. 选择排序 (Selection Sort)    [3]

3.1 算法描述

该算法将序列划分为两部分， 左侧的已排序部分和剩下的待排序部分。 一开始已排序部分为空， 待排序部分为整个序列。 

接下来在待排序序列中找出最小值， 和待排序序列中最左侧的元素进行交换。 把已排序序列的边界右移一位。

如此重复n-1次……

算法的时间复杂度为Θ(n^2) ， 空间复杂度O(1)， 是不稳定排序算法。

3.2 代码实现

void selection_sort(int a[], int n)
{
	int i, j, min;
	for (i = 0; i < n - 1; i++)
	{
		min = i;
		for (j = i + 1; j < n; j++)
			if (a[j] < a[min])
				min = j;

		if (min != i)
		{
			int temp = a[i];
			a[i] = a[min];
			a[min] = temp;
		}
	}
}

4. 归并排序 (Merge Sort) [4]

4.1 算法描述

该算法采用分而治之的策略， 先把整个序列不断划分， 直至划分为单个元素， 

然后开始合并， 在合并的过程中进行排序。

算法的时间复杂度为O(nlogn)， 空间复杂度为O(n), 为稳定排序算法。

4.2 代码实现

void merge(int[], int, int, int);

void merge_sort(int arr[], int l, int r)
{

	if (r - l < 2)
		return;
	else
	{
		//divide and conquer
		int m = (l + r) / 2;
		merge_sort(arr, l, m);
		merge_sort(arr, m+1, r);
		merge(arr, l, m, r);
	}
}

//merge two array, arr[l]...arr[m] and arr[m+1]...arr[r]
void merge(int arr[], int l, int m, int r)
{
	int n1 = m - l + 1;
	int n2 = r - m;
	int a[n1], b[n2];

	for (int i = 0, int j = l; i < n1; i++, j++)
		a[i] = arr[j];

	for (int i = 0, int j = m + 1; i < n2; i++, j++)
		b[i] = arr[j];

	int i = 0;
	int j = 0;
	int k = l;
	while (i < n1 && j < n2)
	{
		if (a[i] <= b[j]) 
		{
			arr[k] = a[i];
			i++;
		} 
		else 
		{
			arr[k] = b[j];
			j++;
		}
		k++;
	}

	while (i < n1) 
	{
		arr[k] = a[i];
		k++;
		i++;
	}

	while (j < n2) 
	{
		arr[k] = b[j];
		k++;
		j++;
	}
}

5. 桶排序 (Bucket Sort) [5]

6. 计数排序 (Counting Sort) [6]

7. 基排序 (Radix Sort) [7]

8. 堆排序 (Heap Sort) [8]

8.1 算法描述

该算法可以说是选择排序的改进版本，把整个序列分为左侧的未排序序列（组织为大顶堆的形式）和右侧的已排序部分。一开始右侧的已排序部分为空，左侧的未排序的部分为整个序列。

接下来从左侧未排序部分取出最大元素， 把已排序序列的边界左移一位， 把取出的最大元素放到右侧已排序部分的最左侧。 

如此重复直至未排序部分（大顶堆）为空……

算法的时间复杂度为Θ(n*log(n)) ， 空间复杂度O(1)， 是不稳定排序算法。

8.2 代码实现 （需其他函数代码支持）

void head_sort(int a, int low, int high)
{
	PQ_complHeap H(a, low, high);  //floyd法建堆
	while (!H.empty())
		a[--high] = H.delMax();
}

9. 锦标赛排序 (Tournament Sort) [9]

10. 快速排序 (Quick Sort) [10]

10.1 算法描述

该算法和归并算法类似，快速排序也是采用分而治之的策略来提高排序效率的。所不同的是，归并排序的时间主要消耗在归并上， 而快速排序的时间主要消耗在划分上。

快速排序排序时， 首先把序列划分为两个子序列， 然后递归的对两个子序列进行快速排序。 直到划分到平凡情况，每个子序列的个数为1， 这时便返回。

问题的关键， 如何进行子序列的划分？

可以把该序列的第一个数移动到它排序后的正确位置，同时它左侧都是比它小的数， 它右侧都是比它大的数。 以该数作为轴， 将两边的数划分为两个子序列。

算法的平均时间复杂度为Θ(n*log(n))  ， 平均空间复杂度O(n*log(n))， 是不稳定排序算法。

10.2 代码实现

int partition(int a[], int lo, int hi);
void quick_sort(int a[], int lo, int hi)
{
	if (hi - lo < 2)
		return;
	else
	{
		int mid = partition(a, lo, hi);
		quick_sort(a, lo, mid);
		quick_sort(a, mid + 1, hi);
	}
}

int partition(int a[], int lo, int hi)
{
	int pivot = a[lo];
	while (lo < hi)
	{
		while ((lo < hi) && (pivot <= a[hi]))
			hi--;
		a[lo] = a[hi];
		while ((lo < hi) && (pivot >= a[lo]))
			lo++;
		a[hi] = a[lo];
	}
	a[lo] = pivot;
	return lo;
}

11. 希尔排序 (Shell Sort) [11]

12. 性能总结 [12]

排序法	平均时间	最差情形	稳定度	额外空间	备注
冒泡	O(n2)	O(n2)	稳定	O(1)	n小时较好
插入	O(n2)	O(n2)	稳定	O(1)	大部分已排序时较好
选择	O(n2)	O(n2)	不稳定	O(1)	n小时较好
归并	O(nlogn)	O(nlogn)	稳定	O(1)	n大时较好
桶
基数	O(logRB)	O(logRB)	稳定	O(n)	B是真数(0-9)，R是基数(个十百)s是所选分组
堆	O(nlogn)	O(nlogn)	不稳定	O(1)	n大时较好
锦标赛
快速	O(nlogn)	O(n2)	不稳定	O(nlogn)	n大时较好
Shell	O(nlogn)	O(ns) 1<s<2	不稳定	O(1)

参考：

[1] 《数据结构》（C++语言版）（第3版） 邓俊辉  P5

[2] 《算法导论》

[3] http://en.wikipedia.org/wiki/Selection_sort

[4] 《数据结构》（C++语言版）（第3版） 邓俊辉  P63

[5]

[6]

[7]

[8] 《数据结构》（C++语言版）（第3版） 邓俊辉  P297

[9]

[10] 《数据结构》（C++语言版）（第3版） 邓俊辉  P335

[11]

[12] http://blog.csdn.net/iamfranter/article/details/6825207

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/39400513