Java教程

[选择排序] 简单选择排序、堆排序

本文主要是介绍[选择排序] 简单选择排序、堆排序,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

文章目录

    • 1. 简单选择排序
    • 2. 堆排序(以大根堆为例)

1. 简单选择排序

  算法思想:假设有n个元素,每一趟选择就是在后面的(n-i+1)个元素中选择最小的元素作为有序子序列的第i个元素,直到第(n-1)趟选择做完。
注:简单选择排序中元素之间的比较次数,与待排序列的初始状态无关。
  相关代码如下:

	void Select_sort(int[] array) {
		for (int i = 0; i < array.length; i++) {
			int min = i; // 用min记录最小元素值的位置
			for (int j = i + 1; j < array.length; j++) {
				if (array[j] < array[min]) {
					min = j; // 更新最小元素值的位置
				}
			}
			if (min != i) {
				Swap(array, i, min); // 更新第i个位置元素的值
			}
		}
	}
	/*
	 * 简单选择排序
	 * 时间复杂度:O(n^2)
	 * 空间复杂度:O(1) 
	 * 稳定性:不稳定
	 */

2. 堆排序(以大根堆为例)

  算法思想:首先把存放在数组中的元素构建成初始大根堆输出堆顶元素后,把堆底元素送入堆顶。此时根节点不满足大根堆的性质,堆被破坏,所以要将堆顶元素做向下调整算法,使其继续保持大根堆的性质,再输出堆顶元素。如此重复,直到堆中只剩下一个元素为止。
  基本步骤可以分为以下几部分:构建初始大根堆;向下调整算法;堆排序。
  相关代码如下:

    // 创建大根堆:从最后一个非叶子结点开始,依次向根节点,做向下调整
	void Create_heap(int[] array) {
		for (int i = ((array.length - 1) - 1) / 2; i >= 0; i--) {
			AdjustDown(array, i, array.length);
		}
	}

	// 向下调整算法:从某一根节点开始,把较大值的元素换到父结点
	void AdjustDown(int[] array, int root, int len) {
		int parent = root;
		int child = 2 * parent + 1; // 左孩子的下标为2*parent+1
		// 保证有左孩子
		while (child < len) {
			// 在有右孩子的情况下,如果右孩子的值大于左孩子的值,就把child++
			if (child + 1 < len && array[child] < array[child + 1]) {
				child++;
			}
			// 如果当前孩子的值大于父结点的值,就交换
			if (array[parent] < array[child]) {
				int tmp = array[parent];
				array[parent] = array[child];
				array[child] = tmp;
				// 更新父节点和孩子结点的下标
				parent = child;
				child = 2 * parent + 1;
			} else {
				break;
			}
		}
	}

	// 堆排序:先创建大根堆
	// 然后让最后一个数与第一个数交换,此时最后一个数为最大值元素,然后进行向下调整
	// 再重复上述步骤,直到只剩下一个元素
	void Heap_sort(int[] array) {
		Create_heap(array);
		int end = array.length - 1; // 最后一个待排序列元素的下标
		while (end > 0) {
			// 交换首尾两个元素,即,输出堆顶元素
			int tmp = array[end];
			array[end] = array[0];
			array[0] = tmp;
			AdjustDown(array, 0, end--);
		}
	}

注:1. 升序–>构建大根堆;降序–>构建小根堆
  2. 堆中调整的时间与树的高度有关
  3. 堆支持插入操作,先将新的结点放在堆的末端,再对新的结点做向上调整算法
  4. 向堆中插入或删除一个元素时,时间复杂度都为O(logn)
  5. 堆排序适合待排序列元素较多的情况

这篇关于[选择排序] 简单选择排序、堆排序的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!