首页 > 代码库 > java排序学习笔记
java排序学习笔记
前面写了js的排序实现，总得玩玩java的哈。
同样，冒泡、选择、快速（这三个之前实现过也写过文章）、堆排序，然后做比较。
主要遇到的难点：
- -||想轻松点写个封装计时的逻辑，不想每调用一个排序就要写一个计时代码。想想，还是javascript写起来方便；
java的话，我想到的方法是写一个抽象类：抽象出排序方法，实现一个排序计时方法（该方法调用了抽象排序，但在先后排序时加入计时代码[感觉像是aop操作]）；
接着所有排序类都继承这个抽象类，并实现排序方法，调用的时候直接调用继承的排序计时方法，这样就不用写多余的代码了。（不过这还搞继承，有点。。。不知道有啥高招呢？）
下面是展示各排序代码：
冒泡:
1 public class BubbleSort extends SortAbstract{ 2 3 public static void main(String[] args) { 4 int[] a = {1,8,5,6,3,7,5,4,8,9,12,2}; 5 new BubbleSort().sort(a); 6 for(int c : a){ 7 System.out.println(c); 8 } 9 }10 public void sort(int[] array){11 if(array.length == 0)return ;12 for(int i=0;i<array.length-1;i++){//i是计数标记13 for(int j=0;j<array.length-i-1;j++){//注意终止条件的判断,冒泡的亮点在于从头到尾一对一对比较14 if(array[j]>array[j+1]){15 swap(array, j, j+1);16 }17 }18 }19 }20 public static void swap(int[] array,int i,int j){21 int temp = array[i];22 array[i] = array[j];23 array[j] = temp;24 }25 }
选择：
1 public class ChooseSort extends SortAbstract{ 2 public static void main(String[] args) { 3 int[] a = {1,8,5,6,3,7,5,4,8,9,12,2}; 4 new ChooseSort().sort(a); 5 for(int c : a){ 6 System.out.println(c); 7 } 8 } 9 10 public void sort(int[] array){11 if(array.length == 0)return ;12 for(int i=0;i<array.length-1;i++){13 for(int j=i+1;j<array.length;j++){14 if(array[i]>array[j]){15 swap(array, i, j);16 }17 }18 }19 }20 21 public static void swap(int[] array,int i,int j){22 int temp = array[i];23 array[i] = array[j];24 array[j] = temp;25 }26 }
快速：
1 public class QuickSort extends SortAbstract{ 2 public static void qSort(int[] num,int low,int high){ 3 if(low<high){ 4 int pivotloc = partition(num,low,high); 5 qSort(num, low, pivotloc-1); 6 qSort(num, pivotloc+1, high); 7 } 8 } 9 public void sort(int[] array){10 qSort(array, 0, array.length-1);11 }12 public static int partition(int[] num,int low,int high){13 int mid = num[low];14 int pivotkey = num[low];15 while(low<high){16 while(low<high&&num[high]>=pivotkey){17 --high;18 }19 num[low] = num[high];20 while(low<high&&num[low]<=pivotkey){21 ++low;22 }23 num[high]=num[low];24 }25 num[low] = mid;26 return low;27 }28 /**29 * @param args30 */31 public static void main(String[] args) {32 // TODO Auto-generated method stub33 int[] num = {9,18,-8,-6,-57,5,62,0};34 qSort(num, 0, num.length-1);35 for(int i=0;i<num.length;i++){36 System.out.println(num[i]);37 }38 }39 40 }
堆：
1 public class HeapSort extends SortAbstract { 2 public void sort(int[] array){ 3 if(array.length<=1){ 4 return; 5 } 6 int len = array.length; 7 for(int i=len/2+1;i>=0;i--){//初始最大堆 无序数组，由最右一个非子节点开始。这里len/2 +1 没想明白 8 maxHeapify(array, i, len); 9 }10 for(int i = len-1; i>0; i-- ){11 swap(array, 0, i); //每次将堆根节点与尾部交换，然后逻辑上数组放弃掉尾部，实际有点像尾部冒泡12 maxHeapify(array, 0, --len); //从顶部开始顶堆调整13 }14 }15 public static int getLeft(int index){16 return index*2+1;17 }18 public static int getRight(int index){19 return (index+1)*2;20 }21 public static void swap(int[] array, int i, int j){22 int temp = array[i];23 array[i] = array[j];24 array[j] = temp;25 }26 public static void maxHeapify(int[] array, int index, int len){27 if(array.length==0 || len<=1){28 return;29 }30 int largest;31 int left = getLeft(index);32 int right = getRight(index);33 if(left<len&&array[index]<array[left]){34 largest = left;35 }else{36 largest = index;37 }38 if(right<len && array[right]>array[largest]){39 largest = right;40 }41 if(largest!=index){42 swap(array, largest, index); //交换两个位置的元素，并递归调用调整交换的孩子节点43 maxHeapify(array, largest, len);44 }45 }46 public static void main(String[] args){47 int[] a = {1,8,5,6,3,7,5,4,8,9,12,2};48 new HeapSort().sort(a);49 for(int c : a){50 System.out.println(c);51 }52 }53 }
计时抽象类：
1 public abstract class SortAbstract {2 public abstract void sort(int[] array);3 public void runWithTimer(int[] array){4 Date start = new Date();5 this.sort(array);6 Date end = new Date();7 System.out.println("排序时间：(ms)"+(end.getTime()-start.getTime()));8 }9 }
测试用例：
1 public class SortTestMain { 2 public static void main(String[] args){ 3 int[] small = {6,44,33,2,3,5,2,1,7,9,8,14}; 4 BubbleSort bubbleSort = new BubbleSort(); 5 ChooseSort chooseSort = new ChooseSort(); 6 QuickSort quickSort = new QuickSort(); 7 HeapSort heapSort = new HeapSort(); 8 System.out.println("冒泡排序："); 9 //int[] smallUse = small.clone();10 bubbleSort.runWithTimer(small.clone());11 System.out.println("选择排序：");12 chooseSort.runWithTimer(small.clone());13 System.out.println("快速排序：");14 quickSort.runWithTimer(small.clone());15 System.out.println("堆排序：");16 heapSort.runWithTimer(small.clone());17 18 System.out.println("对a[10000]排序：");19 int[] big = new int[10000];20 for(int i=0; i<10000; i++){21 big[i] = (int)Math.floor(Math.random()*100001);22 }23 System.out.println("冒泡排序：");24 //int[] smallUse = small.clone();25 bubbleSort.runWithTimer(big.clone());26 System.out.println("选择排序：");27 chooseSort.runWithTimer(big.clone());28 System.out.println("快速排序：");29 quickSort.runWithTimer(big.clone());30 System.out.println("堆排序：");31 heapSort.runWithTimer(big.clone());32 }33 }
测试结果：
结论：
几个元素的排序，基本很快。只有当数据开始多时，堆和快速开始展现出优势。
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。