冒泡排序和选择排序有什么区别？

Question

冒泡排序和选择排序中哪个更快，为什么？两者是否同样有效？

- algo-geeks

---

你是不是正在参加考试或者在做一份可带回家的试卷之类的，并且使用手机？拜托，专心点。 - jason

没有。这个问题是在我的面试中问我的。我说它们是冒泡排序。因为在冒泡排序中，连续的元素被比较，它们存储在相邻的内存位置中，所以它需要更少的时间。你有什么意见吗？ - algo-geeks

同样低效的两者都是 - marc_s

这是我上学期考试的内容。 - BoltClock

这是一个糟糕的面试问题。它并没有提供任何大学成绩单没有提供的信息（这个问题只能得出你在基础计算机科学课程中是否有过脉搏）。我认为，“为工业招聘程序员”应该成为计算机科学学位的必修课程。 - jason

Answer 1

维基百科（强调添加）说：

在简单平均情况下，Θ(n²)算法中，选择排序几乎总是优于冒泡排序和侏儒排序，但通常不如插入排序。插入排序非常相似，因为在第k次迭代之后，数组中的前k个元素按顺序排列。插入排序的优点在于它只扫描所需的元素数量以放置第k + 1个元素，而选择排序必须扫描所有剩余元素以找到第k + 1个元素。简单计算表明，插入排序通常执行的比选择排序少约一半的比较，尽管它可以执行相同数量或更少的比较，具体取决于排序之前数组的顺序。对于某些实时应用程序来说，选择排序的优点在于无论数组的顺序如何，都会执行相同的操作，而插入排序的运行时间可能会有很大差异。然而，如果数组已经排序或“接近排序”，则这通常是插入排序的优势，因为它运行得更高效。虽然从写入次数（Θ(n)交换与Ο(n²)交换）的角度来看，选择排序优于插入排序，但在循环排序中，它几乎总是远远超过（并且从未打败）写入次数，因为循环排序在写入次数上理论上是最优的。如果写入比读取昂贵得多，例如使用EEPROM或Flash存储器，其中每次写入都会缩短存储器的寿命，则这可能很重要。最后，在较大的数组上，Θ(n log n)分治算法（如归并排序）远远优于选择排序。但是，对于小数组（即少于10-20个元素），插入排序或选择排序通常更快。在实践中的一个有用的优化是，对于“足够小”的子列表，切换到插入排序或选择排序。

维基百科对冒泡排序的描述（强调添加）：

冒泡排序的最坏和平均时间复杂度都为O(n²)，其中n是被排序的项数。存在许多具有明显更好的最坏或平均复杂度（O(n log n)）的排序算法。即使是其他的O(n²)排序算法，例如插入排序，也往往比冒泡排序的性能更好。因此，当n很大时，冒泡排序不是一种实用的排序算法。

冒泡排序仅在一个重要方面优于大多数其他实现，甚至快速排序，但不包括插入排序，那就是它能够有效地检测到列表已经排序。冒泡排序在已排序列表上的表现（最佳情况）为O(n)。相比之下，大多数其他算法，即使是那些具有更好平均复杂度的算法，也要在集合上执行其整个排序过程，因此更为复杂。然而，插入排序不仅也有这个机制，而且在列表已经部分排序（具有少量逆序对）的情况下表现更好。

- Cody Gray

---

这道题目没有提到插入排序。 - Nello

Answer 2

相较于冒泡排序，选择排序进行更少的交换；因此，尽管两种排序方法都是O(N²)的，选择排序执行起来更快、更高效！

- isharailanga

Answer 3

比较这两种算法时，我们需要考虑这两种算法所进行的两个操作： i)比较 ii)交换 基于比较操作，这两种算法同样有效； 但是如果你考虑交换操作，你会发现选择排序更有效率。 考虑一个大小为100的按降序排列的数组，我们需要将它们按升序排序。 对于这个问题，在冒泡排序中需要进行100*100=(10000)大约的交换操作，而在选择排序中只需进行100次交换操作，因为在每次迭代中只会进行一次交换操作。

- user9345613

Answer 4

我似乎无法在这里或其他地方找到一个令人满意的解决方案，尽管 Senthil 的 link 正朝着正确的方向前进。

一开始这个问题让我感到困惑，因为冒泡排序可以通过在子数组（或链表等）经过一次未执行值交换的传递后提前终止外部循环来进行优化。选择排序不能通过这种方式帮助，那么为什么它会表现得更好呢？两者在一般用途中都比较弱 - O(n^2) - 那么为什么至少可以稍微改进的那个不是更好呢？

答案纯粹基于我自己和其他实现的检查，即冒泡排序在每个比较命中时都会进行值交换（读取、写入、写入）。选择排序只是记录新的边界值（升序排序为最小值，降序排序为最大值），然后在传递结束时进行交换。

void swapInt(int *ptr1, int *ptr2) {
   int temp;

   temp = *ptr1;
   *ptr1 = *ptr2;
   *ptr2 = temp;
}

/* compare and swap over a shrinking sub-array */
void bubbleSortArray(int a[], const int aSize) {
   int unsorted, i, iMax = (aSize - 1);

   do {
      unsorted = 0;
      for (i = 0; i < iMax; i++) {
         if ( a[i] > a[i + 1] ) {
            unsorted = 1;
            /* swap every time comparison is true */
            swapInt(&a[i], &a[i + 1]);
         }
      }
      --iMax;
   } while (unsorted);
}

/* compare to find min value, write it before shrinking the sub-array */
void selectSortArray(int a[], const int aSize) {
   int i, j, mindex;

   for (i = 0; i < (aSize - 1); i++) {
      mindex = i;
      for (j = (i + 1); j < aSize; j++) {
         if ( a[j] < a[mindex] ) mindex = j;
      }
      /* swap after inner loop terminates */
      swapInt(&a[i], &a[mindex]);
   }
}

- ccy

Answer 5

冒泡排序算法被认为是最简单和效率最低的算法，但选择排序算法与冒泡排序相比更加有效。冒泡排序还需要消耗额外的空间来存储临时变量，并且需要进行更多的交换操作。

- Soner from The Ottoman Empire

---

我对声称冒泡排序需要更多的临时变量空间提出异议。选择排序中，也需要使用一个临时变量来存储最小或最大值。这不是同样占用了空间吗？ - Jonathan Komar

我也不明白为什么冒泡排序需要额外的空间来存储临时变量？ - Vikas Satpute

我遇到了额外空间需求的问题，但是通过巧妙的编程，您可以规避额外的空间要求。 - Albert

Answer 6

尽管它们的最坏、最好和平均情况下的复杂度相当，但有一些方面表明选择排序比冒泡排序更好。

选择排序大部分时间都在试图找到“未排序”部分中的最小元素。这清楚地显示了选择排序和冒泡排序之间的相似性。冒泡排序在每个阶段“选择”剩余的最大元素，但浪费了一些精力来为“未排序”的部分赋予一定的顺序。

- Senthil Kumaran

Answer 7

在冒泡排序中，我们需要更多的比较和交换。

在一个由10个元素组成的数组中，在第一次通过中有9次比较，在第二次通过中有8次比较，7次、6次等等。而且在每次8或9次比较中，我们只能交换一个元素。

相比之下，在选择排序中，我们先找到所有元素中的最小元素，并将其放置在元素的0索引处。

这两种算法的复杂度都是O(n2)，但在最坏的情况下，冒泡排序的复杂度为O(n2)，选择排序的复杂度为O(n2)；在最好的情况下，冒泡排序的复杂度为O(n)，选择排序的复杂度为O(n2)。

- Imdad abro

Answer 8

冒泡排序使用更多的交换次数，而选择排序避免了这种情况。

当使用选择排序时，最多交换n次。但是当使用冒泡排序时，它几乎要交换n*(n-1)次。显然，在内存中，读取时间比写入时间少。比较时间和其他运行时间可以忽略不计。因此，交换次数是问题的关键瓶颈。

- akhil