首页 > 代码库 > 希尔排序(java)
希尔排序(java)
时间复杂度为O( n^(3/2) )
不是一个稳定的排序算法
如何看一个算法是否稳定:
{("scala",12),("python",34),("c++",12),("c",76),("java",44)}
scala和c++的值相等,排序前scala在c++的前面
如果排序后
{("scala",12),("c++",12),("python",34),("java",44),("c",76)}//scala还是在c++的前面,稳定
{("c++",12),("scala",12),("python",34),("java",44),("c",76)}//scala在c++的后面,不稳定
package com.sort.shell;public class ShellSort { public static void swap(int[] list, int a, int b){ int temp; temp = list[a]; list[a] = list[b]; list[b] = temp; } public static void print(int list[]){ for(int i=0; i<list.length; i++){ System.out.print(" "+list[i]); } } /** * {0,9,1,5,8,3,7,4,6,2} * * int increment = L.length-1; * 设置一个增量increment * increment = increment/3+1; * increment=4 * i=5 , 从5号到9号遍历 * 让1号和5号比较,如果1号大于5号,就交换位置 * 2号和6号比较,如果2号不大于6号,就不动 * 3号和7号比较、(3-4)!> 0,结束 * 4号和8号比较 (4-4)!> 0,结束 * 5号和9号比较,发现(5-4=1)>0,就让1号和5号比较,(1-4)!>0,结束 * * increment = increment/3+1; * increment=2 * i=3,从3号到9号遍历 * 1号和3号比较(1-3)!> 0,结束 * 2号和4号比较 * 3号和5号比较,1号和3号比较 * 4号和6号比较,2号和4号比较 * 5号和7号比较,3号和5号比较,1号和3号比较 * 6号和8号比较,4号和6号比较,2号和4号比较 * 7号和9号比较,5号和7号比较,3号和5号比较,1号和3号比较 * * increment = increment/3+1; * increment = 1 * 2号到9号遍历 * 2号和1号比较 * 3号和2号比较 * ....... * * */ public static void shellSort(int[] L){ int i,j; int increment = L.length-1; do{ increment = increment/3+1; //增量序列 for(i=increment+1; i<=L.length-1; i++){ if(L[i] < L[i-increment]){ L[0] = L[i]; // 暂存在L[0] for(j=i-increment; j>0 && L[0]<L[j]; j-=increment){ L[j+increment] = L[j]; //记录后移,查找插入位置 } L[j+increment] = L[0]; //插入 } } }while(increment > 1); } public static void sort(int[] list){ //前奏工作 int [] L = new int[list.length+1]; L[0] = 0; // 让0号元素为作为暂存数据的位置 for(int i=1; i<L.length; i++){ L[i] = list[i-1]; } shellSort(L);//进行希尔排序 //收尾工作 for(int i=1; i<L.length; i++){ list[i-1] = L[i]; } } public static void main(String[] args) { int [] list = new int[]{9,1,5,8,3,7,4,6,2}; print(list); System.out.println(); sort(list); print(list); } }
希尔排序(java)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。