JAVA之简单排序（冒泡、选择、插入）

版权声明：本文为 小异常 原创文章，非商用*转载-保持署名-注明出处，谢谢！
本文网址：https://blog.csdn.net/sun8112133/article/details/81346629

　　排序是数据处理中十分常见且核心的操作，虽说实际项目开发中很小几率会需要我们手动实现，毕竟每种语言的类库中都有n多种关于排序算法的实现。但是了解这些精妙的思想对我们还是大有裨益的。

　　本篇将为大家讲解三大简单排序 —— 冒泡、选择、插入。帮助大家快速理解入门。。

本文讲解三大简单排序（从小到大排序）：

　　一、冒泡排序

　　二、选择排序

　　三、插入排序

---

一、排前热身

　　先搞一个交换数组元素的方法，以供后续程序调用。

/**
 * 交换数组元素
 *  @param arr 数组
 *  @param a 数组元素下标
 *  @param b 数组元素下标
 */
public static void swap(int[] arr, int a, int b) {
    arr[a] = arr[a] + arr[b];
    arr[b] = arr[a] - arr[b];
    arr[a] = arr[a] - arr[b];
}

二、冒泡排序

　　冒泡排序的基本思想是，对相邻的元素进行两两比较，顺序相反则进行交换，这样每一趟会将最小或最大的元素 “浮” 到顶端，最终达到完全有序的状态。

1、算法原理

　　1）从第一个数据开始，与第二个数据相比较，如果第二个数据小于第一个数据，则交换两个数据的位置。

　　2）指针由第一个数据移向第二个数据，第二个数据与第三个数据相比较，如果第三个数据小于第二个数据，则交换两个数据的位置。

　　3）依此类推，完成第一轮排序。第一轮排序结束后，最大的元素被移到了最右面。

　　4）依照上面的过程进行第二轮排序，将第二大的排在倒数第二的位置。

　　5）重复上述过程，每排完一轮，比较次数就减少一次。

2、举个栗子

　　待排序数据：7, 6, 9, 8, 5,1

　　第一轮排序过程：

　　　　指针先指向7，7和6比较，6<7，交换6和7的位置，结果为：6,7,9,8,5,1

　　　　指针指向第二个元素7，7和9比较，9>7，不用交换位置，结果仍为：6,7,9,8,5,1

　　　　指针指向第三个元素9，比较9和8，8<9，交换8和9的位置，结果为：6,7,8,9,5,1

　　　　指针指向第四个元素9，比较9和5，5<9，交换5和9，结果为：6,7,8,5,9,1

　　　　指针指向第五个元素9，比较9和1，1<9，交换1和9的位置，结果为：6,7,8,5,1,9

　　　　第一轮排序结束后，最大的数字9被移到了最右边。

　　第二轮排序，过程同上，只是由于最大的9已经放在最右边了，因此不用在比较9了，少了一次比较，第二轮结束的结果为：6,7,5,1,8,9

　　第三轮结果：6,5,1,7,8,9

　　第四轮比较结果：5,1,6,7,8,9

　　第五轮比较结果：1,5,6,7,8,9

　　最终排序结果为：1,5,6,7,8,9，由上可知 N 个数据排序，需要进行 N-1轮 排序；第 i 轮排序需要的比较次数为 N-i次。

3、动图演示

4、编码思路

　　需要两层循环，第一层循环 i 表示排序的轮数，第二层循环 j 表示比较的次数。

5、代码实现

/**
 * 冒泡排序
 * @param arr
 */
public static void bubbleSort(int[] arr) {
    // 轮数（ N 个数据排序，则需要进行 N-1轮 排序）
    for (int i = 0; i < arr.length-1; i ++) {
        // 标记，如果是true，则此次循环没有进行交换，也就是待排序列已经是有序了，排序完成
        boolean flag = true;
        // 次数（第 i 轮排序需要的比较次数为 N-i次）
        // arr.length-1-i 这里的 -1表示前一个数要和后一个数比较，如果不减1，则会报数组下标越界异常
        for (int j = 0; j < arr.length-1-i; j ++) {
            if (arr[j] > arr[j+1]) {
                swap(arr, j, j+1);   // 交换
                flag = false;
            }
        }
        // 判断本轮是否进行了交换
        if (flag) {
            break;
        }
    }
}

6、算法总结：

　　N 个元素需要排序 N-1轮；

　　第 i 轮需要比较 N-i次；

　　N 个元素排序，需要比较 n（n-1）/2次；

　　冒泡排序的算法复杂度较高，为 O(n*n)。

三、选择排序

　　选择排序是对冒泡排序的改进，它的比较次数与冒泡排序相同，但交换次数要小于冒泡排序。当数据量较大时，效率会有很大的提升，但时间复杂度仍为 O(n*n)。

1、算法原理

　　1）从第一个元素开始，分别与后面的元素向比较，找到最小的元素与第一个元素交换位置；

　　2）从第二个元素开始，分别与后面的元素相比较，找到剩余元素中最小的元素，与第二个元素交换；

　　3）重复上述步骤，直到所有的元素都排成由小到大为止。

2、举个栗子

　　待比较数据：7, 6, 9, 8, 5,1

　　第一轮：此时指针指向第一个元素7，找出所有数据中最小的元素，即1，交换7和1的位置，排序后的数据为：1,6,9,8,5,7

　　第二轮：第一个元素已经为最小的元素，此时指针指向第二个元素6，找到6,9,8,5,7中最小的元素，即5，交换5和6的位置，排序后的结果为：1,5,9,8,6,7

　　第三轮：前两个元素为排好序的元素，此时指针指向第三个元素9，找到9,8,6,7中最小的元素，即6，交换6和9的位置，排序后的结果为：1,5,6,8,9,7

　　第四轮：前三个元素为排好序的元素，此时指针指向第四个元素8，找到8,9,7中最小的元素，即7，交换8和7的位置，排序后的结果为：1,5,6,7,9,8

　　第五轮：前四个元素为排好序的元素，此时指针指向第五个元素9，找到9,8中最小的元素，即8，交换9和8的位置，排序后的结果为：1,5,6,7,8,9

　　到此，全部排序完成。

　　分析： 从上面的原理可以看出，与冒泡排序不同的是，选择排序每排完一轮都把最小的元素移到了最左边；与冒泡排序相同的是，下一轮排序的比较次数比上一轮减少一次，N 个数据比较大小，需要排序 N-1轮，第 i 轮排序需要比较 N-i次。

3、动图演示

4、编码思路

　　需要两次循环，第一层循环 i 表示每轮指针指向的位置，将最小值 min 初始化为第 i 个元素，第二层循环从 j=i+1 开始，分别与 min 比较，如果小于 min，则更新 min 的值，内层循环结束后；交换 min 元素和第 i 个元素的位置。以此类推进行下一轮循环，直到 i=length 时停止循环。当 i=length 时，说明小的元素已经全部移到了左面，因此无需进行内层循环了。

5、代码实现

/**
 * 选择排序
 * @param arr
 */
public static void selectSort(int[] arr) {
    // 每轮指针指向的位置
    for (int i = 0; i < arr.length - 1; i ++) {
        int min = i;       // 用于存放本轮中最小元素的数组下标
        // 从指针指向的下一个位置开始 i+1
        for (int j = i + 1; j < arr.length; j++) {
            // 与最小元素比较，如果当前元素比最小元素小，则记录一下
            if (arr[j] < arr[min]) {
                min = j;
            }
        }
        // 进行交换，如果min发生变化，则进行交换
        if (min != i) {
            swap(arr, min, i);
        }
    }
}

6、算法总结：

　　N 个元素需要排序 N-1轮；

　　第 i 轮需要比较 N-i次；

　　N 个元素排序，需要比较 n(n-1)/2次；

　　选择排序的算法复杂度仍为 O(n*n)；

　　相比于冒泡排序，选择排序的交换次数大大减少，因此速度要快于冒泡排序。

四、插入排序

　　插入排序是简单排序中最快的排序算法，虽然时间复杂度仍然为 O(n*n)，但是却比冒泡排序和选择排序快很多。

1、算法原理

　　1）将指针指向某个元素，这个元素的左侧假设全部有序，先将该元素抽取出来，然后按照从右往左的顺序分别与其左边的元素比较，遇到比其大的元素便将其大的元素右移，直到找到比该元素小的元素或者找到最左面发现其左侧的元素都比它大，停止；

　　2）此时会出现一个空位，将该元素放入到空位中，使得该元素左侧的元素都比它小，右侧的元素都比它大；

　　3）指针向后移动一位，重复上述过程。每操作一轮，左侧有序元素都增加一个，右侧无序元素都减少一个。

2、举个栗子

　　待比较数据：7, 6, 9, 8, 5,1

　　第一轮：指针指向第二个元素6，假设6左面的元素为有序的，将6抽离出来，形成7,空,9,8,5,1，从7开始，6和7比较，发现7>6。将7右移，形成空,7,9,8,5,1，6插入到7前面的空位，结果：6,7,9,8,5,1

　　第二轮：指针指向第三个元素9，此时其左面的元素6,7为有序的，将9抽离出来，形成6,7,空,8,5,1，从7开始，依次与9比较，发现9左侧的元素都比9小，于是无需移动，把9放到空位中，结果为：6,7,9,8,5,1

　　第三轮：指针指向第四个元素8，此时其左面的元素6,7,9为有序的，将8抽离出来，形成6,7,9,空,5,1，从9开始，依次与8比较，发现8<9，将9向后移，形成6,7,空,9,5,1，8插入到空位中，结果为：6,7,8,9,5,1

　　第四轮：指针指向第五个元素5，此时其左面的元素6,7,8,9为有序的，将5抽离出来，形成6,7,8,9,空,1，从9开始依次与5比较，发现5比其左侧所有元素都小，5左侧元素全部向右移动，形成空,6,7,8,9,1，将5放入空位，结果5,6,7,8,9,1。

　　第五轮：同上，1被移到最左面，最后结果：1,5,6,7,8,9。

3、动图演示

4、编码思路

　　需要两层循环，第一层循环 index 表示上述例子中的指针，即遍历从坐标为1开始的每一个元素；
　　第二层循环从 leftindex=index-1 开始，leftindex-- 向左遍历，将每一个元素与 index 处的元素比较，直到 leftindex 处的元素小于 index 处的元素或者 leftindex<0；遍历从 index 到 leftindex 的每一个元素使其右移，最后将 index 处的元素放到 leftindex+1 处的空位处。

5、代码实现

/**
 * 插入排序
 */
public static void doInsertSort(int[] arr){
    // 指针位置，从1开始，用于比较对象的元素下标
    for (int index = 1; index < arr.length; index ++) {
        int temp = arr[index];     // 用于比较的数据
        int leftindex = index - 1;
        // 当比到最左边或者遇到比 temp 小的数据时，结束循环
        while (leftindex>=0 && arr[leftindex]>temp) {
            arr[leftindex+1] = arr[leftindex];
            leftindex --;
        }
        arr[leftindex+1] = temp;   // 把 temp 放到空位上
    }
}

6、算法总结：

　　时间复杂度，由于仍然需要两层循环，插入排序的时间复杂度仍然为 O(n*n)。

　　比较次数：在第一轮排序中，插入排序最多比较一次；在第二轮排序中插入排序最多比较二次；以此类推，最后一轮排序时，最多比较 N-1次，因此插入排序的最多比较次数为 1+2+...+N-1=N*(N-1)/2。尽管如此，实际上插入排序很少会真的比较这么多次，因为一旦发现左侧有比目标元素小的元素，比较就停止了，因此，插入排序平均比较次数为 N*(N-1)/4。

　　移动次数：插入排序的移动次数与比较次数几乎一致，但移动的速度要比交换的速度快得多。

　　综上，插入排序的速度约比冒泡排序快一倍（比较次数少一倍），比选择排序还要快一些，对于基本有序的数据，插入排序的速度会很快，是简单排序中效率最高的排序算法。