排序算法系列一：选择排序、插入排序与希尔排序

零、说在前面

本文是一个系列，入口请移步这里

一、理论部分

1.1：选择排序

1.1.1：算法解读：

使用二分法和插入排序两种算法的思想来实现。流程分为“拆分”、“合并”两大部分，前者就是普通的二分思想，将一个数组拆成n个子组；后者是在每个子组内部用插入法排序，在子组间定义一个辅助数组和三个指针，用辅助数组搭配指针选数进行排序，再将两个子组合并；最终将所有子组合并成一个有序的数组。

1.1.2：时间复杂度

由于该算法使用了双层for循环，分别涉及到 (N-1)*N/2 次的比较和 (N-1)*N/2 次的交换

因此时间复杂度是 (N-1)*N，即 $N^{2}$ -N，故而时间复杂度为 O( $N^{2}$ )

在最优与最坏情况，二分操作耗时不会节约、归并比较阶段操作耗时不会节约，因此遍历的数据量不变，，因此固定为O( $N^{2}$ )

1.1.3：优缺点：

受该算法的时间复杂度所限，在小数据量时有不错的效率，不适用于大量数据排序。

1.1.4：代码：

/**
 * date:    2024-06-23
 * author:  dark
 * description: 选择排序算法（由小到大）
 */
public class Selection {

    /**
     * 逻辑步骤：1：接受一个数组，从左向右循环遍历数组中每个元素，并将每轮循环得到的最小元素置于本轮循环的起始位置
     * @param arrays
     */
    public void selectSort(Integer[] arrays){
        /**
         * 定义临时变量 和 数组长度
         */
        Integer temp = 0 , arrayLength = arrays.length ;
        /**
         * 从左向右遍历数组元素，获取并将每轮遍历的最小元素置于本轮循环的起始位置。
         */
        for (int i = 0; i < arrayLength; i++) {
            for (int j = i+1; j < arrayLength; j++) {
                if(arrays[i] > arrays[j]){
                    temp = arrays[i];
                    arrays[i] = arrays[j];
                    arrays[j] = temp;
                }
            }
        }
    }
}

1.2：插入排序

1.2.1：算法解读：

将数组看做左侧有序右侧无序的两部分。初始状态以数组最左侧的一个数据作为已排序组。逐个使用未排序组元素，从右向左地与已排序组元素逐个对比，若未排序的数据小于已排序数据则交换，否则使用未排序组的下一个元素重复上面的操作，直至整个数组有序。

1.2.2：时间复杂度

由于该算法使用了双层for循环，分别涉及到 (N-1)*N/2 次的比较和 (N-1)*N/2 次的交换

因此时间复杂度是 (N-1)*N，即 $N^{2}$ -N，故而时间复杂度为 O( $N^{2}$ )

最优情况下数组有序，时间复杂度为 O(N)，最坏情况下数据倒序，，时间复杂度为O( $N^{2}$ )，平均时间复杂度为 O( $N^{2}$ ) (推导过程复杂，需要考虑各种情况的加权平均，因此略过)

1.2.3：优缺点：

同选择排序。

1.2.4：代码：

/**
 * date:    2024-06-22
 * author:  dark
 * description: 插入排序算法（由小到大）
 */
public class Insertion {

    /**
     * 逻辑步骤：1：接受一个数组，初始状态以其首元素作为“有序组”，其余元素作为“无序组”，并记录有序组和无序组首元素的坐标
     *         2：遍历无序组，每轮遍历只取无序组左侧首元素，以从右向左的顺序与有序组中的各个元素进行比对
     *            当无需组首元素小于有序组元素，交换二者位置，直至有序组达到首元素或有序组再无元素大于无序组首元素，退出遍历
     *         3：将无序组首元素坐标右移，重复步骤2的操作，直至无序组中没有元素。
     * @param arrays
     */
    public void insertionSort(Integer[] arrays){
        /**
         * 定义临时交换变量
         */
        Integer temp;
        /**
         * 遍历无序组
         */
        for(int i= 1; i < arrays.length; i++){
            /**
             * 将无序组的首元素从右向左逐个与有序组比对，若首元素更小则交换，直至首元素大于有序组某元素或到达有序组首位
             * i 代表无序组的首元素，j 代表有序组的末元素
             */
            for (int j = i-1; j >= 0; j--) {
                if(arrays[j+1] < arrays[j]){
                    temp = arrays[j+1];
                    arrays[j+1] = arrays[j];
                    arrays[j] = temp;
                }
                else{
                    break;
                }
            }
        }
    }
}

1.3：希尔排序

1.3.1：算法解读：

借鉴了分治法的思想，在插入的基础上做了优化。对原数组进行多轮分组，组数据量随着轮次的递增而倍增。同时在每轮都对组内数据进行插入排序，使组数据趋势有序，这为最终一次使用插入排序减少了数据交换的次数。

1.3.2：时间复杂度

因为用到了分治思想，因此时间复杂度除了与数据量有关，还与遍历次数（即对数据量二分次数 logN ）有关，因此时间复杂度为 O(N logN)

1.3.3：优缺点：

因为用到分治思想，故在大数据量情况下排序表现较好。

1.3.4：代码：

/**
 * date:    2024-06-22
 * author:  dark
 * description: 希尔排序算法（由小到大）
 */
public class Shell {

    /**
     * 逻辑步骤：1：接受一个数组，定义分组步长，设初始值为1，并不断用 步长*2+1 的结果与数组长度比对，直至大于后者作为步长的实际值
     *         2：从数组首元素开始，将与之距离为步长倍数的所有元素视为一组，对这组元素按照插入排序法排序。
     *         3：按上述方法逐个处理整个数组的所有元素
     *         4：将步长减半，重复第2、3步，直至步长减为1。
     * @param arrays
     */
    public void shellSort(Integer[] arrays){
        /**
         * 定义步长、数组长度、临时变量
         */
        int stepLength = 1;
        int arrLength = arrays.length;
        int temp = 0;

        /**
         * 确定stepLength 的初始值
         */
        while (stepLength <= arrLength / 2){
            stepLength = stepLength * 2 + 1;
        }

        /**
         * 逐渐缩小步长，重复执行小组插入排序逻辑
         */
        while(stepLength >= 1){
            /**
             * 用以 stepLength 为首元素的子组作为无序组，以 j-stepLength 为首元素的子组作为有序组。执行插入排序
             */
            for (int j = stepLength; j < arrLength; j+=stepLength) {
                for (int k = j-stepLength; k >=0; k-=stepLength) {
                    if(arrays[k+stepLength] < arrays[k]){
                        temp = arrays[k];
                        arrays[k] = arrays[k+stepLength];
                        arrays[k+stepLength] = temp;
                    }
                    else{
                        break;
                    }
                }
            }
            stepLength /= 2;
        }
    }
}