7.堆排序算法
看起来堆排序还是挺简单的,每次通过最大堆排序得到根(就是这个数组的最大值),然后置换到数组的最后位置,再将其中的堆实现方法中的元素个数heap-size[A]减1,在进行最大堆实现,重复以上步骤直到全部置换完成。
看起来还是相当好看的!!!(哎,盗图可耻,哈哈)
算法伪代码:
HEAPSORT(A)
1. BUILD-MAX-HEAP(A)
2. for i <-length[A] to downto 2
3. do exchange A[l] <-A[i] //其中A[l]为本次最大堆实现后的根
4. heap-size[A]<- heap-size[A] - 1
5. MAX-HEAPIFY(A,1) //参考前面的堆实现算法
C++:
main.cpp
#include <iostream>
#include<algorithm>
#include<iterator>
#include<functional>
#include<vector>
using namespace std;
int main(){
int a[]={5,1,9,4,6,2,0,3,8,7};
string b[]={"ChongQing","ShangHai","AoMen","TianJin","BeiJing","XiangGang"};
vector<string> vb=vector<string>(b,b+6);
make_heap(a,a+10,less<int>());//构造成堆结构(less实现升序)
sort_heap(a,a+10,less<int>());//利用STL中的堆排序函数
copy(a,a+10,ostream_iterator<int>(cout," "));
cout<<endl;
}
JAVA:
Sort.java
public class Sort{
static public void heapSort(List<Comparable> a,Comparator comp) {
int i,heapSize=a.size();
LinearList.buildHeap(a, comp);
for(i=heapSize-1;i>0;i--) {
Collections.swap(a, 0, i);//每次都是放到数值的倒数后面位置
heapSize--;
LinearList.heapify(a, 0, heapSize, comp);
}
}
}
Test.java
package test;
import java.util.*;
public class Test{
public static void main(String[] args){
Integer a[]= {5,1,9,4,6,2,0,3,8,7},i;
String b[]= {"ChongQing","ShangHai","ShangHai","AoMen","TianJin","BeiJing","XiangGang"};
Double c[]= {8.5,6.3,1.7,9.2,0.5,2.3,4.1,7.4,5.9,3.7};
ArrayList<Integer> A=new ArrayList<Integer>();
for(i=0;i<10;i++)
A.add(a[i]);
Vector<String> B=new Vector<String>();
for(i=0;i<6;i++)
B.add(new String(b[i]));
LinkedList<Double> C=new LinkedList<Double>();
for(i=0;i<10;i++)
C.add(c[i]);
Sort.heapSort((List)A,new Greater());//Greater表示大的值提取到父节点
System.out.println(A);
Sort.heapSort((List)B,new Less());//Greater表示大的值提取到父节点
System.out.println(B);
Sort.heapSort((List)C,new Greater());//Greater表示大的值提取到父节点
System.out.println(C);
}
}