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

目录

零、说在前面

一、理论部分

1.1：选择排序

1.1.1：算法解读：

1.1.2：时间复杂度

1.1.3：优缺点：

1.1.4：代码：

1.2：插入排序

1.2.1：算法解读：

1.2.2：时间复杂度

1.2.3：优缺点：

1.2.4：代码：

1.3：希尔排序

1.3.1：算法解读：

1.3.2：时间复杂度

1.3.3：优缺点：

1.3.4：代码：

二、对比

2.1：选择与冒泡

2.2：插入与选择

2.3：插入与希尔

---

零、说在前面

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

一、理论部分

1.1：选择排序

1.1.1：算法解读：

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

1.1.2：时间复杂度

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

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

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

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，故而时间复杂度为 O()

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

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)

        无论最优还是最差情况，遍历的数据量及遍历轮次不变，因此时间复杂度恒定 O(N logN)。而且不会因数据完全有序而减少过多的遍历过程。可以用1~8和8~1 验算一次，执行次数基本无差

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;}}
}

二、对比

2.1：选择与冒泡

        二者核心算法接近，区别在于后者将每轮循环中得到的最小值规整到了固定位置，有整理收纳的思想在里面。

2.2：插入与选择

        选择排序受其逻辑制约，无论如何都要把本轮剩余的元素都遍历一次，因此其时间复杂度是固定的 O(N平方)，但插入排序由于有序组数据的规律性，因此其时间复杂度在最优情况下可以达到O(N)（即初始有序），最坏情况下是O(N平方)（即逆序）

2.3：插入与希尔

        后者通过多次小范围插排，将数据尽可能的规整。我测试生成9万、20万和40万条随机数，然后分别使用希尔和插入排序分别对这些数据的副本进行排序。对比结果前两次希尔稍快（60%和80%左右），第三次希尔略慢（103%左右）。可见，随着数据量的增大，多次插排的时间代价带来的时间损耗就比较明显了。