插入排序和希尔排序
插入排序
插入排序是一种简单直观的排序算法，它的工作原理类似于我们整理手上的扑克牌。每次从牌堆中抽出一张牌（即列表中的一个元素），然后将其插入到已排序的牌列（列表）中的正确位置，直到所有牌都被整理好。下面是对您提供的插入排序介绍的总结和补充：
一、概念及其介绍
定义：插入排序是一种简单且直观的排序算法，适用于小规模数据的排序。
基本思想：通过构建有序序列，对于未排序的数据，在已排序序列中从后向前扫描，找到相应位置并插入。
实现特点：使用双层循环，外层循环遍历每个元素，内层循环负责将当前元素插入到正确的位置。
二、适用说明
时间复杂度：平均时间复杂度为 O(n^2)，最坏情况下（完全逆序）也是 O(n^2)，最好情况下（已排序）为 O(n)。
空间复杂度：O(1)，因为它是原地排序，不需要额外的空间。
稳定性：插入排序是一种稳定的排序算法，因为它不会改变相同元素之间的相对顺序。
三、过程
虽然这里没有具体的图示，但可以通过文字描述来理解插入排序的过程。比如，给定一个未排序的数组 [7, 6, 9, 3, 1]，插入排序的过程可以分为以下几个步骤：
1. 第一轮，将 6 插入到 7 前面，数组变为 [6, 7, 9, 3, 1]。
2. 第二轮，9 保持不变，数组仍为 [6, 7, 9, 3, 1]。
3. 第三轮，将 3 插入到适当位置，数组变为 [3, 6, 7, 9, 1]。
4. 第四轮，将 1 插入到最前面，最终数组变为 [1, 3, 6, 7, 9]。
四、Java 实例代码
package runoob;
/**
* 插入排序
*/
public class InsertionSort {
//核心代码---开始
public static void sort(Comparable[] arr){
int n = arr.length;
for (int i = 0; i < n; i++) {
// 寻找元素 arr[i] 合适的插入位置
for( int j = i ; j > 0 ; j -- )
if( arr[j].compareTo( arr[j-1] ) < 0 )
swap( arr, j , j-1 );
else
break;
}
}
//核心代码---结束
private static void swap(Object[] arr, int i, int j) {
Object t = arr[i];
arr[i] = arr[j];
arr[j] = t;
}
public static void main(String[] args) {
int N = 20000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 100000);
InsertionSort.sort(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(' ');
}
}
}下面是代码的简要解释：
sort 方法是排序的核心，它接受一个 Comparable 类型的数组作为参数，使用双重循环来实现插入排序。
内部循环负责将当前元素与已排序的部分进行比较，并在必要时交换它们的位置，以确保当前元素被放置在正确的位置。
swap 方法用于交换数组中两个指定位置的元素。
main 方法用于测试排序功能，它首先生成一个随机数组，然后调用 sort 方法对其进行排序，最后打印排序后的数组。
希尔排序
希尔排序（Shell Sort）是插入排序的一种更高效的改进版本，它通过减少元素之间的比较次数来提高效率。希尔排序通过先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列“基本有序”时，再对全体记录进行一次直接插入排序。
一、概念及其介绍
定义：希尔排序是一种基于插入排序的排序算法，但它通过将原始列表分割成多个子列表来改进性能，每个子列表使用插入排序进行排序。
基本思想：通过比较相距一定间隔的元素来进行排序，逐步减少间隔，直到间隔为1，此时整个列表基本有序，最后进行一次插入排序。
特点：希尔排序能够显著减少插入排序中的比较次数，尤其是在处理大量数据时。
二、适用说明
时间复杂度：希尔排序的时间复杂度取决于所选的增量序列，通常情况下介于 O(n^(1.3-2)) 之间，优于普通插入排序的 O(n^2)。
空间复杂度：O(1)，希尔排序是原地排序算法，不需要额外的存储空间。
稳定性：希尔排序不是稳定的排序算法，因为相等的元素可能会因为插入操作而改变它们的相对顺序。
三、过程
希尔排序的过程可以通过以下步骤来理解：
1. 选择增量：首先确定一个增量序列，常见的增量序列是 gap = length / 2，然后逐步缩小增量，直到 gap = 1。
2. 分组排序：根据当前的增量 gap，将数组分成若干子序列，每个子序列包含相隔 gap 的元素。对每个子序列进行插入排序。
3. 减少增量：将增量 gap 减半，重复上述分组排序的过程，直到 gap 变为 1。
4. 最终排序：当 gap 为 1 时，整个数组已经基本有序，进行最后一次插入排序，确保数组完全有序。
四、Java 实例代码
public class ShellSort {
//核心代码---开始
public static void sort(Comparable[] arr) {
int j;
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
Comparable tmp = arr[i];
for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = tmp;
}
}
}
//核心代码---结束
public static void main(String[] args) {
int N = 2000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10);
ShellSort.sort(arr);
for( int i = 0 ; i < arr.length ; i ++ ){
System.out.print(arr[i]);
System.out.print(' ');
}
}
}下面是代码的详细解释：
public class ShellSort {
// 核心代码 --- 开始
public static void sort(Comparable[] arr) {
// 从较大的增量开始，逐渐减小增量
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
// 对每个子序列进行插入排序
for (int i = gap; i < arr.length; i++) {
Comparable tmp = arr[i];
int j;
// 在子序列中找到合适的位置插入
for (j = i; j >= gap && tmp.compareTo(arr[j - gap]) < 0; j -= gap) {
arr[j] = arr[j - gap];
}
arr[j] = tmp;
}
}
}
// 核心代码 --- 结束
public static void main(String[] args) {
int N = 2000;
Integer[] arr = SortTestHelper.generateRandomArray(N, 0, 10);
ShellSort.sort(arr);
for (int i = 0; i < arr.length; i++) {
System.out.print(arr[i]);
System.out.print(' ');
}
}
}代码解释
sort 方法：
外层循环控制增量 gap，从 arr.length / 2 开始，每次减半，直到 gap 为 1。
中间循环遍历每个子序列的起始位置 i，从 gap 到 arr.length - 1。
内层循环使用插入排序的思想，将当前元素 tmp 插入到正确的子序列位置。
main 方法：
生成一个随机数组 arr，长度为 2000，元素范围在 0 到 10 之间。
调用 sort 方法对数组进行排序。
打印排序后的数组。
原文地址：https://blog.csdn.net/b123321888/article/details/143491758
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！