X5-1、java数据结构---插入排序算法【2020-12-8
2020-11-19 本文已影响0人
鄙人_阿K
总目录：地址如下看总纲
一、简单插入排序
1、插入排序概要
插入式排序属于内部排序法，是对于欲排序的元素以插入的方式找寻该元素的适当位置，以达到排序的目的。
2、基本思想
把n个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。
image.png
3、代码
/**
* title: 简单插入排序
* @author 阿K
* 2020年12月8日 下午10:38:05
*/
public class InsertSort {
public static void main(String[] args) {
// int[] arr = {101, 34, 119, 1, -1, 89};
// insertSort(arr);
// System.out.println(Arrays.toString(arr));
// 创建要给80000个的随机的数组
int[] arr = new int[80000];
for (int i = 0; i < arr.length; i++) {
arr[i] = (int) (Math.random() * 8000000);
}
new InsertSort(arr);
}
//
public InsertSort(int[] arr) {
long time = new Date().getTime();
insertSort(arr);
long time2 = new Date().getTime();
System.out.println("使用了：" + (time2 - time) + "毫秒");
}
// 直接插入排序 Api
public static void insertSort(int[] arr) {
int insertVal = 0;
int insertIndex = 0;
for (int i = 1; i < arr.length; i++) {
// 定义待插入的数
insertVal = arr[i];
// 即arr[1]的前面这个数的下标
insertIndex = i - 1;
// 给insertVal 寻找到插入的位置
// 说明
// 1. insertIndex >= 0 保证在给insertVal 找插入位置，不越界
// 2. insertVal < arr[insertIndex] 待插入的数，还没有找到插入位置
// 3. 就需要将 arr[insertIndex] 后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
// 当退出while循环时，说明插入的位置找到, insertIndex + 1
// 判断是否需要赋值
if (insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
}
}
}
4、八万数据测试
image.png
二、希尔排序（简单插入的增强）
1、基本介绍
希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。
2、思想
image.png
image.png
1、希尔排序时， 对有序序列在插入时采用交换法
2、希尔排序时， 对有序序列在插入时采用移动法(交换法的增强)
3、逐轮分析代码
/**
* title: 希尔排序
* @author 阿K
* 2020年12月10日 下午11:01:23
*/
public class ShellSort {
public static void main(String[] args) {
int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
// 希尔排序 api
public static void shellSort(int[] arr) {
int temp = 0;// 辅助变量
int count = 0;
// 希尔排序的第1轮排序
// 因为第1轮排序，是将10个数据分成了 5组
// [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
for (int i = 5; i < arr.length; i++) {
// 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
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;
}
}
}
// 希尔排序的第2轮排序
// 因为第2轮排序，是将10个数据分成了 2组
// [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
for (int i = 2; i < arr.length; i++) {
// 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
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;
}
}
}
// 希尔排序的第3轮排序
// 因为第3轮排序，是将10个数据分成了 2/2= 1 组
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for (int i = 1; i < arr.length; i++) {
// 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
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;
}
}
}
}
}
4、代码（交换法）
// 希尔排序 api
public static void shellSort2(int[] arr) {
int temp = 0;// 辅助变量
int count = 0;
// 根据前面的逐步分析，使用循环处理
// gap 控制组数
for(int gap = arr.length/2;gap>0;gap/=2) {
for(int i=gap;i<arr.length;i++) {
// 遍历各组中所有的元素(共gap组，每组有 (arr.length/gap) 个元素), 步长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;
}
}
}
}
}
5、代码（移位法）
// 希尔排序 api 移位法
public static void shellSort3(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]) {// 记住 gap是步长值
while (j - gap >= 0 && temp < arr[j - gap]) {
// 找到了适当位置，插入（移动）
arr[j] = arr[j - gap];
j -= gap;
}
// 当退出while后，就给temp找到插入的位置
arr[j] = temp;
}
}
}
}
6、八万数据效率
image.png
7、最终完整代码
package com.kk.datastructure.sort;
import java.util.Arrays;
import java.util.Date;
/**
* title: 希尔排序
* @author 阿K
* 2020年12月10日 下午11:25:31
*/
public class ShellSort {
public static void main(String[] args) {
// int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };
// shellSort3(arr);
// System.out.println(Arrays.toString(arr));
// 创建80000个的随机的数组
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一个[0, 8000000) 数
}
new ShellSort(arr, "2");
new ShellSort(arr, "3");
}
public ShellSort(int[] arr, String zhiling) {
long time = new Date().getTime();
if ("2".equals(zhiling)) {
shellSort2(arr);
long time2 = new Date().getTime();
System.out.println("希尔排序（交换法运行）：" + (time2 - time) + "毫秒");
} else {
shellSort3(arr);
long time2 = new Date().getTime();
System.out.println("希尔排序（移位法运行）：" + (time2 - time) + "毫秒");
}
}
// 希尔排序 api
public static void shellSort(int[] arr) {
int temp = 0;// 辅助变量
// 希尔排序的第1轮排序
// 因为第1轮排序，是将10个数据分成了 5组
// [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]
for (int i = 5; i < arr.length; i++) {
// 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
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;
}
}
}
// 希尔排序的第2轮排序
// 因为第2轮排序，是将10个数据分成了 2组
// [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]
for (int i = 2; i < arr.length; i++) {
// 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
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;
}
}
}
// 希尔排序的第3轮排序
// 因为第3轮排序，是将10个数据分成了 2/2= 1 组
// [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
for (int i = 1; i < arr.length; i++) {
// 遍历各组中所有的元素(共5组，每组有2个元素), 步长5
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;
}
}
}
}
// 希尔排序 api 交换法
public static void shellSort2(int[] arr) {
int temp = 0;// 辅助变量
// 根据前面的逐步分析，使用循环处理
// gap 控制组数
for (int gap = arr.length / 2; gap > 0; gap /= 2) {
for (int i = gap; i < arr.length; i++) {
// 遍历各组中所有的元素(共gap组，每组有 (arr.length/gap) 个元素), 步长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;
}
}
}
}
}
// 希尔排序 api 移位法
public static void shellSort3(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]) {// 记住 gap是步长值
while (j - gap >= 0 && temp < arr[j - gap]) {
// 找到了适当位置，插入（移动）
arr[j] = arr[j - gap];
j -= gap;
}
// 当退出while后，就给temp找到插入的位置
arr[j] = temp;
}
}
}
}
}
