必威体育Betway必威体育官网
当前位置:首页 > IT技术

选择排序(简单选择排序和堆排序)

时间:2019-07-29 16:11:03来源:IT技术作者:seo实验室小编阅读:65次「手机版」
 

堆排序

选择排序的基本思想是:每一趟(例如第i趟)在后面的 n-i+1 个待排序元素中选取关键字最小的元素,作为有序子序列的第i个元素,直到第 n-1 趟做完,待排序元素只剩下一个,就不用再选了。这里主要讲简单选择排序和堆排序(重点,面试中问到过)

一、简单选择排序

基本思想:假设排序表为 L[1....n] ,第i趟排序即从L[i,,,,n]  中选择关键字最小的元素与 L(i) 交换,每一趟排序可以确定一个元素的最终位置,这样经过 n-1 趟排序就可以使整个排序表有序。

public class SelectSort {

	public void selectSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int min = i; // 记录最小元素位置
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < arr[min]) {
					min = j; // 更换最小元素位置
				}
			}

			if (min != i) {
				swap(arr, i, min); // 与第i个位置进行交换
			}
		}
	}

	private void swap(int[] arr, int i, int min) {
		int temp = arr[i];
		arr[i] = arr[min];
		arr[min] = temp;
	}

	@Test
	public void test() {
		int[] arr = new int[] { 1, 10, 3, 8, 6, 7, 9 };
		selectSort(arr);
		System.out.println(Arrays.toString(arr));
	}
}

空间效率为O(1)

元素移动次数很少,当表有序时移动次数为0,但比较的次数与表的次序无关,所以时间复杂度始终为O(n2)

不稳定的算法

二、堆排序

堆排序是一种树形选择排序方法,他的特点是:在排序过程中,将 L[1....n] 看成是一颗完全二叉树的顺序存储结构,利用完全二叉树中双亲结点和孩子结点之间的内在关系,在当前无序区中选择关键字最大(最小)的元素。

堆的定义:n 个关键字序列 L[1...n] 称为堆,当且仅当该序列满足:

1、 L( i ) <= L( 2i ) 且  L( i ) <= L( 2i  + 1)  或者  2、 L( i ) >= L( 2i ) 且  L( i ) >= L( 2i  + 1)     其中 1 <= i <= n/2

满足第一种情况的堆称为小根堆(小顶堆) ,满足第二种情况的堆称为大根堆(大顶堆) 。显然,在大根堆中,最大元素存放在根节点中,且对任一非根结点,他的值小于或者等于双亲结点的值。小根堆的定义刚好相反,根结点是最小元素。堆经常被用来实现优先级队列。

                          大根堆示意图

堆排序的关键是构造初始堆,对初始序列建堆,就是一个反复筛选的过程。n 个结点的完全二叉树,最后一个结点是第 n/2 个结点的孩子。对第 n/2 个结点为根的子树进行筛选(对于大根堆:若根结点的关键字小于左右子女结点中关键字较大者,则交换),使该子树成为堆。之后向前依次对各结点为根的子树进行筛选,看该结点值是否大于其左右子节点的值,若不是,将左右子节点中较大值与之交换,交换之后可能会破坏下一级的堆,于是继续采用上述方法构造下一级的堆,直到以该节点为根的子树构成堆为止。反复利用上述调整堆的方法建堆,直到根节点。

                                             自下往上逐步调整为大根堆

建立大根堆的算法 ,

	public void buildMaxHeap(int[] arr, int len) {
		// n个结点完全二叉树,最后一个节点是第n/2个节点的孩子
		int mid = len; 
		for (int i = mid-1; i >= 0 ; i--) {
			adjustDown(arr, i, len);
		}
	}
	
	public void adjustDown(int[] arr, int k, int length) {
		int temp = arr[k];
		for (int i = 2*k+1; i <= length; i=i*2+1) {
			if(i<length-1 && arr[i] < arr[i+1]) {
				i++;
			}
			if(temp >= arr[i]) {
				break;
			}else {
				arr[k] = arr[i];
				k = i;
			}
		}
		arr[k] = temp;
	}
	

向下调整的时间与树的高度有关,为O( h ), 在元素个数为 n 的序列上建堆,其时间的复杂度为 O( n ),说明可以在线性时间内,将一个无序数组建成一个大顶堆。

排序算法

public class HeapSort {

	public void buildMaxHeap(int[] arr, int len) {
		// n个结点完全二叉树,最后一个节点是第n/2个节点的孩子
		int mid = len; 
		for (int i = mid-1; i >= 0 ; i--) {
			adjustDown(arr, i, len);
		}
	}
	
	public void adjustDown(int[] arr, int k, int length) {
		int temp = arr[k];
		for (int i = 2*k+1; i <= length; i=i*2+1) {
			if(i<length-1 && arr[i] < arr[i+1]) {
				i++;
			}
			if(temp >= arr[i]) {
				break;
			}else {
				arr[k] = arr[i];
				k = i;
			}
		}
		arr[k] = temp;
	}
	
	@Test
	public void test() {
		int[] arr = new int[]{53, 17, 78, 9, 45, 65, 87, 32};
		buildMaxHeap(arr, arr.length);
		System.out.println(Arrays.toString(arr));
		for (int i = arr.length-1; i > 0; i--) {
			swap(arr, i);
//			System.out.println(Arrays.toString(arr));
			adjustDown(arr, 0, i-1);                                                                                                                                                                                                                                                                                 
		}
		System.out.println(Arrays.toString(arr));
	}

	private void swap(int[] arr, int i) {
		int temp = arr[i];
		arr[i] = arr[0];
		arr[0] = temp;
	}
}

* 空间复杂度:O(1)

* 时间复杂度:O(nlog2n)

* 不稳定的

相关阅读

排序算法之堆排序(Heap Sort)——C语言实现

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。 算法分析 在学习堆排序之前我们要先

选择排序--简单选择排序与直接选择排序的区别

直接选择排序:思路(按升序):第一轮要在位置0找到最小的元素,所以0要与(0+1)~length-1挨个比;第二轮要在位置1找到第二小的元素,所以1要与(1+

分享到:

栏目导航

推荐阅读

热门阅读