Java 排序（快排，归并）
浏览数：27 /
时间：2015年06月08日
Java 排序有Java.util.Arrays的sort方法，具体查看JDK API（一般都是用快排实现的，有的是用归并）
1 package yxy; 2 3 import java.util.Arrays; 4 5 public class Test { 6 7 public static void main(String[] args) { 8 // TODO Auto-generated method stub 9 int[] arrs = { 1,0,5,9 }; 10 Arrays.sort(arrs); 11 for (int a : arrs) { 12 System.out.print(a+"\t"); 13 } 14 } 15 }
运行结果：
0 1 5 9
但是如果我是想让从大到小排序呢，（可以逆序输出吧，一边儿呆着去，我是想让数组自己就从大到小排序）（http://luoqidunwu.iteye.com/blog/1571687）
1 package yxy; 2 3 import java.util.Arrays; 4 import java.util.Comparator; 5 6 class DownCompare implements Comparator<Integer> { 7 8 @Override 9 public int compare(Integer o1, Integer o2) { 10 // TODO Auto-generated method stub 11 // return o1==02?0:(o1<o2?1:-1); 12 if (o1.intValue() < o2) { 13 return 1; 14 } else if (o1 == o2) { 15 return 0; 16 } else { 17 return -1; 18 } 19 } 20 21 } 22 23 public class Test { 24 25 public static void main(String[] args) { 26 // TODO Auto-generated method stub 27 Integer[] arrs = { 1, 0, 5, 9 }; 28 Arrays.sort(arrs, new DownCompare()); 29 for (int a : arrs) { 30 System.out.print(a + "\t"); 31 } 32 } 33 }
运行结果：
9 5 1 0
其实是这个方法，需要写一个类继承Comparator接口
sort(T[] a, Comparator<? super T> c) 根据指定比较器产生的顺序对指定对象数组进行排序。
如果说自己写快排呢
先说点儿快排稳定性的吧，快排是不稳定的，比如说 5 8(a) 8(b) 1（a） 1(b) 选5作为枢纽元素，排序后1((b) 1(a) 5 8(b) 8(a)
1 //参考：http://www.algolist.net/Algorithms/Sorting/Quicksort 2 package yxy; 3 4 class QuickSort { 5 int partition(int arr[], int left, int right) { 6 int i = left, j = right; 7 int tmp; 8 int pivot = arr[(left + right) / 2]; // 选择中间元素作为枢元 9 //若改为int pivot = left; ：则 java.lang.StackOverflowError 10 11 while (i < j) { //若改为i<=j: 则java.lang.StackOverflowError 12 while (arr[i] < pivot) 13 i++; 14 while (arr[j] > pivot) 15 j--; 16 if (i <= j) { //若改为 i<j :则java.lang.StackOverflowError 17 tmp = arr[i]; 18 arr[i] = arr[j]; 19 arr[j] = tmp; 20 i++; 21 j--; 22 } 23 } 24 return i; 25 } 26 27 void quickSort(int arr[], int left, int right) { 28 if (arr == null || arr.length <= 1) 29 return; 30 int index = partition(arr, left, right); 31 if (left < index) 32 quickSort(arr, left, index - 1); 33 if (index < right) 34 quickSort(arr, index, right); 35 } 36 } 37 38 public class Test2 { 39 40 public static void main(String[] args) { 41 // TODO Auto-generated method stub 42 int[] arr = { 1, 0, 5, 9 }; 43 new QuickSort().quickSort(arr, 0, arr.length - 1); 44 for (int a : arr) { 45 System.out.print(a + "\t"); 46 } 47 } 48 49 }
对快排不熟悉，为什么改变代码会出现java.lang.StackOverflowError不清楚
明哥给我说的方法，很好理解（下面估计说不清，画个图看看就容易理解了），枢纽元素选择最后一个，然后2个下标指针i,s都指向开始，s的作用是指向i扫描过的第一个比枢纽元素大的位置，i扫描到比枢纽元素小的就和s位置的换，i位置比枢纽元素大的就直接i++
1 package yxy; 2 3 class QuickSort { 4 5 void quickSort(int arr[], int left, int right) { 6 if (arr == null || arr.length <= 1 || left > right) { 7 return; 8 } 9 int i = left, s = left, p = right, tmp; // p指向枢元的位置，i一直往下走，当遇到比arr[p]小的元素时和arr[s]交换 10 while (i < p) { 11 if (arr[i] < arr[p]) { 12 tmp = arr[i]; // 这三句，如果刚开始的元素都小于枢纽元素，则都是自己和自己交换，影响效率，可以判断i和s是否相等，相等就不交换了 13 arr[i] = arr[s]; 14 arr[s] = tmp; 15 i++; 16 s++; 17 } else { 18 i++; 19 } 20 } 21 tmp = arr[s]; 22 arr[s] = arr[p]; 23 arr[p] = tmp; 24 quickSort(arr, left, s - 1); 25 quickSort(arr, s + 1, right); 26 } 27 } 28 29 public class Test2 { 30 31 public static void main(String[] args) { 32 // TODO Auto-generated method stub 33 int[] arr = { 1, 0, 5, 9 }; 34 new QuickSort().quickSort(arr, 0, arr.length - 1); 35 for (int a : arr) { 36 System.out.print(a + "\t"); 37 } 38 } 39 40 }
12、13、14和21、22、23这么写太麻烦了，写个函数吧
1 void swap(int a,int b){ 2 int tmp; 3 tmp=a; 4 b=a; 5 a=tmp; 6 }
哇，不行哇，哦，java传递参数的问题，记起刚学C时经常碰到这个问题了吧
1 void swap(Integer a,Integer b){ 2 Integer tmp; 3 tmp=a; 4 b=a; 5 a=tmp; 6 }
这个也不行
详情参考：http://bbs.csdn.net/topics/390245117 28楼
归并排序
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
