简单选择排序（超全面）

1什么是气泡排序？

气泡排序英语 Bubble Sort ，是最基本的 交换排序 它被称为气泡排序，因为每个元素都可以像一个小气泡一样，根据自己的大小一点一点地移动到数组的一侧。

气泡分选原理：

每次旅行只能返回一个号码。也就是说，第一次行程只能确定最后一个位置上的数字，第二次行程只能是最后一次。 2 返回位上的数字，以此类推 n 通过简单地放置 n-1 数字返回，即执行 n-1 趟操作。

而 “每一趟 ” 两者都需要从第一位开始比较两个相邻的数字，将较大的数字放在后面，比较后向后移动一个位置，继续比较下面的两个相邻数字，重复此步骤，直到最后一个数字没有返回。

2气泡排序到底是如何排序的？

让我们看看气泡排序如何在移动图表中移动。

它到底是怎么移动的？此处提供参考。(漂亮的气泡分类)

（1)开始时，左下标指向第一块石头，右下标指向第二块石头，然后比较

（2)则左下标和右下标同时向右移动并再次比较。

（3第一次旅行后，最大的石头移到了最右边。

（4)下一个 3 继续从尚未排列整齐的石头中选择最大的。规则同上。

（5)如下所示 4 鹅卵石的完整演示过程

3，时间复杂性

从上图可以看出，4 有必要安排一块石头的订单。 3 行程，需要比较第一次行程3其次，第二次旅行需要进行比较。2第三次旅行需要进行比较。1其次，这是一个全面的比较 3 + 2 + 1 次；

那如果有 n 石头在哪里？

那就需要 (n-1) + (n-2) +…+2+1 其次，这不是一个算术级数吗

根据复杂性规则，去除低阶项（即。 n/2）,去掉常数系数，这就是复杂性。 O(n^2)了；

气泡排序也是 稳定排序 因为当两个数字交换时，如果两个数字相同，它们不会因为算法中的哪个语句而相互交换位置。

4，冒泡排序代码原始版本。

//根据刚才的移动图表
//冒泡排序两个比较的元素是尚未排序的元素。--->
public void bubbleSort(int[] array){
    for(int i=0;i array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
    }
}

疑问环节

小花 ：第一层循环用于控制通过次数，即。 n 应比较数字 n-1 旅行能否具体回答第二个循环？

小明：第二层是控制层 i+1 跳闸（因为在回路中 i 是从 0 开始的比较数），然后 i+1 这次旅行是一次比较。 N-1-i 次

小花 ：还不是很清楚，你能用图形给我描述一下吗？

小明 当然，我可以通过几张图片向你解释。

小花 ：这很清楚，但如果遇到以下情况怎么办？换句话说，当执行最后三轮时，发现整个序列已经有序。如果算法可以按照上述代码执行，算法仍然会“认真地”继续执行第七和第八轮。这可以优化吗？

小明 ：当然，它可以优化。如果我们能够判断序列是有序的并对其进行标记，那么剩余的几轮排序可以在不执行的情况下提前完成。

小花 ：那么如何优化上述代码以获得这种效果呢？

小明 ：其实也很简单，就是对上面的代码做一点改动，也就是使用 布尔变量 isSorted 作为标记。如果在这一轮排序中有元素交换，则该序列是无序的。

5，冒泡排序代码优化版本

public static int[] bubbleSort(int[] arr) {
     if (arr == null || arr.length < 2) {
          return arr;
     }
    for (int i = 0; i < arr.length - 1; i++) {
         boolean isSorted  = true;//有序标记，每轮初始true
         for (int j = 0; j < arr.length -i - 1; j++) {
             if (arr[j + 1] < arr[j]) {
                 isSorted  = false;//存在元素交换，因此不有序，标签变得false
                 int t = arr[j];
                 arr[j] = arr[j+1];
                 arr[j+1] = t;
             }
         }
         //无论是在一次旅行后发生换位，如果没有换位，都会直接跳出大循环。
         if(isSorted )
              break;
     }
     return arr;
}

小花 是的，我还有一个问题。如果系列的前半部分是无序的，下半部分是有序的呢？这样(3，4，2，1，5，6，7，8)这个数组，其实下面的很多元素已经是有序的了，但是每一轮还是徒劳地进行了多次比较？例如：

第一轮：

元素 3 和元素 4 比较，3 大于 4，因此位置保持不变。

接着元素 4 和元素 2 比较，4 大于 2，所以 4 和 2 交换

接着元素 4 和元素 1 交换

然后我发现，下面实际上是一个有序的系列，但我仍然要相互比较，因此多次比较都是徒劳的。

第二轮：

元素 3 和元素 2 比较，3 大于 2，所以 3 和 2 交换

元素 3 和 1 比较发现 3 大于 1，所以 3 和 1 交换

然后我发现，下面实际上是一个有序的系列，但我仍然要相互比较，这也是很多次。

小明 对于您上面提出的问题，关键在于定义本系列的有序区域。如果使用冒泡排序代码的原始版本进行分析，则有序区域的长度和排序的轮数相等。例如，第一轮排序后有序区域的长度为1，第二轮排序后有序区域的长度为2 ……。

然而，在第二轮之后，实际序列的实际有序区域可能大于该长度，即上面的示例。 5 事实上，它们都属于有序区域。因此，后一种比较是没有意义的。

我们可以这样做来避免这种情况：在每一轮排序结束时，记录最后一个元素交换的位置，这是无序序列的边界，然后是有序区域。

6，气泡排序代码升级

public static int[] bubbleSort(int[] arr) {
     if (arr == null || arr.length < 2) {
          return arr;
     }
    //记录上次交换的位置
    int lastExchangeIndex = 0;
    //无序序列的边界，每次比较只需要在此进行比较。
    int sortBorder = arr.length - 1;

    for (int i = 0; i < arr.length - 1; i++) {
         boolean isSorted  = true;//有序标记，每轮初始true
         for (int j = 0; j < sortBorder; j++) {
             if (arr[j + 1] < arr[j]) {
                 isSorted  = false;//存在元素交换，因此不有序，标签变得false
                 int t = arr[j];
                 arr[j] = arr[j+1];
                 arr[j+1] = t;
                 lastExchangeIndex = j;
             }
         }
        sortBorder = lastExchangeIndex
         //无论是在一次旅行后发生换位，如果没有换位，都会直接跳出大循环。
         if(isSorted )
              break;
     }
     return arr;
}

---