常用排序汇总.docxVIP

思想:初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。packagecom.sort; 2//不稳定 3importjava.util.Arrays; 4 5publicclassHeapSort { 6publicstaticvoid main(String[] args) { 7int[] a={49,38,65,97,76,13,27,49,78,34,12,64}; 8intarrayLength=a.length; 9//循环建堆 10for(inti=0;iarrayLength-1;i++){ 11//建堆 12buildMaxHeap(a,arrayLength-1-i); 13//交换堆顶和最后一个元素 14 swap(a,0,arrayLength-1-i); 15System.out.println(Arrays.toString(a)); 16 } 17 }18//对data数组从0到lastIndex建大顶堆19publicstaticvoidbuildMaxHeap(int[] data, intlastIndex){20//从lastIndex处节点（最后一个节点）的父节点开始 21for(inti=(lastIndex-1)/2;i=0;i--){22//k保存正在判断的节点 23int k=i;24//如果当前k节点的子节点存在 25while(k*2+1=lastIndex){26//k节点的左子节点的索引 27intbiggerIndex=2*k+1;28//如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在29if(biggerIndexlastIndex){ 30//若果右子节点的值较大 31if(data[biggerIndex]data[biggerIndex+1]){ 32//biggerIndex总是记录较大子节点的索引 33biggerIndex++; 34 } 35 } 36//如果k节点的值小于其较大的子节点的值 37if(data[k]data[biggerIndex]){ 38//交换他们 39 swap(data,k,biggerIndex); 40//将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值 41 k=biggerIndex; 42 }else{ 43break; 44 } 45 }46 }47 }48//交换49privatestaticvoid swap(int[] data, inti, int j) { 50inttmp=data[i]; 51 data[i]=data[j]; 52 data[j]=tmp; 53 } 54 }冒泡排序：比较SB，只适合教学，效率低，但易实现。但能保证稳定。选择排序：比冒泡排序好一点，好的地方是交换次数少了，但仍然很SB。而且不稳定。插入排序：有点像打扑克牌时的排序，但插入时会让数组的移动变多，如果是链表则效率很高。且能保证稳定。归并排序：典型地递归分治，缺点是需要额外的空间来存储结果。但能保证稳定。快速排序：跟归并排序很像，但区别是归并排序切分的中点是数组索引，快速排序切分的中点是第一个数据的值。相同的是，都要碰运气。但不稳定。堆排序：思路很特别，花了好几个班车上的时间片，另外用了扑克牌演示每一步的过程才弄明白流程。但不稳定。