文章目录

• • 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. 堆排序适合待排序列元素较多的情况