选择排序，插入排序，冒泡排序超简单教程(能有效的区分)。Java语言描述

亦凉 2022-05-30 08:50 54阅读 0赞

首先，我相信一个东西最重要的是思想，所以，本文重点关注这三个排序背后的思想。希望能帮你理解并分清这四个排序。

> 注：n代表一组数的个数.
> 
> i 代表任意的某个数( 0 < i < n + 1).
> 
> 使用从小到大，从前到后的排序。（实际中，顺序完全可以相反，此时为了教学方便）
> 
> 前修知识：时间复杂度。 数组下标从0开始。如何交换两个数。

**目录**

1.选择排序

1.1 用具体例子说明：

1.2 排序思想

1.3 见名知意

1.4 抽象过程：

1.5 实例操作

1.6 代码实现（JAVA版本）：

1.7 代码实现（C语言版）

1.8 算法分析

1.9 拓展知识

2 插入排序

2.1 用具体例子说明

2.2 排序思想

2.3 见名知意

2. 4 抽象过程

2.5 实例操作

2.6 代码实现（JAVA版本）

2.7 代码实现（C语言版）

2.8 算法分析

拓展部分

3 冒泡排序

3.1 用具体例子说明

3.2 排序思想

3.3 见名知意

3.4 抽象过程

3.5 实例操作

3.6 代码实现（JAVA版本）

3.7 代码实现（C语言版）

拓展部分

本博客的所有源码

--------------------

![1342700879_2982.jpg][]

# 1.选择排序 #

## 1.1 用具体例子说明： ##

现在有十名同学要按身高排队。需要你的帮助。

> 1.  于是你看了一下十人，找到了其中最低的人，让他站在了第一位。
> 2.  找到剩下九人中个子最低的人，让她站在了第二位。
> 3.  找到剩下八人中个子最低的人，让它站在第三位。
> 4.  ............
> 5.  找到剩下一人中个子最低的人，让TA站在第十位。//注：我们一般省略此步。因为如果前九位是最小的九位，那么最后一位一定是最大值。
> 6.  此时完成排序，十人身高有序。

## 1.2 排序思想 ##

选择排序是最符合机器思维的一个排序，因为人们机器最喜欢做的事情就是暴力了，选择排序就是一个**简单的暴力**加上**减而治之**的思想。

## 1.3 见名知意 ##

选择排序：使用选择进行排序，每次选出最小值

## 1.4 抽象过程： ##

> 1.  对于任意一个待排序数组，从第 1 位遍历一次数组，找到最小值，使其与第 1 位交换。
> 2.  从第二位开始遍历一次数组，找到其中的最小值，使其与第二位进行交换
> 3.  一般化：从第 i 位遍历一次数组，找到第 i 小的值，使其与第 i 位交换。
> 4.  最后找到最大值，此时一定在最后一位。不需要进行交换。

## 1.5 实例操作 ##

![70][]

一般n位的数组，我们只需要遍历 n-1次即可，因为最后一位一定是最大值。

## 1.6 代码实现（JAVA版本）： ##

/**
         * Description: 选择排序JAVA语言描述
         */
        public static void selectSort(int[] a) { // 选择排序.
            int len = a.length; // 得到数组长度
            for (int i = 0; i < len; i++) {// 从第 0 位置开始找
                int min = i;
                for (int j = i + 1; j < len; j++) { // 找最小值对应的位置
                    if (a[j] > a[min])
                        min = j; // 只要比min小，就改变min的值，确保min最后保存的值为最小值的位置
                }
                exch(a, i, min); // 将找到的最小值放到合适的位置(即第 i 位置)
            }
        }

## 1.7 代码实现（C语言版） ##

TODO

## 1.8 算法分析 ##

> 1.  这个算法的复杂度约为 : N² / 2 次比较，N次交换。
> 2.  空间复杂度：只借用了常数级别的空间，可以忽略。

# 1.9 拓展知识 #

>  *  减而治之：在选排中，我们的第 i 次循环，总是从第 i 位开始，那么遍历个数为：n, n-1, n-2..........3,2.随着循环次数的增加，待遍历的个数减少，就是减而治之。也就是说：随着代码的运行，筛选范围逐个减少就是减而治之。与之相关的还有分而治之。
>  *  选择排序在所有情形下都是O(n²)的。
>  *  选择排序是所有排序中最简单，但也是思想最通用的排序，其他排序很多都有这种找出最小值后减而治之的思想。

# 2 插入排序 #

## 2.1 用具体例子说明 ##

依然是十人身高排队问题。

> 1.  让第一个人另起一排。
> 2.  让第二个人站到另起一排的合适位置。
> 3.  让第三个人站到另起一排的合适位置。
> 4.  .......
> 5.  当最后一人站到另起一排的合适位置时，排序结束， 另起的一排就是十人按身高的顺序。

## 2.2 排序思想 ##

> 插入排序：认为第一位单独为一个有序数组，将其他值挨个插入到这个有序数组中，并且始终保持有序。当其余 n - 1位插入完成，排序结束。

## 2.3 见名知意 ##

> 插入排序经典之处在于把数组排序问题转化成了新数值插入到已有的有序数组的问题。所以称之为插入排序。

## 2. 4 抽象过程 ##

> 1.  认为第一位数为一个已经排序好的数组haveSort。// 只有一个数的有序数组。
> 2.  将第二位数插入到我们逻辑中的数组 haveSort 中去，并保持逻辑数组haveSort有序。
> 3.  将第三位数插入到我们逻辑中的数组 haveSort 中去，并保持逻辑数组haveSort有序。
> 4.  ..........
> 5.  将最后一位数插入到我们逻辑中的数组 haveSort 中去，并保持逻辑数组haveSort有序。
> 6.  此时原数组与我们的逻辑数组haveSort重合，且haveSort有序，所以原数组排序结束。

注：haveSort数组不存在，只是我们在逻辑上划分出来的数组，它本质上就是原数组的前 i 位数组成的数，不过有序而已。

## 2.5 实例操作 ##

![70 1][]

## 2.6 代码实现（JAVA版本） ##

/**
         * 
         * Description: 插入排序Java代码版
         * 
         * @Title: insertSort
         * @param a 待排序数组。
         *            void
         */
        public void insertSort(int[] a) { // 插入排序
            int len = a.length; // 获得数组的长度。即外循环次数。
            for (int i = 1; i < len; i++) {
                for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
                    // 从尾部开始交换位置，直到到达合适位置。 此时插入完成。
                    exch(a, j, j - 1);  // 交换相邻的数字，实现插入。
                }
            }
        }

## 2.7 代码实现（C语言版） ##

TODO

## 2.8 算法分析 ##

时间 ：(N)~N²/2 次比较和0 ~N²/2 次交换

## 拓展部分 ##

>  *  插入排序适用于基本有序的情况，当数字基本有序时，或者数组中的每个元素距离它的最终位置都不远，排序时间就接近于线性排序.
>  *  一个有序的大数组合并一个小数组时，或者两个有序数组的合并时，使用插入排序的思想也很快可以解决。 //较常用
>  *  插入排序最坏情况是O(N²)的，但最好情形是O(n)的，数组越有序，插入排序越快.
>  *  一般对链式结点链是比较困难的一件事，我们可以使用插入排序对链式结点链进行排序.
>  *  希尔排序就是插入排序的改进版，最坏情况降低到O(N^1.5)，显著提高.但是破坏了插入排序的稳定性。

# 3 冒泡排序 #

## 3.1 用具体例子说明 ##

十个人排队。需要你的帮助，个鬼啦，不要你的帮助。

冒泡排序才是我们真正生活中使用的排队。

> 每个人都告诉后一个人：你如果比我低，请和我交换位置。
> 
> 假设大家有序从后向前询问，每3秒开始一次询问，用最多30秒，就完成了排序。
> 
>  *  第一次询问
>     
>      *  第1个人向第2个人发出请求，如果第1人比第2人高，那么交换。
>      *  第2个人向第3个人发出请求，如果第2人比第3人高，那么交换。
>      *  第3个人向第4个人发出请求，如果第3人比第4人高，那么交换。
>      *  .........
>      *  第9个人向第10个人发出请求，如果第9人比第10人高，那么交换。
>      *  第一次询问结束。此时第十个人一定是最高的身高，因为最高身高的人每次请求都进行了交换，所以到了队尾。
>  *  第二次询问
>     
>      *  第1个人向第2个人发出请求，如果第1人比第2人高，那么交换。
>      *  第2个人向第3个人发出请求，如果第2人比第3人高，那么交换。
>      *  第3个人向第4个人发出请求，如果第3人比第4人高，那么交换。
>      *  .........
>      *  第8个人向第9个人发出请求，如果第8人比第9人高，那么交换。
>      *  第二次询问结束。此时第九个人一定是第二高的身高，因为第二高身高的人每次请求都进行了交换，所以到了队尾。
>  *  第三次询问
>  *  第四次询问
>  *  ........
>  *  第九次询问
>  *  第一人一定是最低，所以不进行询问，10-1 = 9 次询问，完成排序。
> 
> 注： 说白了就是模拟真实情况下的排队，发挥每个人的力量去排序，但是计算机毕竟是单线程，所以尽可能的模拟就造成了需要多次遍历询问的结果

## 3.2 排序思想 ##

明显的看到了分而治之的影子，而且冒泡排序也是某种意义上的选择排序，每次遍历推选出最大的值，但是不同之后在于，冒泡不是直接交换最大值和最后一位，而是每次都像气泡一样，诸位询问，诸位交换。

## 3.3 见名知意 ##

这个排序就像一堆气泡，想象一下：一堆气泡，起点不同，大家同时向上奔跑，所有值，都在 "嘟嘟嘟" 的向上冒着。而跑得慢的气泡就被跑得快的气泡赶超过去。最终从上向下数去：越大的气泡位置越高，实现有序。

## 3.4 抽象过程 ##

与3.1具体例子说明相同,此处不再赘述

## 3.5 实例操作 ##

![70 2][]

## 3.6 代码实现（JAVA版本） ##

/**
         * 
         * Description: 冒泡
         * 
         * @Title: bubbleSort
         * @param a
         *            待排序数组 void
         */
        public void bubbleSort(int[] a) {
            int len = a.length; // 得到 a[] 的容量
            for (int i = 0; i < a.length; i++) { // 询问次数
                for (int j = i; j < a.length; j++) { // 进行冒泡
                    if (a[i] > a[j]) {
                        exch(a, j, i); // 不关心交换的细节、
                    }
                }
            }
        }

## 3.7 代码实现（C语言版） ##

TODO

## 拓展部分 ##

著名的堆排序就是建立在冒泡排序和二叉树上发展而来的。

最后推荐一下：[一个用动图展示排序的网站][Link 1]

其中，SEL是(select )选择排序，INS是 (insert)插入排序

# 本博客的所有源码 #

package sort;
    
    import java.util.Iterator;
    
    public class BaseSort {
        /**
         * 
         * Description: 选择排序JAVA语言描述
         * 
         * @Title: selectSort
         * @param a
         *            传入数组(排序以数组为对象，方便。) void
         */
        public void selectSort(int[] a) { // 选择排序.
            int len = a.length; // 得到数组长度
            for (int i = 0; i < len; i++) {// 从第 0 位置开始找
                int min = i;
                for (int j = i + 1; j < len; j++) { // 找最小值对应的位置
                    if (a[j] > a[min])
                        min = j; // 只要比min小，就改变min的值，确保min最后保存的值为最小值的位置
                }
                exch(a, i, min); // 将找到的最小值放到合适的位置(即第 i 位置)
            }
        }
    
        /**
         * 
         * Description: 插入排序Java代码版
         * 
         * @Title: insertSort
         * @param a
         *            待排序数组。 void
         */
        public void insertSort(int[] a) { // 插入排序
            int len = a.length; // 获得数组的长度。即外循环次数。
            for (int i = 1; i < len; i++) {
                for (int j = i; j > 0 && a[j] < a[j - 1]; j--) {
                    // 从尾部开始交换位置，直到到达合适位置。 此时插入完成。
                    exch(a, j, j - 1); // 不关心交换细节
                }
            }
        }
    
        /**
         * 
         * Description: 冒泡
         * 
         * @Title: bubbleSort
         * @param a
         *            待排序数组 void
         */
        public void bubbleSort(int[] a) {
            int len = a.length; // 得到 a[] 的容量
            for (int i = 0; i < a.length; i++) { // 询问次数
                for (int j = i; j < a.length; j++) { // 进行冒泡
                    if (a[i] > a[j]) {
                        exch(a, j, i); // 不关心交换的细节、
                    }
                }
            }
        }
    
        /**
         * Description: 传入一个数组，交换其中下标为j和i的值
         * 
         * @Title: exch
         * @param a
         * @param j
         * @param i
         *            void
         */
        private void exch(int[] a, int j, int i) {
            int t = a[j];
            a[j] = a[i];
            a[i] = t;
        }
    
    }

[1342700879_2982.jpg]: https://img-my.csdn.net/uploads/201207/19/1342700879_2982.jpg
[70]: /images/20220530/9066ba935cc74d04be7d66722f7b7239.png
[70 1]: /images/20220530/021330faf6734d7b94601e7d5457e396.png
[70 2]: /images/20220530/cd5f4418498345c6986d4818696ccadf.png
[Link 1]: https://visualgo.net/zh/sorting