首页 / JAVA / 插入排序与希尔排序Java实现
插入排序与希尔排序Java实现
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了插入排序与希尔排序Java实现,小编现在分享给大家,供广大互联网技能从业者学习和参考。文章包含1957字,纯文字阅读大概需要3分钟。
内容图文
![插入排序与希尔排序Java实现](/upload/InfoBanner/zyjiaocheng/1214/b22f9a7a39c64c94b97cda355ff086d1.jpg)
public class TestMain { public static void main(String[] args) { Integer[] a = new Integer[5000]; for (int i = 0; i < a.length; i++) { int temp = (int)(StdRandom.random()*10000); a[i] = temp; } Integer[] b = new Integer[5000]; for (int i = 0; i < b.length; i++) { b[i] = a[i]; } //生成两个相同的随机数组 Stopwatch timer2 = new Stopwatch(); ToSort.insertsort(b); System.out.println(timer2.elapsedTime()); //比较两种排序运行的时间 Stopwatch timer = new Stopwatch(); ToSort.shellsort(a); System.out.println(timer.elapsedTime()); } } class ToSort{ /* * 插入排序 * 时间复杂度O(N^2) N为数组长度 */publicstaticvoid insertSort(Comparable[] a) { for (int i = 1; i < a.length; i++) { //从 1项开始,递增项数,将前 i 项进行排序 //int temp = (int) a[i];int j; for ( j = i; j > 0 && less(a[j] /*如果改为右移这里则改为 temp*/, a[j-1]); j--) { //前 i-1 项为已排好序的数组,将第 i 项与 i-1 项比较,比前面的小则交换两项,然后继续比较 i-1 和 i-2 //例子:1,4,8,3 排序后将 3 插入到了 4 前面 1,3,4,8 exch(a, j, j-1); //这里将交换改为右移可以提高速度 a[j] = a[j-1]; } //a[j] = temp; } } /* * 希尔排序 */publicstaticvoid shellSort(Comparable[] a) { int T = a.length; int h = 1; while(h<T/3) h = h*3 + 1; //使用 1, 4, 13, 40, 121这个希尔序列while (h >= 1) { //当 h 为 1 时,其实就是插入排序,但前面的工作可以使整个过程变快for (int i = h; i < T; i++) { //按当前间隔 h 进行比较,从第一个数开始每隔 h 取一个数,组成数组,进行排序。for (int j = i; j >= h && less(a[j], a[j-h]) ; j -= h) { exch(a, j, j-h); } } h = h/3; } } /* * 判断是否v < w */privatestaticboolean less(Comparable v, Comparable w) { return v.compareTo(w) < 0; //+1则false,-1则true } /* * 交换a[i]与a[j]的值 */privatestaticvoid exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } /* * 打印出数组 */publicstaticvoid show(Comparable[] a) { for (Comparable comparable : a) { System.out.print(comparable+" "); } System.out.println(); } /* * 判断数组是否有序 */publicstaticboolean isSorted(Comparable[] a) { for (int i = 1; i < a.length; i++) { if (less(a[i], a[i-1])) returnfalse; } returntrue; } }
希尔排序示意图
原文:http://www.cnblogs.com/zhangqi66/p/7244442.html
内容总结
以上是互联网集市为您收集整理的插入排序与希尔排序Java实现全部内容,希望文章能够帮你解决插入排序与希尔排序Java实现所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错,欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明:本文内容由互联网用户自发贡献,该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 gblab@vip.qq.com 举报,一经查实,本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。