假设我想对一个大小为 n 的整数数组进行排序。假设我有交换方法
我的这种冒泡排序实现正确吗?
for(int i=0;i<n;i++)
for (int j=0;j<n;j++)
if (array[i]<array[j]) swap(array[i], array[j]);
(我只是想知道它是否正确,我不在乎效率低下)
是的,这是正确的。证明可以按照以下思路构建。
总是当 j 循环(内部)完成时(所以 j=n,i 将作为下一个操作增加),然后 a[i] 是最大值,a[i] 之前的部分按升序排列(下面的证明) . 因此,当外部循环即将以 i=n-1 完成时,a[i] 为最大值,并且直到索引 i 的项目都是有序的(并且因为前面的项目都没有大于最大值)所以整个数组被订购。
要证明在 j 循环之后 a[i] 始终是最大值很简单:当 j 循环时 i 没有变化,如果 j 遇到大于 a[i] 的项目,那么将其带到 a[i] 并且因为j 扫描了整个数组,它不可能包含大于 a[i] 的元素。
证明直到 i 的项目是有序的是完全归纳。我们将使用上面关于 a[i] 为最大值的陈述。
对于 i=0 微不足道的(没有前面的元素)。a[0] 是最大值并且“它是有序的”。
i=1(只是为了好玩):1 个项目到了 a[0](不要关心它的值,它不能大于 max),并且 a[1] 是最大值。所以 a[0..1] 排序。
现在,如果在以 i=k 结束的 j 循环之后满足这些命题,则会发生以下情况:
i <- k+1
假设当前项 a[i]=q。
j 将 a[] 扫描到 k。由于 k 是最大值,它将被交换为 i。超出我的项目还没有被打扰。所以基本上 max 向上移动了一个,所以一个项目,特别是 q 被添加到数组的第一部分。让我们看看如何:
j 扫描到 max 的排序部分,直到它在索引 m 处找到大于 a[i] 的项目。(它会在最坏的情况下找到 a[i-1]。)直到 m 的项目被排序。现在将在此处插入 a[i],范围 [m..i-1] 中的所有项目将向上移动一个。由于 m 是插入 a[i] 的正确位置,因此 a[0..i] 将在移动后排序。现在唯一要证明的是 [m..i] 中的 j 循环确实执行了移动:
开始时序列 a[i],a[m..i-1] 是有序的,因此此区间内的每次比较都会触发交换:a[i] 始终是 a[j..i] 中最小的部分。交换(i 与 j)将使第 j 个位于正确的位置(前面的最小项目),并且 j 进入间隔的剩余部分。
所以 j 达到 i=k+1 (这里没有交换)并且 a[k+1] 是最大的,所以在这个 j 循环中没有更多的交换,所以最后 a[0..k+1] 被排序。
所以最后,如果这些论点对于 i=k 成立,那么它们在 j 循环之后对于 i=k+1 成立。我们确定它们在 1 个 j-loop 之后对于 i=0 成立,并且从 i-loop 表明总共会有 n 个 j-loop 所以这些论文对于 i=n-1 成立,这正是我们所承诺的在第一段中证明。
降序排序是不正确的..
想一想array = [2, 1]
,它输出[1, 2]
您可以通过更改j=0
为j=i+1
for(int i=0;i<n;i++)
for (int j=i+1;j<n;j++)
if (array[i]<array[j]) swap(array[i], array[j]);
但是对于升序排序是正确的。
这里简单证明:
假设在我们有循环输出的每一步之后a[0] <= a[1] <= ... <= a[i-1] <= a[i]
,我们称之为假设_i
假设_i是对的i = 0
如果假设_i对于0 <= i < M <= N是正确的。什么时候i = M
,我们有a[0] <= a[1] <= ... <= a[M - 2] <= a[M - 1]
。j
在从 0 到 M 的内循环之后,我们得到a[0] <= a[1] <= ... <= a[M - 2] <= a[M - 1] <= a[M]
. 当从 M+1 继续内循环j
到 N - 1 时,a[M] 会变得更大。所以假设_i也适用于i = M
.