经典排序算法(三) —— Shell Sort 希尔排序
2021/12/15 7:19:51
本文主要是介绍经典排序算法(三) —— Shell Sort 希尔排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
目录- 简介
- 排序过程
- 实现
- 复杂度
简介
1959年由Shell发明,是第一个突破O(n2)的排序算法,是简单插入排序的改进版。
它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。
希尔排序在数组中采用跳跃式分组的策略,通过某个增量将数组元素划分为若干组,然后分组进行插入排序,随后逐步缩小增量,继续按组进行插入排序操作,直至增量为1。
希尔排序中对于增量序列的选择十分重要,直接影响到希尔排序的性能。一些经过优化的增量序列如Hibbard经过复杂证明可使得最坏时间复杂度为O(n^3/2)。
排序过程
实现
/** * 希尔排序 * * @param arr n * @return */ public static int[] sort(int[] arr) { int n = arr.length; int gap = n; while ((gap /= 2) != 0) { for (int i = 0; i + gap < n; i++) { int tmp = i; while (tmp != -1 && arr[tmp] < arr[tmp + gap]) { exchangeArrayEle(arr, tmp, tmp + gap); tmp -= 1; } } } return arr; } /** * 交换数组元素 * 临时变量法 * * @param nums 数组 * @param i 待交换元素i * @param j 待交换元素j */ public static void exchangeArrayEle(int[] nums, int i, int j) { Assert.assertNotNull(nums); int tmp = nums[i]; nums[i] = nums[j]; nums[j] = tmp; }
复杂度
O(n^3/2)
这篇关于经典排序算法(三) —— Shell Sort 希尔排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)