八大排序（一）：四种简单的排序（直接插入排序、希尔排序、冒泡排序、选择排序）

港控/mmm° 2022-05-25 02:16 52阅读 0赞

源码地址：  
[https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A0%81/Sort.java][https_github.com_TimePickerWang_aimed-at-offer_blob_master_java_E6_BA_90_E7_A0_81_Sort.java]

## 一、直接插入排序 ##

直接插入排序基本思想是每一步将一个待排序的记录，插入到前面已经排好序的有序序列中去，直到插完所有元素为止。  
直接插入排序算法的运作如下：  
假设有一组无序序列 R0, R1, … , RN-1。  
(1) 我们先将这个序列中下标为 0 的元素视为元素个数为 1 的有序序列。  
(2) 然后，依次把 R1, R2, … , RN-1 插入到这个有序序列中。所以，我们需要一个外部循环，从下标 1 扫描到 N-1 。  
(3) 接下来描述插入过程。假设这是要将 Ri 插入到前面有序的序列中。由前面所述，我们可知，插入Ri时，前 i-1 个数肯定已经是有序了。  
所以我们需要将Ri 和R0 ~ Ri-1 进行比较，确定要插入的合适位置。这就需要一个内部循环，我们一般是从后往前比较，即从下标 i-1 开始向 0 进行扫描。

结合下图可以更直观的理解  
![这里写图片描述][70]

直接插入排序：

public float[] insertSort(float[] array) {
            int j;
            for (int i = 1; i < array.length; i++) {
                j = i - 1;
                float temp = array[i];
                while (j >= 0 && array[j] > temp) {
                    array[j + 1] = array[j];
                    j--;
                }
                array[j + 1] = temp;
            }
            return array;
        }

当数据正序时，执行效率最好，每次插入都不用移动前面的元素，时间复杂度为O(N)。  
当数据反序时，执行效率最差，每次插入都要前面的元素后移，时间复杂度为O(N\*2)。

## 二、希尔排序 ##

希尔排序跟直接插入排序很相似，其实对比下代码就知道就是在直接插入排序的基础上增加了一个分组的功能。结合下图理解一下：

![这里写图片描述][70 1]

在上面这幅图中，有一个大小为 10 的无序序列：  
第一趟排序中，通过计算gap1=N/2（即10/2），将10个元素分为5组，即（9,4），（1,8），（2,6），（5,3），（7,5），然后对每组内的元素进行插入排序。  
第二趟排序中，把上次的 gap 缩小一半，即 gap2 = gap1 / 2 = 2 (取整数)。这样每相隔距离为 2 的元素组成一组，可以分为 2 组。分组后依旧对每组的元素进行插入排序。  
第三趟排序中，再次把 gap 缩小一半，即gap3 = gap2 / 2 = 1。 这样相隔距离为 1 的元素组成一组，即只有一组。再进行一次插入排序。  
需要注意的是，图中有两个相等数值的元素 5 和 5 。我们可以清楚的看到，在排序过程中，两个元素位置交换了。所以，希尔排序是不稳定的算法。

希尔排序：

public float[] shellSort(float[] array) {
            int arrLength = array.length;
            for (int step = arrLength >> 1; step > 0; step >>= 1) {
                for (int i = step; i < arrLength; i += step) {
       // 从这里开始跟插入排序比较
                    int j = i - step;
                    float temp = array[i];
                    while (j >= 0 && array[j] > temp) {
                        array[j + step] = array[j];
                        j -= step;
                    }
                    array[j + step] = temp;
                }
            }
            return array;
        }

## 三、冒泡排序 ##

冒泡排序算法的运作如下：  
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。  
2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素会是最大的数。  
3.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

可以结合下图理解（一轮排序）：  
![这里写图片描述][70 2]

冒泡排序：

public float[] bubbleSort(float[] array) {
            for (int i = 1; i < array.length; i++) {
                for (int j = 0; j < array.length - i; j++) {
                    if (array[j] > array[j + 1]) {
                        float temp = array[j];
                        array[j] = array[j + 1];
                        array[j + 1] = temp;
                    }
                }
            }
            return array;
        }

原数组本身就是有序的，仅需n-1次比较就可完成  
若是倒序，比较次数为 n-1+n-2+…+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度依然为ON\*2）

## 四、选择排序 ##

选择排序是简单直观的一种算法，基本思想为每一趟从待排序的数据元素中选择最小（或最大）的一个元素作为首元素，直到所有元素排完为止，择排序是不稳定的排序方法（比如序列\[5， 5， 3\]第一次就将第一个\[5\]与\[3\]交换，导致第一个5挪动到第二个5后面）。

选择排序算法的运作如下：  
(1)从**待排序序列**中，找到最小的元素；  
(2)如果最小元素不是**待排序序列**的第一个元素，将其和**待排序序列**的第一个元素互换；  
(3)从余下的 N - i 个元素中，找出关键字最小的元素，重复(1)、(2)步，直到排序结束。

选择排序：

public float[] selectSort(float[] array) {
            for (int i = 0; i < array.length - 1; i++) {
                int minIndex = i;
                for (int j = i + 1; j < array.length; j++) {
                    if (array[j] < array[minIndex]) {
                        minIndex = j;
                    }
                }
                float temp = array[minIndex];
                array[minIndex] = array[i];
                array[i] = temp;
            }
            return array;
        }

简单选择排序的比较次数与序列的初始排序无关。 假设待排序的序列有 N 个元素，则比较次数总是N (N - 1) / 2。  
而移动次数与序列的初始排序有关：  
当序列正序时，移动次数最少，为 0.  
当序列反序时，移动次数最多，为3N (N - 1) / 2。  
所以，综合以上，简单排序的时间复杂度为 O(N\*2)。

ref:  
1.[图解排序算法(一)之3种简单排序(选择，冒泡，直接插入)][3]  
2.[排序四 希尔排序][Link 1]  
2.[排序五 简单选择排序][Link 2]

[https_github.com_TimePickerWang_aimed-at-offer_blob_master_java_E6_BA_90_E7_A0_81_Sort.java]: https://github.com/TimePickerWang/aimed-at-offer/blob/master/java%E6%BA%90%E7%A0%81/Sort.java
[70]: /images/20220525/aea0313b4fa844ef9dfd6e6e9c19cc83.png
[70 1]: /images/20220525/feac20dd0e154abaa464430e2b0155ce.png
[70 2]: /images/20220525/99290280e107423ba22404173ba37b20.png
[3]: http://www.cnblogs.com/chengxiao/p/6103002.html
[Link 1]: http://www.cnblogs.com/jingmoxukong/p/4303279.html
[Link 2]: http://www.cnblogs.com/jingmoxukong/p/4303289.html