首页 > 代码库 > 一种时间复杂度为O(n)的排序方法(转载)
一种时间复杂度为O(n)的排序方法(转载)
原文地址:http://my.oschina.net/u/158457/blog/28536
排序的方法很特别,有点类似插入排序的味道
先看下代码
1 public class Sort { 2 private static boolean[] temp = new boolean[10000]; 3 4 /** 5 * @notice 注意参数中的array数组中的每个元素大小不能超过9999,而且不能有重复元素。 6 * 同时也就意味着array数组大小不能超过10000,其中元素大小在0-9999的这样一个范围。 7 */ 8 public void sort(int[] array) { 9 init(); 10 for (int i = 0; i < array.length; i++) { 11 temp[array[i]] = true;//这个是核心 保证了temp数组中子元素为true的对象是按array[i]中元素的正序进行排序的 12 } 13 14 int loc = 0; 15 for (int j = 0; j < temp.length; j++) { 16 if (temp[j]) 17 array[loc++] = j; 18 } 19 } 20 21 private void init()// 其实在此方法中通过传一个整数可以剪枝,而整数为array数组中元素的最大值 22 { 23 for (int i = 0; i < temp.length; i++) 24 temp[i] = false; 25 } 26 27 public void print(int[] array) { 28 for (int i = 0; i < array.length; i++) 29 System.out.print(array[i] + " "); 30 System.out.println(); 31 } 32 33 public static void main(String[] args) { 34 Sort sort = new Sort(); 35 int array[] = new int[] { 3, 5, 1, 2, 10, 88, 25, 66 }; 36 sort.print(array); 37 sort.sort(array); 38 sort.print(array); 39 } 40 }
核心代码
temp[array[i]] = true;
原作者提到了此方法存在的缺陷:1.数组不能重复 2.array数组中的每个元素大小不能超过9999
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。