排序算法相关知识点( 二 ) _算法

堆排序使用的是二叉堆。它首先将所有的元素添加到一个堆上，然后不断移除最大的元素以获得一个排好序的线性表。
二叉堆(binary heap) 是一棵具有以下属性的二叉树：
1).它是一棵完全二叉树。
2).每个结点大于或等于它的任意一个孩子。

文章插图

上图中，只有a是一个堆。b的根(39)小于它的右孩子(42)，c和d的二叉树都不是完全的。
1.堆的存储
如果堆的大小事先知道，那么可以将堆存储到一个数组。数根在位置0处，它的两个孩子在位置1和位置2处。
对于位置i的结点，它的左子结点在位置2i+1处，它的右子结点在位置2i+2处，而它父结点在位置(i-1)/2处。

文章插图

2.添加一个新结点
为了给堆添加一个新结点，首先将它添加到堆的末尾，然后按如下方式重建这棵树：
将最后一个结点作为当前结点；
while(当前结点大于它的父结点){
将当前结点与它的父结点交换；
现在当前结点往上面进了一个层次；
}

文章插图

3.删除根结点
经常需要删除推中最大元素，也就是堆中的根结点。在删除根结点后，必须要重建这棵树以保持堆的属性：
用最后一个结点替换根结点；
让根结点成为当前结点；
while(当前结点具有子结点并且当前结点小于它的子结点){
将当前结点与它的较大子结点交换；
现在当前结点往下面退了一个层次；
}

文章插图

上图将原根删除后
public class Head<E extends Comparable<E>> {
private JAVA.util.ArrayList<E> list=new java.util.ArrayList<>(); public Heap() {
} public Head(E[] objects){
for(int i=0;i<objects.length;i++)
add(objects[i]);
} public void add(E newObject){
list.add(newObject);
int currentIndex=list.size()-1; while (currentIndex>0){
int parentIndex=(currentIndex-1)/2;
if(list.get(currentIndex).compareTo(list.get(parentIndex))>0){
E temp=list.get(currentIndex);
list.set(currentIndex,list.get(parentIndex));
list.set(parentIndex,temp);
}
else
break; currentIndex=parentIndex;
}
} public E remove(){
if(list.size()==0)return null; E removedObject=list.get(0);
list.set(0,list.get(list.size()-1));
list.remove(list.size()-1); int currentIndex=0;
while (currentIndex<list.size()){
int leftChildIndex=2*currentIndex+1;
int rightChildIndex=2*currentIndex+2; if(leftChildIndex>=list.size()) break;//the tree is a heap
int maxIndex=leftChildIndex;
if(rightChildIndex<list.size()){
if(list.get(maxIndex).compareTo(list.get(rightChildIndex))<0){
maxIndex=rightChildIndex;
}
} //swap if the current node is less than the maximum
if(list.get(currentIndex).compareTo(list.get(maxIndex))<0){
E temp=list.get(maxIndex);
list.set(maxIndex,list.get(currentIndex));
list.set(currentIndex,temp);
currentIndex=maxIndex;
}
else
break;
}
return removedObject;
} public int getSize(){
return list.size();
}
} 六．桶排序和基数排序通常基数排序需要耗费O(dn)的时间对带整数键的n个元素排序，其中d是所有键值中基数位数目的最大值。
桶排序是稳定的(stable)，这意味着原始线性表中的两个元素有相同的键值，那么它们在有序线性表中的顺序是不变的。

文章插图

import java.util.LinkedList;
//注意这里只实现了简单的1位处理
public class BucketSort {
public static void bucketSort(int[] list)
{
LinkedList[] bucket=new LinkedList[10];
for(int i=0;i<list.length;i++) {
int key=calKey(list[i]);
if(bucket[key]==null)
bucket[key]=new LinkedList();
System.out.println(list[i]);
bucket[key].add(list[i]);
}
int k=0;
for(int i=0;i<bucket.length;i++) {
if(bucket[i]!=null) {
for(int j=0;j<bucket[i].size();j++) {
list[k++]=(int)bucket[i].get(j);
}
}
}
} private static int calKey(int value)
{
return value%10;
}
}七．外部排序外部排序的I/O复杂度为O(n)，合并步骤的总数为log(n/c)，总数为O(n)*log(n/c)，因此外部排序的复杂度是O(nlogn) 。