常用数据结构与算法实现
以下博客根据B站罗召勇老师视频：数据结构与算法基础-Java版（罗召勇）写的详细笔记
数据结构与算法基础：
数据结构与算法之基础概述
数据结构：
（一）数据结构与算法之数组
（二）数组结构与算法之栈
（三）数据结构与算法之队列
（四）数据结构与算法之链表
（五）数据结构与算法之树结构基础
（六）数据结构与算法之二叉树大全
（七）数据结构与算法之Huffman tree(赫夫曼树 / 霍夫曼树 / 哈夫曼树 / 最优二叉树)
（八）数据结构与算法之多路查找树（2-3树、2-3-4树、B树、B+树）
（九）数据结构与算法之图结构
十大经典算法：
（一）数据结构与算法之冒泡排序（含改进版）
（二）数据结构与算法之选择排序（含改进版）
（三）数据结构与算法之插入排序（含改进版）
（四）数据结构与算法之希尔排序
（五）数据结构与算法之归并排序
（六）数据结构与算法之快速排序
（七）数据结构与算法之堆排序
（八）数据结构与算法之计数排序
（九）数据结构与算法之桶排序
（十）数据结构与算法之基数排序
希尔排序概念
希尔排序（Shell Sort）是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止
动图展示：
静图分析：
代码实现
import java.util.Arrays; public class ShellSort { public static void main(String[] args) { int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0}; shellSort(arr); // [3, 5, 1, 6, 0, 8, 9, 4, 7, 2] // [0, 2, 1, 4, 3, 5, 7, 6, 9, 8] // [0, 1, 2, 3, 4, 5, 6, 7, 8, 9] } //希尔排序 public static void shellSort(int[] arr) { //遍历所有的步长 for (int gap = arr.length / 2; gap > 0; gap = gap / 2) { //遍历所有的元素 for (int i = gap; i < arr.length; i++) { //遍历本组中所有元素 for (int j = i - gap; j >= 0; j -= gap) { //如果当前元素大于加上步长后的那个元素 if (arr[j] > arr[j + gap]) { int temp = arr[j]; arr[j] = arr[j + gap]; arr[j + gap] = temp; } } } //打印每次排序后的结果 System.out.println(Arrays.toString(arr)); } } }
时间复杂度
最优时间复杂度：根据步长序列的不同而不同
最坏时间复杂度：O(n^2)
稳定性：不稳定
希尔排序不像其他时间复杂度为O(N log2N)的排序算法那么快，但是比选择排序和插入排序这种时间复杂度为O(N2)的排序算法还是要快得多，而且非常容易实现。它在最坏情况下的执行效率和在平均情况下的执行效率相比不会降低多少，而快速排序除非采取特殊措施，否则在最坏情况下的执行效率变得非常差。
迄今为止，还无法从理论上精准地分析希尔排序的效率，有各种各样基于试验的评估，估计它的时间级介于O(N^3/2)与 O(N^7/6)之间。我们可以认为希尔排序的平均时间复杂度为o(n^1.3)。
