Shell排序(希尔)算法--java
1 package com.zc.manythread; 2 /** 3 * 4 * @author 偶my耶 5 * 6 */ 7 public class ShellSort { 8 public static int count = 0; 9 10 public static void shellSort(int[] data) { 11 // 计算出最大的h值 12 int h = 1; 13 while (h <= data.length / 3) { 14 h = h * 3 + 1; 15 } 16 while (h > 0) { 17 for (int i = h; i < data.length; i += h) { 18 if (data[i] < data[i - h]) { 19 int tmp = data[i]; 20 int j = i - h; 21 while (j >= 0 && data[j] > tmp) { 22 data[j + h] = data[j]; 23 j -= h; 24 } 25 data[j + h] = tmp; 26 print(data); 27 } 28 } 29 // 计算出下一个h值 30 h = (h - 1) / 3; 31 } 32 } 33 34 public static void print(int[] data) { 35 for (int i = 0; i < data.length; i++) { 36 System.out.print(data[i] + "\t"); 37 } 38 System.out.println(); 39 } 40 public static void main(String[] args) { 41 42 int[] data = new int[] { 4, 3, 6, 2, 1, 9, 5, 8, 7 }; 43 print(data); 44 shellSort(data); 45 print(data); 46 47 } 48 }
运行结果:
Shell排序是不稳定的,它的空间开销也是O(1),时间开销估计在O(N3/2)~O(N7/6)之间
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。