贡献者: 有机物
排序算法:
排序算法有很多种,例如:快速排序、归并排序、插入排序、冒泡排序、堆排序等等。
这里只介绍几种常用的排序算法:快速排序、归并排序和堆排序。
这里先介绍快速排序:
快排的主要思想是基于分治。分治的大概流程可以分为三步:分解 -> 解决 -> 合并,快排大致也是这么实现的,我们这里不详细介绍分治算法,着重讨论一下排序算法。
快速排序的期望时间复杂度为 q[i], q[j]
且
快速排序一般分为
快排与归并排序唯一一点不同的是最后不用合并,因为子数组都是原址排序的,所以不需要合并操作,数组已经有序。但归并排序的核心是合并操作。
分界点一般确定为
这里使用算法导论中的循环不变式简单的证明一下快速排序的正确性:
待证问题:while
循环结束后,q[l..j] <= mid
并且 q[j + 1..r] >= mid
。
循环不变式:q[l...i] <= mid
并且 q[j ... r] >= mid
。
需要证明这个循环不变式在第一轮迭代之前是成立的,并且在每一轮迭代后也是成立的。在循环结束之后,可以证明出待证问题。
证明:
i = l - 1, j = r + 1
。所以 q[l...i]
和 q[j ... r]
都为空,循环不变式显然成立。q[l...i - 1] <= mid, q[i] >= mid
。当对于 q[j + 1...r] >= mid, q[j] <= mid
。进行交换操作后,会使得:q[l...i] <= mid, q[j...r] >= mid
。所以再下次迭代开始之前,循环不变式同样得到保持。i >= j
,由于最后的一轮迭代中的 if 判断不一定执行,所以,只能得到:i >= j
和 q[l...i - 1] <= mid, q[i] >= mid
和 q[j + 1...r] >= mid, q[j] <= mid
。因为有:i >= j
,显然有:i - 1 >= j - 1
。根据:q[l...i - 1] <= mid,q[j] <= mid
可以得到:q[l...j] <= mid
。又因为 q[j + 1...r] >= mid
,所以问题得证。
证毕。
友情链接: 超理论坛 | ©小时科技 保留一切权利