ava讲讲几种常见的排序算法（二） 目录 java讲讲几种常见的排序算法(一) java讲讲几种常见的排序算法(二) 堆排序 思路：构建一个小顶堆，小顶堆就是棵二叉树，他的左右孩子均大于他的根节点（大顶堆反之）。 构建完一个小顶堆后，开始排序。 将最后一个节点和第一个节点交换位置（根节点是最小的，最小的顶点放到了后面），交换后进行调整，保持小顶堆（次小的顶点到了根节点）。 依次执行下去，这样每一次交换将最小的顶点的放到了最后，所以最后数组会从大到小排列。 public static void heapSort(int array[]) { int j=array.length; //构建堆 for (int i = j/2-1; i >=0; i--) { f(i,j,array); } //堆排序，从后面的节点开始更第一个节点交换位置，然后进行调整，这样数组将从大到小排列 for (int i = j-1; i>=0; i--) { // System.out.println(array[0]); swap(array,i,0); f(0,i,array); } } public static void f(int low,int high,int array[]) { int i=low; int j=2*i+1; int temp=array[i]; while(jarray[j+1]) j++; //如果大于根节点，进行上浮，将该节点上浮，对下面的子树再进行调整 if(array[j]>bucketList=new ArrayList>(10); for (int i = 0; i < 10; i++) { bucketList.add(new LinkedList()); } return bucketList; } public static void bucketSort(int array[],int base,List> bucketList) { //100以内的数，超过100不用再就千分位的数 if(base==1000) return; for (int i = 0; i < array.length; i++) { LinkedList bucket=bucketList.get((array[i]/base)%10); bucket.add(array[i]); } int index=0; for (int i = 0; i < bucketList.size(); i++) { LinkedList bucket=bucketList.get(i); if(bucket.isEmpty()) continue; else { while(!bucket.isEmpty()) { array[index]=bucket.poll(); index++; } } } bucketSort(array,base*10,bucketList); } 归并排序 思路：将一个数组分成两部分（A,B）。 A实现左边有序，再实现右边有序，然后进行合并，最后实现A这一个大部分实现有序。 然后B同样进行以上同样的操作，最后B这一大部分实现有序，最后，AB合并，实现整体有序。 同样，在实现A的有序也是自底向上进行合并的。 public static void mergeSort(int array[],int first,int end,int temp[]) { int mid=(first+end)/2; if(first

关键字：