常用排序算法

常用算法分类

常用算法性能分析


后三个算法中的 k 表示桶的数量

稳定/不稳定：若i<j,a[i]=a[j],排完序后a[i]与a[j]的相对位置不发生变化(即仍然i<j)，则称算法是稳定的，反之不稳定。这种特性在一些情况下还是有用的，例如对按学生姓名排好序的列表再按成绩排序时，可以保证成绩相同的学生是按照姓名排序的。
在位：如果一个算法不需要额外的储存空间（除了个别储存单元外），我们把它称为是在位的。

1、冒泡排序（Bubble Sort）

冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。
如果对n个数按从小到大排序的话，就要执行n-1趟“冒泡”操作，每执行一趟都将剩余列表中的最大值交换到最后。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void bubblesort(int *array, int length)
{
	int temp;
	//执行length-1趟"冒泡"操作
	for (int i = 0; i < length - 1; ++i) {
		//在剩余数列中对满足条件的两个数执行交换操作
		for (int j = 0; j < length - i - 1; ++j) {
			if (array[j] > array[j + 1]) {
				temp = array[j];
				array[j] = array[j + 1];
				array[j + 1] = temp;
			}
		}
	}
}

冒泡排序是一种基于蛮力法的算法，因此在处理较多的数据时，使用冒泡排序显然不是一个好的选择。通过这样可以对冒泡排序的性能进行少许提升：若在一次循环中没有进行元素交换的操作，就表示列表已经有序，可以直接结束算法了。（这样最好情况下时间复杂度就是O(n)了）

2、快速排序（Quick Sort）

快速排序是最常用的排序算法，它是基于二分思想（分治法）的一种排序，要求升序排列时；

  1. 在要排序的数列中找一个基准值（pivot）
  2. 然后将数列中小于基准值的数放到基准值左边，大于基准值的数放到基准值的右边
  3. 递归的对基准值左边和右边的数列执行上述步骤
  • 对数列6 1 2 7 9 3 4 5 10 8执行1、2步骤图示：
    注意 j 先出发




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
void quicksort(int* array, int left, int right)
{
	int i, j, t, temp;
	if (left > right)
		return;
	temp = array[left];		//设置基准值
	i = left;
	j = right;
	while (i != j) {
		//先让 j--,因为基准值在最左边，先 j-- 可以保证 i，j 相遇处的值绝对小于基准值
		while (array[j] >= temp && i < j)
			j--;
		while (array[i] <= temp && i < j)
			i++;
		if (i < j) {
			t = array[i];
			array[i] = array[j];
			array[j] = t;
		}
	}
	array[left] = array[i];
	array[i] = temp;
	quicksort(array, left, i - 1);			//排序基准值左边的数列
	quicksort(array, i + 1, right);			//排序基准值右边的数列
}
  • 算法处理过程：

快速排序之所以比较快，是因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样只能在相邻的数之间进行交换，交换的距离就大得多了。因此总的比较和交换次数就少了，速度自然就提高了。
当然在最坏的情况下（例如以两端为基准点对有序列表再次排序时），即分裂点位于数列的两端时，仍是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的；最好情况下，即分裂点在中间时，时间复杂度为O(nlogn)。
对于快速算法的优化，包括以下几个方面：

  • 更好的基准选择方法（如 三平均分区法，以最左边、最右边和中间的元素的中值作为基准值）；
  • 当子数组足够小时改用更简单的排序算法；
  • 避免递归（非递归快速排序）；

3、选择排序（Selection Sort）

选择排序也是蛮力法在排序方面的一种应用。选择排序开始时，我们扫描整个列表找到值最小的元素与第一个元素交换，然后从第二个元素开始扫描整个列表，找到最小值与第二个元素进行交换，直到从第n-1个元素开始扫描整个列表找到最小值与第n-1位元素进行交换。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
void SelectionSort(int* array, int len)
{
	int temp, minIndex;
	for (int i = 0; i < len - 1; ++i) {
		int minIndex = i;
		for (int j = i + 1; j < len; ++j) {
			if (array[minIndex] > array[j])
				minIndex = j;
		}
		temp = array[i];
		array[i] = array[minIndex];
		array[minIndex] = temp;
	}
}

无论输入的数列是怎样的，选择排序的时间复杂度都是O(n^2),然而，键的交换次数仅为O(n)。

4、插入排序（Insertion Sort）

插入排序是一种通过减一技术(减治法)实现的排序算法。

  • 减治技术利用了一个问题给定实例的解和同样问题较小实例的解之间的某种关系。一旦建立 了这种关系，我们就可以从顶至下(递归)或从底至上(非递归)地来运用该关系。

插入排序就建立了这种关系：假设一个列表的前n-1项已经有序，我们可以通过把第n项元素插入到这个较小规模的有序列表中，得到最终的有序列表。
假设当前要插入的元素为temp，我们从右到左扫描这个有序的子数组，遇到第一个小于等于temp的元素，然后把temp插入到该元素后面。

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
30
31
//插入排序
void InsertionSort(int* array, int len)
{
	int temp, preIndex;
	for (int i = 1; i < len; ++i) {
		temp = array[i];			//储存当前要向有序链表中插入的元素的值
		preIndex = i;
		while (preIndex > 0 && temp < array[preIndex - 1]) {
			array[preIndex] = array[preIndex - 1];
			preIndex--;
		}
		array[preIndex] = temp;
	}
}

//插入排序（递归）
void InsertionSort2(int* array, int len)
{
	if (len == 1)
		return;
	InsertionSort2(array, len - 1);

	int preIndex, temp;
	temp = array[len - 1];
	preIndex = len - 1;
	while (preIndex > 0 && temp < array[preIndex - 1]) {
		array[preIndex] = array[preIndex - 1];
		--preIndex;
	}
	array[preIndex] = temp;
}

在最坏情况下，temp < array[preIndex - 1]的执行次数达到最大（比如是个递减的列表(相对而言，上述代码是升序排序)），这是算法复杂度为O(n^2)。然而，对于有序数组这种最优输入，该算法有着非常好的性能。对于升序排序来说，当输入的列表为升序列表时，temp < array[preIndex - 1]只需执行n次，即时间复杂度为O(n)。因此，当输入数列基本有序时，插入排序能够有更好的性能

5、希尔排序（Shell Sort）

希尔排序又称“缩小增量排序”，希尔排序从“减少记录个数”和“序列基本有序”两个方面对直接插入排序进行了改进。在希尔排序中，对列表进行分组，对每组记录进行直接插入排序，经过几次分组之后，整个列表中的记录都“基本有序”了，这时在对整体进行一次直接插入排序。
希尔排序通过相隔某个“增量”对记录进行分组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
void ShellSort(int* array, int len)
{
	int temp, preIndex;
	//增量（grp）为1时，对整个数组进行直接插入排序，
	//此时的数列基本上是排好序的了。
	for (int grp = len / 2; grp > 0; grp /= 2) {
		//对每组进行插入排序
		for (int i = grp; i < len; ++i) {
			preIndex = i - grp;
			temp = array[i];
			while (preIndex >= 0 && array[preIndex] > temp) {
				array[preIndex + grp] = array[preIndex];
				preIndex -= grp;
			}
			array[preIndex + grp] = temp;
		}
	}
}

希尔排序只能用于顺序结构，不能用于链式结构，增量序列可以有各种取法，但应该使增量序列的值没有除1之外的公因子，并且最后一个增量的值必须为1，记录总的比较次数和移动次数比直接插入排序要少，记录个数越多，效果越明显，因此，希尔排序更适合初始记录无须、数据量较大时的情况。

6、堆排序（Heap Sort）

堆排序是一种树型选择排序，在排序过程中，将待排序序列看成一棵完全二叉树。利用完全二叉树中双亲结点与孩子结点之间的内在关系，在当前序列中选择最大（或最小）的记录。通过大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，来选择当前序列中的最大（或最小）的记录。

  • 堆的定义（1 <= i <= n/2）
    （1）ki >= k2i且ki >= k2i+1 （2）ki <= ki且ki <= ki+1
    按堆的定义将带排序序列调整为大根堆，交换r[1]与r[n],调整剩余数列为大顶堆（即只需将当前堆顶元素向下调整即可），直到堆中只剩一个元素为止。
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
30
31
32
33
34
35
36
//向下调整
void SiftDown(int *array, int n, int i)
{
	//如果当前结点至少存在一个孩子结点，比较它与孩子结点的大小
	while ((2 * i + 1) <= n) {
		int t = i;
		if (array[t] < array[2 * i + 1])
			t = 2 * i + 1;
		if ((2 * i + 2) <= n && array[t] < array[2 * i + 2])
			t = 2 * i + 2;
		//当前结点比它的孩子结点小，进行交换
		if (t != i) {
			int temp = array[t];
			array[t] = array[i];
			array[i] = temp;
			i = t;		//当前结点的索引变为t
		}
		//当前结点比它两个孩子结点的值大，结束调整
		else
			break;
	}
}
void HeapSort(int *array, int n)
{
	//（初始化堆）从最后一个非叶结点的结点开始依次进行向上调整
	for (int i = n / 2; i >= 0; --i) {
		SiftDown(array, n, i);
	}
	//将堆顶元素放到最后，并在剩余的 n-- 数内对新的堆顶元素向下调整
	while (n >= 0) {
		int temp = array[n];
		array[n] = array[0];
		array[0] = temp;
		SiftDown(array, --n, 0);
	}
}

对于堆排序，初建堆时比较次数较多，因此记录较少时不宜采用，当记录较多时较为高效。

7、归并排序（Merge Sort）

归并排序就是将两个或者两个以上的有序列表合成一个有序列表的过程。将2个有序表合成一个有序表的过程称为2-路归并。对一个有n个记录的列表进行归并排序时，可以将列表看成是n个有序的子序列，每个序列的长度为1。然后两两合并得到n/2个长度为2或1的有序子序列，再两两合并，直到得到一个长度为n的有序序列为止。
在归并时，分别从两个要归并的序列中得到最小的值，放到一个新的列表中，重复这个过程直到其中一个列表为空，然后将非空列表中的剩余部分直接复制到新列表中。

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
30
31
32
void merge(int *array, int L_left, int L_right, int R_left, int R_right)
{
	//申请一个新数组用来储存排好序的数组
	int *temp = new int[R_right - L_left + 1];
	int i = L_left, j = R_left, k = 0;
	//将两数组中的数据有序归并到temp中
	while (i <= L_right && j <= R_right) {
		temp[k++] = (array[i] < array[j]) ? array[i++] : array[j++];
	}
	//将左数组或者右数组中剩余的有序数列归并到temp中
	while (i <= L_right) {
		temp[k++] = array[i++];
	}
	while (j <= R_right) {
		temp[k++] = array[j++];
	}
	//将排好序的数列替换到原数列中
	k = 0;
	for (i = L_left; i <= R_right; ++i) {
		array[i] = temp[k++];
	}
	//释放临时开辟的空间
	delete[] temp;
}
void MergeSort(int *array, int left, int right)
{
	if (left + 1 <= right) {
		MergeSort(array, left, (right + left) / 2);
		MergeSort(array, (right + left) / 2 + 1, right);
		merge(array, left, (right + left) / 2, (right + left) / 2 + 1, right);
	}
}

用顺序表实现归并排序时，需要和待排序记录个数相等的辅助储存空间，因此空间复杂度为O(n)，归并排序可用于练市结构，且不需要附加的储存空间。

以上排序算法测试源代码： https://github.com/syfx/Sort/blob/master/Sort/Sort.cpp


 上一页

算法 最短路径 图

 评论