c++ - 最简单的冒泡排序

Question

假设我想对一个大小为 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]);

（我只是想知道它是否正确，我不在乎效率低下）

Answer 1

是的，这是正确的。证明可以按照以下思路构建。

总是当 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 成立，这正是我们所承诺的在第一段中证明。

Answer 2

降序排序是不正确的..

想一想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.