第一种排序:【冒泡排序】基本数据类型的排序。
【1】最简易的冒泡排序。效率低。因为比较的次数和趟数最多。
1 /** 2 * 最原始的冒泡排序。 3 * 效率低。 4 * 因为趟数和次数最多。都是按最大化的循环次数进行循环 5 * @Title: sort 6 * @Description: TODO(这里用一句话描述这个方法的作用) 7 * @param arr 8 * @return void 返回类型 9 * @author 尚晓飞 10 * @date 2014-8-5 上午8:42:45 11 */ 12 public static void sort(int[] arr){ 13 //要走arr.length-1趟 14 for(int i=0;i<arr.length-1;i++){ 15 System.out.println("第"+(i+1)+"趟"); 16 for(int j=0;j<arr.length-1;j++){ 17 18 if(arr[j]>arr[j+1]){ 19 int temp=arr[j]; 20 arr[j]=arr[j+1]; 21 arr[j+1]=temp; 22 23 } 24 System.out.println("第"+(j+1)+"次"+Arrays.toString(arr)); 25 } 26 } 27 System.out.println("TestSort.sort01()"+Arrays.toString(arr)); 28 }
【2】进行一次优化的冒泡排序。减少每趟的比较次数。
1 /** 2 * 冒泡排序,减少每趟比较的次数. 3 * 每一趟都能找到数列中相对最大的一个数。 4 * 而每一次,都是进行数列中每两个相邻的数进行比较。需要比较数列长度-1次。才能完成一趟。 5 * 由于每一趟都找出一个最大数,所以,找出的最大数,就不用再比较了,因此每一趟的比较次数就随着趟数的增加而减少。 6 * @Title: sort01 7 * @Description: TODO(这里用一句话描述这个方法的作用) 8 * @param arr 9 * @return void 返回类型 10 * @author 尚晓飞 11 * @date 2014-8-4 下午8:37:45 12 */ 13 public static void sort01(int[] arr){ 14 //要走arr.length-1趟 15 for(int i=0;i<arr.length-1;i++){ 16 System.out.println("第"+(i+1)+"趟"); 17 for(int j=0;j<arr.length-1-i;j++){ 18 19 if(arr[j]>arr[j+1]){ 20 int temp=arr[j]; 21 arr[j]=arr[j+1]; 22 arr[j+1]=temp; 23 } 24 System.out.println("第"+(j+1)+"次"+Arrays.toString(arr)); 25 } 26 } 27 System.out.println("TestSort.sort01()"+Arrays.toString(arr)); 28 }
【3】进行最终的优化。减少比较的趟数和次数
1 /** 2 * 冒泡排序。最终版,减少趟数并且也减少每趟的次数 3 * @Title: sort02 4 * @Description: TODO(这里用一句话描述这个方法的作用) 5 * @param arr 6 * @return void 返回类型 7 * @author 尚晓飞 8 * @date 2014-8-4 下午8:52:59 9 */ 10 public static void sort02(int[] arr){ 11 //建立一个标示。如果数列已经排序完毕,则跳出循环,提高效率 12 boolean flag=true; 13 for(int i=0;i<arr.length-1;i++){ 14 System.out.println("第"+(i+1)+"趟"); 15 flag=true; 16 for(int j=0;j<arr.length-1-i;j++){ 17 18 if(arr[j]>arr[j+1]){ 19 int temp=arr[j]; 20 arr[j]=arr[j+1]; 21 arr[j+1]=temp; 22 //如果有相邻数字互换位置,说明数列还没有排好序,则将标示改成false,不让跳出循环 23 flag=false; 24 } 25 System.out.println("第"+(j+1)+"次"+Arrays.toString(arr)); 26 } 27 28 //在某一趟,已经没有相邻数据交换位置,说明,顺序已经排好,则跳出本层循环 29 if(flag){ 30 break; 31 } 32 33 34 } 35 System.out.println("TestSort.sort02()"+Arrays.toString(arr)); 36 }
break,continu,return的区别:
break---->用于终止break所在的本层循环,对本层循环后边同层相邻的代码无影响,会执行后边的代码。
continu-->用于暂停本次循环,不执行continu后边循环体内的代码,继续下次循环。
return--->用于返回方法。无论多少层循环,无论处于什么位置,一旦执行到return,则方法终止运行。后边的代码,无论本层,还是他层,一概不执行。
第二种排序:引用数据类型的排序。
【A】[内置引用类型(String Date Integer等),自定义引用类型]
实现步骤:(1)实现一个接口。java.lang.Comparable
(2)重写一个方法public int compareTo(Object obj)
(3)返回 0 表示 this=obj
返回 正数 表示this>obj
返回 负数 表示 this<obj
第一种:常用内置类的比较规则
[1]Integer --->首先将两个包装类,转换成基本数据类型。然后进行大小比较。
[2]Character---> 字符类比较规则是:先将两个字符转换成对应的unicode值,然后进行相减。从而比较大小。
[3]String
---->从两个字符串的第一个字符开始,逐个对应字符进行比较,如果遇见字符不同,返回字符的unicode码之差,后边字符不在对比,比较。决定两个字符串的大小。
---->如果一个字符串是另一个子符串的起始子字符串,则进行长度差比较。比如:abc.compareTo(abcde)进行比较,返回-2
[4]Date--->将两个时间都转换成长整形数,然后比较两个数的大小。决定谁大谁小
1 Integer a;//首先将两个包装类,转换成基本数据类型。然后进行大小比较。 2 public int compareTo(Integer anotherInteger) { 3 int thisVal = this.value; 4 int anotherVal = anotherInteger.value; 5 return (thisVal<anotherVal ? -1 : (thisVal==anotherVal ? 0 : 1)); 6 } 7 8 9 10 //字符类比较规则是:先将两个字符转换成对应的unicode值,然后进行相减。从而比较大小。 11 Character adCharacter;//字符的排序规则: 12 public int compareTo(Character anotherCharacter) { 13 return this.value - anotherCharacter.value; 14 } 15 16 17 String aString; 18 //字符串的比较规则 19 //(1)从两个字符串的第一个字符开始,逐个对应字符进行比较,如果遇见字符不同,返回字符的unicode码之差,后边字符不在对比,比较。决定两个字符串的大小。 20 //(2)如果一个字符串是另一个子符串的起始子字符串,则进行长度差比较。比如:abc.compareTo(abcde)进行比较,返回-2 21 public int compareTo(String anotherString) { 22 int len1 = count; 23 int len2 = anotherString.count; 24 int n = Math.min(len1, len2); 25 char v1[] = value; 26 char v2[] = anotherString.value; 27 int i = offset; 28 int j = anotherString.offset; 29 30 if (i == j) { 31 int k = i; 32 int lim = n + i; 33 while (k < lim) { 34 char c1 = v1[k]; 35 char c2 = v2[k]; 36 if (c1 != c2) { 37 return c1 - c2; 38 } 39 k++; 40 } 41 } else { 42 while (n-- != 0) { 43 char c1 = v1[i++]; 44 char c2 = v2[j++]; 45 if (c1 != c2) { 46 return c1 - c2; 47 } 48 } 49 } 50 return len1 - len2; 51 } 52 53 54 //比较规则:将两个时间都转换成长整形数,然后比较两个数的大小。决定谁大谁小 55 Date aDate; 56 public int compareTo(Date anotherDate) { 57 long thisTime = getMillisOf(this); 58 long anotherTime = getMillisOf(anotherDate); 59 return (thisTime<anotherTime ? -1 : (thisTime==anotherTime ? 0 : 1)); 60 }
【B】[jdk内置引用类型性,自定义比较规则]
实现步骤:(1)实现一个接口。java.util.Comparator
(2)重写一个方法public int compare(String o1, String o2)
(3)返回 0 表示 o1=o2
返回 正数 表示o1>o2
返回 负数 表示 o1<o2
内置引用类型实现java.lang.Comparable接口定义比较规则和自定义规则实现java.util.Comparator接口的不同之处和区别
1 /** 2 * 自定义对象的比较规则:实现的是java.util.Comparator接口 3 * 【1】可以作为一个独立的比较器,进行两个对象之间按某种自定义的规则比较 4 * 【2】可以作为一个工具 5 */ 6 7 public class MyCompa2 implements java.util.Comparator<String>{ 8 @Override 9 public int compare(String o1, String o2) { 10 // TODO Auto-generated method stub 11 //自定义规则 12 return 0; 13 } 14 15 /** 16 * jdk内置类的比较规则,实现java.lang.Comparable接口 17 * 【1】本类对象的比较器,私有化。 18 * 19 * 20 */ 21 public class MyCompa implements Comparable<String> { 22 23 @Override 24 public int compareTo(String obj) { 25 // TODO Auto-generated method stub 26 //写比较规则的代码 27 //return :正数 this>obj 0 this==obj 负数 this<obj 28 return 0; 29 }
封装的一个排序工具类,结合了冒泡排序和内置类排序规则和自定义排序规则。代码示范
1 /** 2 * 公共的比较器。自定义字符串的比较规则。按字符串长度进行比较 3 * @ClassName: MyCompa2 4 * @Description: TODO(这里用一句话描述这个类的作用) 5 * @author 尚晓飞 6 * @date 2014-8-6 下午6:47:32 7 * 8 */ 9 public class MyCompa2 implements java.util.Comparator<String>{ 10 /** 11 * 自定义两个字符串的比较规则:按长度大小的比较 12 * @Title: compare 13 * @Description: TODO(这里用一句话描述这个方法的作用) 14 * @author 尚晓飞 15 * @date 2014-8-6 下午6:49:17 16 * @param o1 17 * @param o2 18 * @return 19 * @see java.util.Comparator#compare(java.lang.Object, java.lang.Object) 20 */ 21 @Override 22 public int compare(String o1, String o2) { 23 // TODO Auto-generated method stub 24 int a=o1.length(); 25 int b=o2.length(); 26 return a-b; 27 } 28 /**测试该比较器的方法。 29 * String[] str=new String[]{"abcdef","adc","abcde","abf","ab","a"}; 30 CompareUtil.sort2(str, new MyCompa2()); 31 System.out.println(Arrays.toString(str)); 32 打印结果:[a, ab, adc, abf, abcde, abcdef] 33 */ 34 35 } 36 37 38 39 40 /** 41 * 排序工具类 包括:内置引用类,自身的排序规则 42 * 内置引用类简单的自定义排序规则 43 * @ClassName: CompareUtil 44 * @Description: TODO(这里用一句话描述这个类的作用) 45 * @author 尚晓飞 46 * @date 2014-8-6 下午7:46:18 47 * 48 */ 49 public class CompareUtil { 50 /** 51 * 对容器进行排序+自定义的排序规则 52 * 53 *泛型方法的规则 54 * 【访问修饰符】 +【静态,非静态修饰符】+泛型+【返回值类型】+方法名(带泛型的参数列表){} 55 * 56 * @Title: sort3 57 * @Description: TODO(这里用一句话描述这个方法的作用) 58 * @param list 59 * @param comparator 60 * @return void 返回类型 61 * @author 尚晓飞 62 * @date 2014-8-6 下午7:09:54 63 */ 64 public static <T> void sort3(List<T> list,Comparator<T> comparator){ 65 //将容器转换成数组 66 Object[] arr=list.toArray(); 67 //对转换成的数组进行排序 68 sort2(arr, new MyCompa2()); 69 //将排好序的容器中的元素,按顺序重新放入容器 70 for(int i=0;i<arr.length;i++){ 71 list.set(i, (T)arr[i]); 72 } 73 } 74 75 /** 76 * 自定义规则的比较器。对字符串进行长度的排序(升序排列) 77 * MyCompa2是自定义规则的比较器 78 * @Title: sort2 79 * @Description: TODO(这里用一句话描述这个方法的作用) 80 * @param arr 81 * @param myCompa2 82 * @return void 返回类型 83 * @author 尚晓飞 84 * @date 2014-8-6 下午6:52:19 85 */ 86 public static <T> void sort2(Object[] arr,Comparator<T> comparator){ 87 for(int i=0;i<arr.length-1;i++){ 88 boolean flag=true; 89 for(int j=0;j<arr.length-1-i;j++){ 90 //进行比较 91 if(comparator.compare((T)arr[j], (T)arr[j+1])>0){ 92 Object temp=arr[j]; 93 arr[j]=arr[j+1]; 94 arr[j+1]=temp; 95 flag=false; 96 } 97 } 98 99 if(flag){ 100 break; 101 } 102 } 103 } 104 105 106 /** 107 *常用jdk内置引用类型的数据,进行升序排序 108 * @Title: sort 109 * @Description: TODO(这里用一句话描述这个方法的作用) 110 * @param obj 111 * @return void 返回类型 112 * @author 尚晓飞 113 * @date 2014-8-5 下午8:06:43 114 */ 115 public static void sort(Object[] obj){ 116 for(int i=0;i<obj.length-1;i++){ 117 boolean flag=true; 118 for(int j=0;j<obj.length-1-i;j++){ 119 //进行比较 120 if(((Comparable)obj[j]).compareTo(obj[j+1])>0){ 121 Object temp=obj[j]; 122 obj[j]=obj[j+1]; 123 obj[j+1]=temp; 124 flag=false; 125 } 126 } 127 128 if(flag){ 129 break; 130 } 131 } 132 } 133 134 /** 135 * 使用泛型方法进行排序(升序) 136 * @Title: sort2 137 * @Description: TODO(这里用一句话描述这个方法的作用) 138 * @param obj 139 * @return void 返回类型 140 * @author 尚晓飞 141 * @date 2014-8-5 下午8:25:02 142 */ 143 public static <T extends Comparable<T>> void sort2(T[] obj){ 144 for(int i=0;i<obj.length-1;i++){ 145 boolean flag=true; 146 for(int j=0;j<obj.length-1-i;j++){ 147 //进行比较 148 if(((Comparable)obj[j]).compareTo(obj[j+1])>0){ 149 T temp=obj[j]; 150 obj[j]=obj[j+1]; 151 obj[j+1]=temp; 152 flag=false; 153 } 154 } 155 156 if(flag){ 157 break; 158 } 159 } 160 161 } 162 163 /** 164 * 对list容器进行排序(升序) 165 * @Title: sort3 166 * @Description: TODO(这里用一句话描述这个方法的作用) 167 * @param list 168 * @return void 返回类型 169 * @author 尚晓飞 170 * @date 2014-8-5 下午8:29:44 171 */ 172 public static <T extends Comparable<T>> void sort3(List<T> list){ 173 //将list容器转换成数组 174 Object[] objects=list.toArray(); 175 //对数组进行排序 176 CompareUtil.sort(objects); 177 //改变容器中对应的值 178 for(int i=0;i<objects.length;i++){ 179 list.set(i, (T)objects[i]); 180 } 181 182 } 183 184 185 186 public static void main(String[] args) { 187 String[] aStrings={"dfb","cmd","bdsf","addf"}; 188 189 CompareUtil.sort(aStrings); 190 System.out.println(Arrays.toString(aStrings)); 191 } 192 }
java.util包中有一个Collections工具类对list容器进行排序。测试代码。
1 import java.util.ArrayList; 2 import java.util.Arrays; 3 import java.util.Collections; 4 import java.util.List; 5 /** 6 * java.util包中提供了一个工具类Collections对集合的排序 7 * 一种:使用jdk内置的排序规则(升序) 8 * 二种:使用java.utli.Comparator接口,重写方法,自定义排序规则 9 * @ClassName: Demo5 10 * @Description: TODO(这里用一句话描述这个类的作用) 11 * @author 尚晓飞 12 * @date 2014-8-6 下午8:07:18 13 * 14 */ 15 public class Demo5 { 16 public static void main(String[] args) { 17 // public static <T extends Comparable<? super T>> void sort(List<T> list) 18 //容器工具类,提供的排序方法一。规则,是jdk内部规则 19 List<Integer> list=new ArrayList<Integer>(); 20 21 list.add(10); 22 list.add(9); 23 list.add(8); 24 System.out.println(Arrays.toString(list.toArray()));//排序前,打印结果[10, 9, 8] 25 Collections.sort(list); 26 System.out.println(Arrays.toString(list.toArray()));//排序后,打印结果[8, 9, 10] 27 28 //public static <T> void sort(List<T> list, Comparator<? super T> c) 29 //容器工具类,提供的排序方法二.规则,自定义的。java.util.Comparator 30 List<String> list2=new ArrayList<String>(); 31 list2.add("abcdef"); 32 list2.add("abcde"); 33 list2.add("abcd"); 34 list2.add("abc"); 35 list2.add("ab"); 36 list2.add("a"); 37 System.out.println(Arrays.toString(list2.toArray()));//排序前:打印结果[abcdef, abcde, abcd, abc, ab, a] 38 Collections.sort(list2, new MyCompa2()); 39 System.out.println(Arrays.toString(list2.toArray()));//排序后:打印结果[a, ab, abc, abcd, abcde, abcdef] 40 41 } 42 43 }