提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

目录

前言

一、希尔排序

1.排序原理

2.希尔排序实现

2.1 希尔排序API

2.2 希尔排序实现

二、归并排序

1.排序原理

2.归并排序实现

2.1 归并排序API

2.2 归并排序实现

三、快速排序

1.排序原理

2.快速排序实现

2.1 快速排序API

2.2 快速排序实现

总结

前言

提示：这里可以添加本文要记录的大概内容：

自学JAVA数据结构笔记，跟学视频为：黑马程序员Java数据结构与java算法全套教程，数据结构+算法教程全资料发布，包含154张java数据结构图_哔哩哔哩_bilibili

提示：以下是本篇文章正文内容，下面案例可供参考

一、希尔排序

1.排序原理

1.选定一个增长量h，按照增长量h作为数据分组的依据，对数据进行分组；

2.对分好组的每一组数据完成插入排序；

3.减小增长量，最小减为1，重复第二步操作

2.希尔排序实现

2.1 希尔排序API

类名             Shell

构造方法      Shell()：创建Shell对象

成员方法 1.public static void sort(Comparable[] a)：对数组内的元素进行排序 2.private static boolean greater(Comparable v,Comparable w):判断v是否大于w 3.private static void exch(Comparable[] a,int i,int j)：交换a数组中，索引i和索引j处的值

2.2 希尔排序实现

希尔排序类：

package sort;public class Shell {public static void sort(Comparable[] nums){int len = nums.length;//确定增长量h的最大值int h = 1;while(h < len / 2){h = h * 2 + 1;}//当增长量h小于1时，排序结束while(h >= 1){for(int i = h;i < len;i ++){//找到待插入元素for(int j = i;j >= h;j -= h){if(greater(nums[j - h],nums[j])){//找到最小值，交换exch(nums,j - h,j);}else{break;}}}//更新h值h = h / 2;}}//判断v是否大于wprivate static boolean greater(Comparable v,Comparable w){return v.compareTo(w) > 0;}//交换private static void exch(Comparable[] nums,int i,int j){Comparable temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

测试类：

package sort;import java.util.Arrays;public class ShellTest {public static void main(String[] args) {Integer[] nums = {3,6,7,9,0,1,4,2,5,8};Shell.sort(nums);System.out.println(Arrays.toString(nums));}}

二、归并排序

1.排序原理

1.尽可能的一组数据拆分成两个元素相等的子组，并对每一个子组继续拆分，直到拆分后的每个子组的元素个数是 1为止。

2.将相邻的两个子组进行合并成一个有序的大组；

3.不断的重复步骤2，直到最终只有一个组为止。

2.归并排序实现

2.1 归并排序API

类 名                 Merge

构 造 方 法        Merge()：创建Merge对象

成 员 方 法        1.public static void sort(Comparable[] a)：对数组内的元素进行排序                                       2.private static void sort(Comparable[] a, int lo, int hi)：对数组a中从索引lo到索引hi之间的元素进 行排序

                        3.private static void merge(Comparable[] a, int lo, int mid, int hi):从索引lo到所以mid为一个子 组，从索引mid+1到索引hi为另一个子组，把数组a中的这两个子组的数据合并成一个有序的大组（从 索引lo到索引hi）

                        4.private static boolean less(Comparable v,Comparable w):判断v是否小于w  成 员 变 量      1.private static Comparable[] assist：完成归并操作需要的辅助数组

2.2 归并排序实现

归并排序类：

package sort;public class Merge {private static Comparable[] assist;//归并所需要的辅助数组//排序算法public static void sort(Comparable[] nums) {//根据输入数组的长度创建辅助数组assist = new Comparable[nums.length];//左指针int left = 0;//右指针int right = nums.length-1;//排序sort(nums, left, right);}//重写sortprivate static void sort(Comparable[] nums, int left, int right) {if (right <= left) {return;}int mid = left + (right - left) / 2;//对left到mid之间的元素进行排序；sort(nums, left, mid);//对mid+1到right之间的元素进行排序；sort(nums, mid + 1, right);//对lo到mid这组数据和mid到hi这组数据进行归并merge(nums, left, mid, right);}private static void merge(Comparable[] nums, int left, int mid, int right) {int i = left;       //指向assist数组中开始填充数据的索引int p1 = left;      //指向第一组数据的第一个元素int p2 = mid + 1;   //指向第二组数据的第一个元素//比较左边小组和右边小组中的元素大小，哪个小，就把哪个数据填充到assist数组中while(p1 <= mid && p2 <= right){if(less(nums[p1],nums[p2])){//如果p1比p2小，则将p1加入辅助数组assist[i++] = nums[p1++];}else{//如果p2比p1小，则将p2加入辅助数组assist[i++] = nums[p2++];}}//当第一组数据没有遍历完即p1没有走完//将p1剩下元素全部加入辅助数组中while(p1 <= mid){assist[i++] = nums[p1++];}//当第二组数据没有遍历完即p2没有走完//将p2剩下元素全部加入辅助数组中while (p2 <= right){assist[i++] = nums[p2++];}//最后将辅助数组中的数据全部放回nums中if (right + 1 - left >= 0) {System.arraycopy(assist, left, nums, left, right + 1 - left);}}//判断v是否小于wprivate static boolean less(Comparable v, Comparable w) {return v.compareTo(w) < 0;}}

测试类：

package sort;import java.util.Arrays;public class MergeTest {public static void main(String[] args) {Integer[] nums = {3,6,7,9,0,1,4,2,5,8};Merge.sort(nums);System.out.println(Arrays.toString(nums));}}

三、快速排序

1.排序原理

1.首先设定一个分界值，通过该分界值将数组分成左右两部分；

2.将大于或等于分界值的数据放到到数组右边，小于分界值的数据放到数组的左边。此时左边部分中各元素都小于 或等于分界值，而右边部分中各元素都大于或等于分界值；

3.然后，左边和右边的数据可以独立排序。对于左侧的数组数据，又可以取一个分界值，将该部分数据分成左右两 部分，同样在左边放置较小值，右边放置较大值。右侧的数组数据也可以做类似处理。

4.重复上述过程，可以看出，这是一个递归定义。通过递归将左侧部分排好序后，再递归排好右侧部分的顺序。当 左侧和右侧两个部分的数据排完序后，整个数组的排序也就完成了。

切分原理： 把一个数组切分成两个子数组的基本思想：

1.找一个基准值，用两个指针分别指向数组的头部和尾部；

2.先从尾部向头部开始搜索一个比基准值小的元素，搜索到即停止，并记录指针的位置；

3.再从头部向尾部开始搜索一个比基准值大的元素，搜索到即停止，并记录指针的位置；

4.交换当前左边指针位置和右边指针位置的元素；

5.重复2,3,4步骤，直到左边指针的值大于右边指针的值停止。

2.快速排序实现

2.1 快速排序API

类名                 Quick

构造方法          Quick()：创建Quick对象

成员方法          1.public static void sort(Comparable[] a)：对数组内的元素进行排序

                        2.private static void sort(Comparable[] a, int lo, int hi)：对数组a中从索引lo到索引hi之间的元素 进行排序

                        3.public static int partition(Comparable[] a,int lo,int hi):对数组a中，从索引 lo到索引 hi之间的元 素进行分组，并返回分组界限对应的索引

                        4.private static boolean less(Comparable v,Comparable w):判断v是否小于w                         5.private static void exch(Comparable[] a,int i,int j)：交换a数组中，索引i和索引j处的值

2.2 快速排序实现

快速排序类：

package sort;public class Quick {//排序算法public static void sort(Comparable[] nums) {//左指针int left = 0;//右指针int right = nums.length-1;//排序sort(nums, left, right);}//重写sortprivate static void sort(Comparable[] nums, int left, int right) {if (right <= left) {return;}//对nums数组中，从left到right的元素进行切分int partition = partition(nums, left, right);//对左边分组中的元素进行排序sort(nums, left, partition - 1);//对右边分组中的元素进行排序sort(nums, partition + 1, right);}private static int partition(Comparable[] nums, int left,int right) {Comparable key = nums[left];    //把最左边的元素当做基准值int p1 = left;               //初始指向最左边的元素int p2 = right + 1;          //初始指向左右侧的元素下一个位置//进行切分while(true){//先从右往左扫描，找到一个比基准值小的元素while(less(key,nums[--p2])){//循环停止，证明找到了一个比基准值小的元素if (p2 == left){//已经扫描到最左边了，无需继续扫描break;}}//再从左往右扫描，找一个比基准值大的元素//循环停止，证明找到了一个比基准值大的元素while(less(nums[++p1],key)){if (p1 == right){//已经扫描到了最右边了，无需继续扫描break;}}if (p1 >= p2){//扫描完了所有元素，结束循环break;}else{//交换p1和p2索引处的元素exch(nums,p1,p2);}}//交换最后p2索引处和基准值所在的索引处的值exch(nums,left,p2);//p2就是切分的界限return p2;}//判断v是否小于wprivate static boolean less(Comparable v, Comparable w) {return v.compareTo(w) < 0;}//交换private static void exch(Comparable[] nums,int i,int j){Comparable temp = nums[i];nums[i] = nums[j];nums[j] = temp;}
}

测试类：

package sort;import java.util.Arrays;public class QuickTest {public static void main(String[] args) {Integer[] nums = {3,6,7,9,0,1,4,2,5,8};Quick.sort(nums);System.out.println(Arrays.toString(nums));}}

总结

提示：这里对文章进行总结：