1. 首页
  2. 文章中心
  3. 数据结构

数据结构笔记_16 插入排序（直接插入排序、希尔排序）一、直接插入排序二、希尔排序（交换法）三、希尔排序（移位法）

74 阅读 0 评论
我是靠谱客的博主 复杂水池，最近开发中收集的这篇文章主要介绍数据结构笔记_16 插入排序（直接插入排序、希尔排序）一、直接插入排序二、希尔排序（交换法）三、希尔排序（移位法），觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

一、直接插入排序

1、介绍

插入式排序属于内部排序法，是对于待排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。

可以比方成打牌，将抓到的牌按一定的顺序，插入到合适的位置。

2、思想

插入排序（Insertion Sorting）的基本思想是：把n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

为了方便理解，以一个例子的拆分步骤，分析程序执行原理。

3、代码

1）逐步推导

例：将101,34,119,1按从小到大的顺序排列。

package com.huey.sort;

import java.util.Arrays;

/**
 * @author Huey
 *
 *         2021年2月15日 下午8:30:21
 */

public class InsertSort {

	public static void main(String[] args) {
		// 逐步推导的方法来写，便于理解
		// 第1轮{101,34,119,1} => {34,101,119,1}
		int[] arr = { 101, 34, 119, 1 };
		insertSort(arr);
	}

	// 插入排序
	public static void insertSort(int[] arr) {

		// 第一轮

		// 定义待插入的数
		int insertVal = arr[1];// 先保存一下，不然后面后移 arr[insertIndex] 会丢失。
		int insertIndex = 1 - 1;// 即arr[1]的前面这个数的下标

		// 给insertVal 找到插入的位置
		// 说明：
		// 1.insertIndex >= 0 保证在给insertVal 找插入位置时，不越界
		// 2.insertVal < arr[insertIndex] 表示待插入的数，还没有找到插入位置
		// 3.就需要将 arr[insertIndex] 后移

		while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
			arr[insertIndex + 1] = arr[insertIndex];// {101,34,119,1} => {101,101,119,1}
			insertIndex--;// 让34和前面这个元素进行比较
		}
		// 当退出while 循环时，插入的位置已找到，insertIndex + 1
		// 两种情况：1、一开始就不满足循环条件，直接退出。2、进入循环最后一次判断 insertIndex为-1，退出循环时+1，表示第一个位置。
		arr[insertIndex + 1] = insertVal;

		System.out.println("第一轮插入后~");
		System.out.println(Arrays.toString(arr));

		// 第二轮
		insertVal = arr[2];
		insertIndex = 2 - 1;

		while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
			arr[insertIndex + 1] = arr[insertIndex];
			insertIndex--;
		}

		arr[insertIndex + 1] = insertVal;
		System.out.println("第二轮~");
		System.out.println(Arrays.toString(arr));

		// 第三轮
		insertVal = arr[3];
		insertIndex = 3 - 1;

		while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
			arr[insertIndex + 1] = arr[insertIndex];
			insertIndex--;
		}

		arr[insertIndex + 1] = insertVal;
		System.out.println("第三轮~");
		System.out.println(Arrays.toString(arr));

	}
}

输出结果：
在这里插入图片描述

2）使用循环进行简化~

package com.huey.sort;

import java.util.Arrays;

public class InsertSort {

	public static void main(String[] args) {
		int[] arr = { 101, 34, 119, 1 };
		insertSort(arr);
	}

	// 插入排序
	public static void insertSort(int[] arr) {

		for (int i = 0; i < arr.length - 1; i++) {

			int insertIndex = i;
			int insertVal = arr[i + 1];

			while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
				arr[insertIndex + 1] = arr[insertIndex];
				insertIndex--;
			}
			arr[insertIndex + 1] = insertVal;
			System.out.printf("第" + (i + 1) + "轮排序后~n");
			System.out.println(Arrays.toString(arr));
		}
	}

}

输出结果：

在这里插入图片描述

3）速度测试

老规矩，测试一下速度，跟前面一样随机生成80000个数：

在这里插入图片描述

经过多次测试，基本上都在1s.

二、希尔排序（交换法）

1、介绍

希尔排序(Shell’s Sort)是希尔( Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序（Diminishing Increment Sort）。

2、思想

希尔排序是把记录按下标的一定増量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

原理图如下：
在这里插入图片描述

3、代码

1）逐步推导

package com.huey.sort;

import java.util.Arrays;

/**
 * @author Huey
 *
 * 2021年2月17日 下午4:31:18
 */
public class ShellSort {

	public static void main(String[] args) {
		int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
		shellSort(arr);
	}

	// 使用逐步推导的方式(交换法)
	public static void shellSort(int[] arr) {

		// 第1轮排序，将10个数据分成了10/2 = 5组
		int temp = 0;
		for (int i = 5; i < arr.length; i++) {
			// 遍历各组中所有的元素（共有5组，每组2个元素）
			for (int j = i - 5; j >= 0; j -= 5) {
				// 如果当前元素大于加上步长后的那个元素，说明交换
				if (arr[j] > arr[j + 5]) {
					temp = arr[j];
					arr[j] = arr[j + 5];
					arr[j + 5] = temp;
				}
			}
		}
		System.out.println("希尔排序第1轮后:" + Arrays.toString(arr));

		// 第2轮排序，将10个数据分成了5/2 = 2组
		for (int i = 2; i < arr.length; i++) {
			// 遍历各组中所有的元素（共有2组，每组5个元素），步长2
			for (int j = i - 2; j >= 0; j -= 2) {
				// 如果当前元素大于加上步长后的那个元素，说明交换
				if (arr[j] > arr[j + 2]) {
					temp = arr[j];
					arr[j] = arr[j + 2];
					arr[j + 2] = temp;
				}
			}
		}
		System.out.println("希尔排序第2轮后:" + Arrays.toString(arr));

		// 第3轮排序，将10个数据分成了2/2 = 1组
		for (int i = 1; i < arr.length; i++) {
			// 遍历各组中所有的元素（共有1组，每组10个元素），步长1
			for (int j = i - 1; j >= 0; j -= 1) {
				// 如果当前元素大于加上步长后的那个元素，说明交换
				if (arr[j] > arr[j + 1]) {
					temp = arr[j];
					arr[j] = arr[j + 1];
					arr[j + 1] = temp;
				}
			}
		}
		System.out.println("希尔排序第3轮后:" + Arrays.toString(arr));
	}

}

输出结果：
在这里插入图片描述
基本步骤、原理明白了之后。下面使用for 循环处理:

2）使用循环处理

package com.huey.sort;

import java.util.Arrays;

/**
 * @author Huey
 *
 *         2021年2月17日 下午4:31:18
 */
public class ShellSort {

	public static void main(String[] args) {
		int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
		shellSort(arr);
	}

	// 使用逐步推导的方式
	// 交换法
	// 思路（算法） => 代码
	public static void shellSort(int[] arr) {
		int temp = 0;
		int count = 0;
		// 根据逐步分析，使用循环处理
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
		// 控制进行几次分组
			for (int i = gap; i < arr.length; i++) {
				// 遍历各组中所有的元素（共有gap组）
				for (int j = i - gap; j >= 0; j -= gap) {
					// 如果当前元素大于加上步长后的那个元素，说明交换
					if (arr[j] > arr[j + gap]) {
						temp = arr[j];
						arr[j] = arr[j + gap];
						arr[j + gap] = temp;
					}
				}
			}
			System.out.println("希尔排序第" + (++count) + "轮：" + Arrays.toString(arr));
		}

	}

}

输出结果：
在这里插入图片描述

3）速度测试

package com.huey.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class ShellSortSolo {

	public static void main(String[] args) {
		// 测试一下希尔排序的速度O(nlogn)
		// 创建要给80000个的随机的数组
		int[] arr = new int[80000];
		for (int i = 0; i < 80000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
		}

		// 格式化时间
		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的时间是:" + date1Str);
		System.out.println("正在排序中，请稍后~");

		// 测试冒泡排序
		shellSort(arr);

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序后的时间是:" + date2Str);
	}

	public static void shellSort(int[] arr) {
		int temp = 0;
		int count = 0;
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
			for (int i = gap; i < arr.length; i++) {
				for (int j = i - gap; j >= 0; j -= gap) {
					if (arr[j] > arr[j + gap]) {
						temp = arr[j];
						arr[j] = arr[j + gap];
						arr[j + gap] = temp;
					}
				}
			}
		}

	}

}

输出结果：
在这里插入图片描述
基本上在4~5s.

三、希尔排序（移位法）

交换法，只要发现一个大的就交换一次，在疯狂交换，效率不高。
移位法，先找到位置再进行交换，效率很高。

例子：按从小到大排序2，3，1

交换法：

	public static void shellSort(int[] arr) {
		int temp = 0;
		int count = 0;
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
			for (int i = gap; i < arr.length; i++) {
				for (int j = i - gap; j >= 0; j -= gap) {
					if (arr[j] > arr[j + gap]) {
						temp = arr[j];
						arr[j] = arr[j + gap];
						arr[j + gap] = temp;
					}
				}
			}
		}
	}

gap = 1
i = 1，j = i - gap = 0，arr[j] < arr[j + 1]不进入if. = = > 2，3，1
i = 2，j = i - gap = 1，arr[j] > arr[j + 1]进入if 将这两个数字进行交换。 = = > 2，1，3
i = 2，j = j - gap = 0，arr[j] > arr[j + 1]进入if 将这两个数字进行交换。 = = > 1，2，3

gap = 0，退出

移位法：

	public static void shellSortMoving(int[] arr) {

		// 增量gap,并逐步的缩小增量
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
			// 从第gap个元素开始，逐个对其所在的组进行直接插入排序
			for (int i = gap; i < arr.length; i++) {
				int j = i;
				int temp = arr[j];
				if (arr[j] < arr[j - gap]) {
					while (j - gap >= 0 && temp < arr[j - gap]) {
						// 开始移动，而不是之前的交换
						arr[j] = arr[j - gap];
						j -= gap;
					}
					// 当退出循环后，就给temp找到了插入的位置
					arr[j] = temp;
				}
			}
		}
	}

gap = 1
i = 1，j = gap = 1，j = i = 1，temp = 3，arr[j] > arr[j - gap]不进入if. = => 2，3，1
i = 2，j = gap = 1，j = i = 2，temp = 1，arr[j] < arr[j - gap]进入if. 满足条件进入while（进行两次移位：2，3，3 和 2，2，3 = => 1，2，3

gap = 0，退出

前一种交换法可以理解为借希尔排序进行分组+冒泡排序，而移位法可以理解为借希尔排序进行分组+插入排序。

package com.huey.sort;

import java.text.SimpleDateFormat;
import java.util.Date;

public class ShellSortMoving {

	public static void main(String[] args) {
		// 测试希尔排序（移位）的速度
		// 创建要给80000个的随机的数组
		int[] arr = new int[80000];
		for (int i = 0; i < 80000; i++) {
			arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
		}

		// 格式化时间
		Date data1 = new Date();
		SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
		String date1Str = simpleDateFormat.format(data1);
		System.out.println("排序前的时间是:" + date1Str);
		System.out.println("正在排序中，请稍后~");

		// 测试希尔排序
		shellSortMoving(arr);

		Date data2 = new Date();
		String date2Str = simpleDateFormat.format(data2);
		System.out.println("排序后的时间是:" + date2Str);
	}

	// 对希尔排序进行优化 -> 移位法
	public static void shellSortMoving(int[] arr) {

		// 增量gap,并逐步的缩小增量
		for (int gap = arr.length / 2; gap > 0; gap /= 2) {
			// 从第gap个元素开始，逐个对其所在的组进行直接插入排序
			for (int i = gap; i < arr.length; i++) {
				int j = i;
				int temp = arr[j];
				if (arr[j] < arr[j - gap]) {
					while (j - gap >= 0 && temp < arr[j - gap]) {
						// 开始移动，而不是之前的交换
						arr[j] = arr[j - gap];
						j -= gap;
					}
					// 当退出循环后，就给temp找到了插入的位置
					arr[j] = temp;
				}
			}
		}
	}

}

在这里插入图片描述
在这里插入图片描述

基本都在0~1s.

极限测试一把八千万个数字：
在这里插入图片描述
厉害：
在这里插入图片描述

最后

以上就是复杂水池为你收集整理的数据结构笔记_16 插入排序（直接插入排序、希尔排序）一、直接插入排序二、希尔排序（交换法）三、希尔排序（移位法）的全部内容，希望文章能够帮你解决数据结构笔记_16 插入排序（直接插入排序、希尔排序）一、直接插入排序二、希尔排序（交换法）三、希尔排序（移位法）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。

本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
点赞(49)

相关文章

【冒泡排序-三个任意不同数字输出最大值】
【冒泡排序-三个任意不同数字输出最大值】
冒泡法排序
冒泡法排序
冒泡排序（任意三个数从大到小排序）
冒泡排序（任意三个数从大到小排序）
汇编学习笔记->数组的冒泡排序使用冒泡排序算法对数组进行升序排序一些指令的说明
汇编学习笔记->数组的冒泡排序使用冒泡排序算法对数组进行升序排序一些指令的说明
数据结构笔记_16 插入排序（直接插入排序、希尔排序）一、直接插入排序二、希尔排序（交换法）三、希尔排序（移位法）
数据结构笔记_16 插入排序（直接插入排序、希尔排序）一、直接插入排序二、希尔排序（交换法）三、希尔排序（移位法）
用起泡法对10个数排序（由小到大和由大到小）
用起泡法对10个数排序（由小到大和由大到小）
C语言三个数字比较大小
C语言三个数字比较大小
matlab快速排序
matlab快速排序

评论列表共有 0 条评论

立即
投稿
返回
顶部