前言
本文简单介绍了希尔排序和归并排序的java代码实现，要看原理建议看书或者网上寻找视频资源。本文不对原理有过多阐述。
目录
一、希尔排序
1.1、希尔排序的定义：
2.2、案例解析：
二、归并排序
一、希尔排序
1.1、希尔排序的定义：
希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。
2.2、案例解析：
希尔排序是插入排序的一种，又称“缩小增量排序”，是插入排序算法的一种更高效的改进版本。
2.2、案例解析：
对数组进行排序：{3, 6, 9, 2, 8, 4, 5, 7, 1, 0}
获取数组的增量，应该为5
用增量h为5数组分为5组数据，3,4;6,5;9,7;2,1;8,0;
进入循环对该5组数据进行排序之后，在增量为2进行排序，直到增量为1，结束循环，也就得到了希尔排序的最终结果。
代码演示
package com.Sorting.ShellSort;
import java.util.ArrayList;
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
Integer[] arr = {3, 6, 9, 2, 8, 4, 5, 7, 1, 0};
ShellSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(Comparable[] arr) {
int n = arr.length;
int h = 1;
//确定增长量h的最大值
while (h < n / 2) {
h = h * 2 + 1;
}
while (h >= 1) {
//待排序元素i
for (int i = h; i < n; i++) {
for (int j = i; j >= h; j -= h) {
//同一组元素j-h即是需要比较的元素，例如，h=5,5-5=0，那么索引0处的值就应该和索引5处的值进行比较
//比较完成之后，就进入下一组，继续进行比较，当一轮比较完毕之后，减少增长量，继续进行比较，直到增长量为1
if (greater(arr[j - h], arr[j])) {
exchangeElement(arr, j, j - h);
} else {
break;
}
}
}
//增长量减小，增长量依次除以二
h /= 2;
}
}
public static boolean greater(Comparable a, Comparable b) {
return a.compareTo(b) > 0;
}
public static void exchangeElement(Comparable[] a, int i, int j) {
Comparable temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
二、归并排序
归并排序
定义：
归并排序是建立在归并操作上的一种有效的排序算法，该算法是采用分治法的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序 表，称为二路归并。
依旧是上面的案例
解题步骤：
1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是1为止。 2.将相邻的两个子组进行合并成一个有序的大组； 3.不断的重复步骤 2 ，直到最终只有一个组为止。归并的时候需要使用三个指针和一个辅助数组，一个指针指向辅助数组的插入元素的起始索引，一个指向第一组数组的第一个元素，最后一个指针指向第二组数据的第一个元素。 代码实现
package com.Sorting.mergeSort;
import java.util.Arrays;
public class MergeSort {
public static void main(String[] args) {
Integer[] arr = {3, 6, 9, 2, 8, 4, 5, 7, 1, 0};
MergeSort.sort(arr);
System.out.println(Arrays.toString(arr));
}
private static Comparable[] auxiliary;
public static void sort(Comparable[] array) {
auxiliary = new Comparable[array.length];
int low = 0;
int high = array.length - 1;
sort(array, low, high);
}
public static void sort(Comparable[] array, int low, int high) {
if (high <= low) {
//如果后面的值比前面的值小，就不用进行排序
return;
}
//取中间值操作
int mid = low + (high - low) / 2;
//从low到mid之间的元素进行排序
sort(array, low, mid);
//从mid之后一位即第二组元素第一位开始，到high之间的元素的排序
sort(array, mid + 1, high);
//合并操作
merge(array, low, mid, high);
}
public static void merge(Comparable[] array, int low, int mid, int high) {
//定义一个指针，指向辅助数组Auxiliary的开始填充数据的索引
int i = low;
//定义一个指针，指向第一组数据的第一个元素
int e1 = low;
//定义一个指针，指向第二组数据的第一个元素
int e2 = mid + 1;
//比较两个小组的各个元素，哪个元素小，就将元素插入到辅助数组中
//当第一个指针，指到第一组最后一个元素，和第二个指针指到第二组数据最后一个元素的时候，
while (e1 <= mid && e2 <= high) {
//比较数组中的元素
if (lessThan(array[e1], array[e2])) {
//如果第一个元素小，就将第一个元素放入辅助数组中
//并且i指针后移，e1也需要后移
auxiliary[i++] = array[e1++];
} else {
//反之就是将e2元素放入辅助数组之中
auxiliary[i++] = array[e2++];
}
}
//下面两个循环是上面循环结束时可能只有一个指针结束，那么就要继续执行下面的
//两个循环当中的其中一个，
while (e1 <= mid) {
auxiliary[i++] = array[e1++];
}
while (e2 <= high) {
auxiliary[i++] = array[e2++];
}
//将相应的元素填充到原数组当中
for (int index = low; index <= high; index++) {
array[index] = auxiliary[index];
}
}
public static boolean lessThan(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
}
