首页 > 代码库 > 数据结构精要------直接选择和堆排序算法

数据结构精要------直接选择和堆排序算法

上篇总结中主要实践了算法的内排序的交换排序,那么接下来我们继续实践选择排序的两种:直接选择和堆排序算法。

-----直接选择排序


package com.sort;

/**
 * 直接选择排序算法
 * @author weixing-yang
 *
 * 算法思路:
 *  首先找出最大元素,将其与a[n-1]位置置换。
 *  然后在余下的n-1个元素中寻找最大元素,将其与a[n-2]位置置换。
 *  如此进行下去。知道n个元素排序完毕。

*/ public class SelectSort { public void selectSort(int[] arr, int n){ int i,j,k; int temp = 0; for (i= 0; i < n -1; i++) { for(k = i,j = i+1; j < n; j++){ if(arr[k] > arr[j]) k = j; } if( k != j){ temp = arr[k]; arr[k] = arr[i]; arr[i] = temp; } } } }


-----堆排序

堆排序是树型选择排序的改进,它使用的辅助空间较少,仅须要一个元素用于空间交换。

什么是堆?堆:根结点的关键码值或者大于左右子树或者都小于左右子树,并且左右子树也是堆。假设每一个结点的值都大于左右子树关键码值,称之为大顶堆。

每一个结点的值都小于左右子树的关键码值,称之为小顶堆。

堆是一个全然二叉树

堆排序有两个步骤:(1)初建堆;(2)调整堆

以下代码实践:

package com.sort;

/**
 * 堆排序算法
 * @author weixing-yang
 *
 * 算法思路:
 * 先将初始文件R[0:n-1]建成一个大根堆,此堆为初始的无序区 ; 
 * 再将keyword最大的记录R[0](即堆顶)和无序区的最后一个记录R[n-1]交换。
 * 由此得到新的无序区R[0:n-2]和有序区R[n-1],且满足R[0:n-2].keys≤R[n-1].key 。 
 * 因为交换后新的根R[0]可能违反堆性质。故应将当前无序区R[0:n-2]调整为堆(重建堆)。 
 * 然后再次将R[0:n-2]中keyword最大的记录R[0]和该区间的最后一个记录R[n-2]交换,
 * 由此得到新的无序区R[0:n-3]和有序区R[n-2:n-1]。且仍满足关系R[0..n-3].keys≤R[n-2:n-1].keys,
 * 相同要将R[0:n-3]调整为堆…… 直到无序区仅仅有一个元素R[0]时,R[0:n-1]为有序序列。

*/ public class HeapSort { // 排序函数 public void heapSort(int[] array) { // 对数组进行筛选,建成一个大顶堆 double len = array.length - 1; for (int i = (int) Math.floor(len / 2); i > 0; i--) { heapAdjust(array, i, array.length - 1); } for (int i = array.length - 1; i > 0; i--) { // 将堆顶元素与最后一个元素调换位置,即输出最大值 swap(array, 1, i); // 将最后一位剔出。数组最大下标变为i-1。自队顶至叶子进行调整,形成一个新堆。此过程称为筛选 heapAdjust(array, 1, i - 1); } } // 建堆函数。觉得【s。m】中仅仅有 s // 相应的keyword未满足大顶堆定义,通过调整使【s,m】成为大顶堆 public void heapAdjust(int[] array, int s, int m) { // 用0下标元素作为暂存单元 array[0] = array[s]; // 沿孩子较大的结点向下筛选 for (int j = 2 * s; j <= m; j *= 2) { // 保证j为较大孩子结点的下标,j < m 保证 j+1 <= m ,不越界 if (j < m && array[j] < array[j + 1]) { j++; } if (!(array[0] < array[j])) { break; } // 若S位较小,应将较大孩子上移 array[s] = array[j]; // 较大孩子的值变成S位的较小值,可能引起顶堆的不平衡,故对其所在的堆进行筛选 s = j; } // 若S位较大,则值不变;否则,S位向下移动至2*s、4*s、。。

。 array[s] = array[0]; } // 交换函数 public void swap(int[] array, int i, int j) { int temp; temp = array[i]; array[i] = array[j]; array[j] = temp; } }


-----測试函数

package com.sort;

public class Main {
	
	public static void main(String[] args){
		int[] array = {25, 36, 45,40, 12, 34, 55}; 
		int n = array.length;
		SelectSort select = new SelectSort();
		HeapSort heap = new HeapSort();
		long start = System.currentTimeMillis();
		select.selectSort(array, n);//直接选择排序
		//heap.heapSort(array);
		long end = System.currentTimeMillis();
		long sum = end - start;
		System.out.println("排序花费的总毫秒数:"+sum);
		for (int i = 0; i < array.length; i++) {
			System.out.print(array[i]+" ");
		}
	}
}

-----执行结果

排序花费的总毫秒数:0
12 25 34 36 40 45 55 
直接选择排序的时间复杂度是n2, 高速排序的时间复杂度是nlogn。空间复杂度是O(1)。


@@------->>下篇继续实践插入排序的两种排序算法







数据结构精要------直接选择和堆排序算法