總目錄：地址如下看總綱
一替废、簡單插入排序
1、插入排序概要
插入式排序?qū)儆趦?nèi)部排序法倒得，是對于欲排序的元素以插入的方式找尋該元素的適當(dāng)位置立叛，以達(dá)到排序的目的。
2壤躲、基本思想
把n個待排序的元素看成為一個有序表和一個無序表城菊，開始時有序表中只包含一個元素，無序表中包含有n-1個元素碉克，排序過程中每次從無序表中取出第一個元素凌唬，把它的排序碼依次與有序表元素的排序碼進(jìn)行比較，將它插入到有序表中的適當(dāng)位置漏麦，使之成為新的有序表客税。
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));
// 創(chuàng)建要給80000個的隨機(jī)的數(shù)組
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++) {
// 定義待插入的數(shù)
insertVal = arr[i];
// 即arr[1]的前面這個數(shù)的下標(biāo)
insertIndex = i - 1;
// 給insertVal 尋找到插入的位置
// 說明
// 1. insertIndex >= 0 保證在給insertVal 找插入位置唁奢，不越界
// 2. insertVal < arr[insertIndex] 待插入的數(shù)霎挟，還沒有找到插入位置
// 3. 就需要將 arr[insertIndex] 后移
while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
arr[insertIndex + 1] = arr[insertIndex];
insertIndex--;
}
// 當(dāng)退出while循環(huán)時，說明插入的位置找到, insertIndex + 1
// 判斷是否需要賦值
if (insertIndex + 1 != i) {
arr[insertIndex + 1] = insertVal;
}
}
}
}
4麻掸、八萬數(shù)據(jù)測試
image.png
二酥夭、希爾排序（簡單插入的增強(qiáng)）
1、基本介紹
希爾排序是希爾（Donald Shell）于1959年提出的一種排序算法。希爾排序也是一種插入排序熬北，它是簡單插入排序經(jīng)過改進(jìn)之后的一個更高效的版本疙描，也稱為縮小增量排序。
2讶隐、思想
image.png
image.png
1起胰、希爾排序時， 對有序序列在插入時采用交換法
2巫延、希爾排序時效五， 對有序序列在插入時采用移動法(交換法的增強(qiáng))
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個數(shù)據(jù)分成了 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) {
// 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
if (arr[j] > arr[j + 5]) {
temp = arr[j];
arr[j] = arr[j + 5];
arr[j + 5] = temp;
}
}
}
// 希爾排序的第2輪排序
// 因為第2輪排序疼阔，是將10個數(shù)據(jù)分成了 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) {
// 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
if (arr[j] > arr[j + 2]) {
temp = arr[j];
arr[j] = arr[j + 2];
arr[j + 2] = temp;
}
}
}
// 希爾排序的第3輪排序
// 因為第3輪排序婆廊，是將10個數(shù)據(jù)分成了 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) {
// 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
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;
// 根據(jù)前面的逐步分析茵典，使用循環(huán)處理
// gap 控制組數(shù)
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) {
// 如果當(dāng)前元素大于加上步長后的那個元素列荔，說明交換
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個元素，逐個對其所在的組進(jìn)行直接插入排序
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]) {
// 找到了適當(dāng)位置贴浙，插入（移動）
arr[j] = arr[j - gap];
j -= gap;
}
// 當(dāng)退出while后砂吞，就給temp找到插入的位置
arr[j] = temp;
}
}
}
}
6、八萬數(shù)據(jù)效率
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));
// 創(chuàng)建80000個的隨機(jī)的數(shù)組
int[] arr = new int[80000];
for (int i = 0; i < 80000; i++) {
arr[i] = (int) (Math.random() * 8000000); // 生成一個[0, 8000000) 數(shù)
}
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個數(shù)據(jù)分成了 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) {
// 如果當(dāng)前元素大于加上步長后的那個元素袁串，說明交換
if (arr[j] > arr[j + 5]) {
temp = arr[j];
arr[j] = arr[j + 5];
arr[j + 5] = temp;
}
}
}
// 希爾排序的第2輪排序
// 因為第2輪排序概而，是將10個數(shù)據(jù)分成了 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) {
// 如果當(dāng)前元素大于加上步長后的那個元素囱修，說明交換
if (arr[j] > arr[j + 2]) {
temp = arr[j];
arr[j] = arr[j + 2];
arr[j + 2] = temp;
}
}
}
// 希爾排序的第3輪排序
// 因為第3輪排序赎瑰，是將10個數(shù)據(jù)分成了 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) {
// 如果當(dāng)前元素大于加上步長后的那個元素破镰，說明交換
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;// 輔助變量
// 根據(jù)前面的逐步分析餐曼，使用循環(huán)處理
// gap 控制組數(shù)
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) {
// 如果當(dāng)前元素大于加上步長后的那個元素，說明交換
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個元素源譬，逐個對其所在的組進(jìn)行直接插入排序
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]) {
// 找到了適當(dāng)位置集惋，插入（移動）
arr[j] = arr[j - gap];
j -= gap;
}
// 當(dāng)退出while后，就給temp找到插入的位置
arr[j] = temp;
}
}
}
}
}
