前言
本文简单介绍了希尔排序和归并排序的java代码实现,要看原理建议看书或者网上寻找视频资源。本文不对原理有过多阐述。
目录
一、希尔排序
1.1、希尔排序的定义:
希尔排序是插入排序的一种,又称“缩小增量排序”,是插入排序算法的一种更高效的改进版本。
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;
/**
* @author wang
* @version 1.0
* @packageName com.Sorting.ShellSort
* @className ShellSort
* @date 2022/1/21 11:40
* @Description 希尔排序代码实现
*/
public class ShellSort {
/**
* @Date 2022/1/21 12:04
* @Param
* @param args
* @Return void
* @MetodName main
* @Author wang
* @Description 测试代码,测试结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
*/
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));
}
/**
* @Date 2022/1/21 12:04
* @Param
* @param arr
* @Return void
* @MetodName sort
* @Author wang
* @Description 排序方法,
*/
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;
}
}
/**
* @Date 2022/1/21 12:04
* @Param
* @param a
* @param b
* @Return boolean
* @MetodName greater
* @Author wang
* @Description 比较方法,比较a元素是否大于b元素
*/
public static boolean greater(Comparable a, Comparable b) {
return a.compareTo(b) > 0;
}
/**
* @Date 2022/1/21 12:05
* @Param
* @param a
* @param i
* @param j
* @Return void
* @MetodName exchangeElement
* @Author wang
* @Description 交换数组元素位置
*/
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;
/**
* @author wang
* @version 1.0
* @packageName com.Sorting.mergeSort
* @className MergeSort
* @date 2022/1/21 19:13
* @Description 归并排序代码实现
*/
public class MergeSort {
/**
* @Date 2022/1/21 19:57
* @Param
* @param args
* @Return void
* @MetodName main
* @Author wang
* @Description 测试方法,测试结果:[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
*/
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;
/**
* @param array
* @Date 2022/1/21 19:54
* @Param
* @Return void
* @MetodName sort
* @Author wang
* @Description 对数组进行归并排序
*/
public static void sort(Comparable[] array) {
auxiliary = new Comparable[array.length];
int low = 0;
int high = array.length - 1;
sort(array, low, high);
}
/**
* @param array
* @param low
* @param high
* @Date 2022/1/21 19:55
* @Param
* @Return void
* @MetodName sort
* @Author wang
* @Description 递归分组排序操作
*/
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);
}
/**
* @param array
* @param low
* @param mid
* @param high
* @Date 2022/1/21 19:56
* @Param
* @Return void
* @MetodName merge
* @Author wang
* @Description 合并操作
*/
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];
}
}
/**
* @param a
* @param b
* @Date 2022/1/21 12:04
* @Param
* @Return boolean
* @MetodName greater
* @Author wang
* @Description 比较方法,比较a元素是否小于b元素
*/
public static boolean lessThan(Comparable a, Comparable b) {
return a.compareTo(b) < 0;
}
}
文章评论