排序 - 交换排序 [1 - 冒泡排序] + 简单选择排序。。

电玩女神 2022-10-02 03:53 227阅读 0赞

我特别喜欢“傻”文章。

这篇有点长，因为包括了两个算法，冒泡和简单选择排序。你可以分开看。各用20分钟足够。不够的话你找我。

这篇说说冒泡排序，这是一个很经典的算法，如果你没听过，相信你是一个极品程序员。

你或许知道算法的原理，但你能把他描述的很清楚吗？让我来试一试。

冒泡算法，举例来说：

要排序的数据为 \{6, 3, 7, 9, 2\}

冒泡排序简单地说就是逐渐选出最大的那个值，把他放在最后面，然后找出从第一个到第 size - 1 个元素中最大的，放到倒数第二位，以此类推。

冒泡排序是分几趟完成的，首先我们来看在每趟中都做哪些动作，从第一趟开始。

第一趟会这么做：

\{ 6, 3, 7, 9, 2\},  6 和 3 进行比较，6 > 3 成立，则交换；

\{3,  6, 7, 9, 2\}, 6 和 7 进行比较，6 > 7 不成立，则不交换；

\{3, 6,  7, 9, 2\}, 7 和 9 进行比较，7 >9 不成立，则不交换；

\{3, 6, 7,  9, 2\}, 9 和 2 进行比较，9 > 2 成立，则交换；

\{3, 6, 7, 2, 9\}. 对于5个元素的数组，我们做了4次比较后，一趟冒泡完成。

接着第二趟怎么做呢？因为 9 是第一趟中选出的最大的，已经放到了最后。

那么第二趟其实就不需要对9进行比较了，第二趟关心的元素是： \{3, 6, 7, 2\}

第二趟会这么做：

\{ 3, 6, 7, 2\}, 3 和 6 进行比较，3 > 6 不成立，则不交换；

\{3, 6, 7, 2\}, 6 和 7 进行比较，6 > 7 不成立，则不交换；

\{3, 6, 7, 2\}, 7 和 2 进行比较，7 > 2 成立，则交换；

\{3, 6, 2, 7\}。 对于4个元素的数组，我们做了3次比较后，第二趟冒泡完成，此时结果为 \{3, 6, 2, 7, 9\}

第三趟要关心的数据是\{3,6,2\}，具体过程就不详细说了，第三趟排序的结果是：\{3, 2, 6\}; 总结果为：\{3, 2, 6, 7, 9\}

第四趟要关心的数据是\{3,2\}，第四趟排序的结果是：\{2,3\};

第五趟要关心的数据是\{2\}，咦？只有一个元素怎么排序呢？对的，我们在第一节直接插入排序时就说了，

只有一个元素的序列就是有序的，所以我们可以忽略第五趟。

我们也可以得出一个结论，对于5个元素的数组，排序需要4趟，推广后，对于n个元素的数组，排序需要n-1趟。

public static void bubbleSort(int[] toSort) {
        int size = toSort.length;
        
        // 外层循环，代表冒泡的趟数
        // 共有size个元素，则需要 size - 1 趟冒泡
        for (int i = 0; i < size - 1; i++) {
          
          // 因为每趟冒泡都会把最大的放到后面
          // 而接下来的那趟就可以少考虑一个元素
          // 对于每趟冒泡，我们做比较的次数为：（无序数组元素个数 - 1）
          // 
          // size - i, 就是无序数组的个数
          // size - i - 1 就是要做的比较的次数
          for (int j = 0; j < size - i - 1; j++) {
            
            // 总是跟相邻的元素比较，如果大于下一个，则交换
            if (toSort[j] > toSort[j + 1]) {
              int tmp = toSort[j];
              toSort[j] = toSort[j + 1];
              toSort[j + 1] = tmp;
            }
          }
        }
      }

复杂度:

时间复杂度：O(n^2)

\---------------------

我想把简单选择排序也写到这儿，因为我常常把这两种算法弄混了，写到这儿好做比较。

简单选择排序：

在冒泡排序中，是每个元素都跟相邻的元素进行比较，如果下一个元素大于当前，就交换，一趟完成后，就可以把最大的数字放到最后；

简单选择排序，是每趟都先把无序数组中最大的元素找出来，然后把他和无序数组中最后一个元素进行交换，注意这里明显的区别就是：

简单选择排序中，每趟最多进行一次交换。

举例来讲：要排序的数据为 \{6, 3, 7, 9, 2\}

第一趟这么做：

找到这组数据中最大的元素，我们发现他是 9， 那么他跟最后一个元素（下标为4，数值为2）进行交换，交换后得到： \{6, 3, 7, 2, 9\}

第二趟：因为最大的 9 已经放到末尾了，无序的数组为 \{6, 3, 7, 2\}。

找到这组数据中最大的元素，我们发现他是 7， 那么他跟最后一个元素（下标为3，数值为2）进行交换，交换后得到： \{6, 3, 2, 7\}

第三趟：无序数组为\{6, 3, 2\}, 最大的元素为6，那么他跟最后一个元素（下标为2，数值为2）进行交换，得到：\{2, 3, 6\}

第四趟：无序数组为\{2, 3\}, 啊？这已经有序了啊，怎么还排序？是的，这是一种特殊情况，假如我们最开始的数组是\{6, 2, 7, 9, 3\}的话，你会发现进行到这一步的时候，无序数组为\{3,2\}，所以这一步是必须的，但这一步最大的元素是3，最后一个元素也是他本身，所以不需要进行交换；

第五趟，就只有一个元素了，不用进行排序了。

是不是跟冒泡神似？你可能会说no，嗯反正我是弄混了。

其实还有一点，冒泡排序的重点在于找到最大值的下标，因为我们最终交换的时候是把最大值的下标所指向的数值跟最后一个元素的数值进行交换。

那如何找最大值的下标呢？

思路是这样的：

我们需要做一趟比较来找到最大值的下标。

在这一趟循环中，去比较：

第一个元素跟所有的元素的值，

如果其他元素大于这个元素了，就把他的下标记下来，

再拿这个较大元素去跟剩下的比，比完一圈就找到最大的了。

还是例子清楚：

对于\{6, 3, 7, 9, 2\}来讲，我们先假设最大值的下标为0，（很明显，这是错误的，但这是我们的开端）。

这趟比较从 1 开始。

下标为0的值为6，下标为1的值为3. 6 < 3吗？否，则比较下一个元素；

下标为2的值为7，6 < 7 吗？是，则把7的下标记下来：2；接下来我们就用7去跟剩下的比较了；

下标为3的值为9, 7 < 9 吗？是，则把9的下标记下来：3；接下来我们就用9去跟剩下的比较了；

下标为4的值为2, 9 < 2 吗？否。比较完成。

最后记下来的下标为3. 即这个数组中最大值的下标为3.

Java算法如下：

public static void selectionSort(int[] toSort) {
        int size = toSort.length;
        for (int i = 0; i < size - 1; i++) {
          int maxIndex = getMaxIndex(toSort, size - i);
          
          // size - i - 1 是无序数组的最后一个元素
          // 如果最后一个元素就是最大值，那么就不用交换了。
          if (size - i - 1 == maxIndex) {
            continue;
          }
          
          
          int tmp = toSort[size - i - 1]; // last unsorted element
          toSort[size - i - 1] = toSort[maxIndex];
          toSort[maxIndex] = tmp;
        }
      }
      
    	private static int getMaxIndex(int[] toSort, int len) {
    	  // 先把最大值元素的下标记为0
    	  int maxIndex = 0;
    	  
        for (int i = 1; i < len; i++) {
          // tmp中永远都是存当前的最大值
          int tmp = toSort[maxIndex];
          if (tmp < toSort[i]) {
            // 注意：当发现有更大的值的时候，我们改变了maxIndex！
            // 正因如此，maxIndex才能保证是最终的最大值的索引
            maxIndex = i;
          }
        }
        return maxIndex;
      }

简单选择排序的时间复杂度：O(n^2)

下一篇我们讨论冒泡排序的改进算法：快速排序