程序员必须知道的8大排序Java版源代码

package com.my.sort; import java.util.Arrays; /*** * Title:HeapSort.java * Description:堆排序 * Company: www.bjfulei.com.cn * author： mingliang * mail: 996036006@qq.com * date: 2017年1月11日 下午4:26:44 * 基本思想：堆排序是一种树形选择排序，是对直接选择排序的有效改进。 * 堆的定义如下：具有n个元素的序列（h1,h2,...,hn), * 当且仅当满足（hi>=h2i,hi>=2i+1） 或（hi<=h2i,hi<=2i+1）(i=1,2,...,n/2)时称之为堆。 * 在这里只讨论满足前者条件的堆。由堆的定义可以看出，堆顶元素（即第一个元素）必为最大项（大顶堆）。 * 完全二叉树可以很直观地表示堆的结构。堆顶为根，其它为左子树、右子树。 * 初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。 * 然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。 * 依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程， * 一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。 * 一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。 * * 一般都用数组来表示堆，i结点的父结点下标就为(i – 1) / 2。 * 它的左右子结点下标分别为2 * i + 1和2 * i + 2。 * 如第0个结点左右子结点下标分别为1和2。 */ public class HeapSort { public static void heapSort(int[] a){ System.out.println("开始排序"); int arrayLength=a.length; //循环建堆 for(int i=0;i<arrayLength-1;i++){ //建堆 buildMaxHeap(a,arrayLength-1-i); //交换堆顶和最后一个元素 swap(a,0,arrayLength-1-i); System.out.println(Arrays.toString(a)); } } private static void swap(int[] data, int i, int j) { int tmp=data[i]; data[i]=data[j]; data[j]=tmp; } //对data数组从0到lastIndex建大顶堆 private static void buildMaxHeap(int[] data, int lastIndex) { //从lastIndex处节点（最后一个节点）的父节点开始 for(int i=(lastIndex-1)/2;i>=0;i--){ //k保存正在判断的节点 int k=i; //如果当前k节点的子节点存在 while(k*2+1<=lastIndex){ //k节点的左子节点的索引 int biggerIndex=2*k+1; //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 if(biggerIndex<lastIndex){ //若果右子节点的值较大 if(data[biggerIndex]<data[biggerIndex+1]){ //biggerIndex总是记录较大子节点的索引 biggerIndex++; } } //如果k节点的值小于其较大的子节点的值 if(data[k]<data[biggerIndex]){ //交换他们 swap(data,k,biggerIndex); //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值 k=biggerIndex; }else{ break; } } } } public static int[] myHeapSort(int[] arr){ //二叉树层数 int in=arr.length; int ret[]=new int[arr.length]; int sort[]=arr; int start=0; while(true){ if(in!=arr.length){ start=1; } int[] copy = new int[sort.length-start]; System.arraycopy(sort, start, copy, 0,sort.length-start); sort = copy; int len=sort.length; int tst=(int)Math.log(len)+1; for(int j=tst;j>0;j--){ //每层最后一个元素的下标 int max=(int)(Math.pow(2, j+1))-2; if(len-1<max){ max=len-1; } for(int i=max;i>0;i--){ int top_index=(i-1) / 2; int left_index=2 * top_index + 1; int right_index=2 * top_index + 2; //System.out.println("left="+left_index+" i="+i+" j="+j); int temp=sort[left_index]; int temp_index=left_index; if(sort[top_index]>sort[left_index]){ temp=sort[top_index]; temp_index=top_index; } //右节点不存在 if(right_index<=len-1){ if(temp<sort[right_index]){ temp=sort[right_index]; temp_index=right_index; } } if(temp_index!=top_index){ int tem=sort[top_index]; sort[top_index]=temp; sort[temp_index]=tem; } i=left_index; //到达该层的最小节点 int _min_index=(int)(Math.pow(2, j))-1; if(left_index==_min_index){ /*System.out.println("\n第"+j+"层比较结束"); for(int so:sort) System.out.print(so+" ");*/ break; } } } ret[in-1]=sort[0]; in--; if(in==1){ ret[1]=sort[0]; ret[0]=sort[1]; break; } } return ret; } public static void main(String[] args) { // TODO Auto-generated method stub //int sort[]={49,38,65,97,76,13,27,49,78,34,12,64,5,4,62,99,98,54,56,17,18,23,34,15,35,25,53,51}; int sort[]={1,2,3,100,19,36,7,25,17}; heapSort(sort); //int[] ret=myHeapSort(sort); for(int so:sort) System.out.print(so+" "); /*for(int so:sort) System.out.print(so+" ");*/ } }