4、希尔排序(缩小增量法) 属于插入类排序,由Shell提出,希尔排序对直接插入排序进行了简单的改进:它通过加大插入排序中元素之间的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项大跨度地移动,当这些数据项排过一趟序之后,希尔排序算法减小数据项的间隔再进行排序,依次进行下去,进行这些排序时的数据项之间的间隔被称为增量,习惯上用字母h来表示这个增量。
常用的h序列由Knuth提出,该序列从1开始,通过如下公式产生:
h = 3 * h +1
反过来程序需要反向计算h序列,应该使用
h=(h-1)/3
public static void shellSort(int[] arr) // 计算出最大的h值
{
int h=1;
while(h<=arr.length/3)
h=h*3+1;
while(h>0)
{
for(int i=h;i<arr.length;i+=h)
{
if(arr[i]<arr[i-h])
{
int tmp=arr[i];
int j=i-h;
while(j>=0&&arr[j]>tmp)
{
arr[j+h]=arr[j];
j-=h;
}
arr[j+h]=tmp;
}
}
h=(h-1)/3; // 计算出下一个h值
}
}
复制代码
作者: syw02014 时间: 2014-2-26 17:01
5、堆排序:堆积排序(Heapsort)是指利用堆积树(堆)这种资料结构所设计的一种排序算法,可以利用数组的特点快速定位指定索引的元素。堆排序是不稳定的排序方法,辅助空间为O(1), 最坏时间复杂度为O(nlog2n) ,堆排序的堆序的平均性能较接近于最坏性能。 堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征,使得在当前无序区中选取最大(或最小)关键字的记录变得简单。
用大根堆排序的基本思想
① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区
② 再将关键字最大的记录R[1](即堆顶)和无序区的最后一个记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key
③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,由此得到新的无序区R[1..n-2]和有序区R[n-1..n],且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。直到无序区只有一个元素为止。
大根堆排序算法的基本操作:
① 初始化操作:将R[1..n]构造为初始堆;
② 每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换,然后将新的无序区调整为堆(亦称重建堆)。
注意:
①只需做n-1趟排序,选出较大的n-1个关键字即可以使得文件递增有序。
②用小根堆排序与利用大根堆类似,只不过其排序结果是递减有序的。堆排序和直接选择排序相反:在任何时刻堆排序中无序区总是在有序区之前,且有序区是在原向量的尾部由后往前逐步扩大至整个向量为止。
public static void heapSort(int[] arr)
{
for(int i=0;i<arr.length;i++)
{
createMaxdHeap(arr,arr.length-i-1);
swap(arr, 0, arr.length-i-1);
for(int i = 0; i < arr.length; i++)
System.out.print(arr[i] + "\t");
}
}
public static void createMaxdHeap(int[] arr, int lastIndex)
{
for(int i=(lastIndex-1)/2;i>=0;i--)
{
int k=i;// 保存当前正在判断的节点
while (2*k+1<=lastIndex) // 若当前节点的子节点存在
{
int biggerIndex=2*k+1; // biggerIndex总是记录较大节点的值,先赋值为当前判断节点的左子节点