​​选择排序

堆排序

活动地址：CSDN21天学习挑战赛

目录

1.选择排序

1.1 定义 

1.2 说明

1.3 代码实现

1.4 复杂度 

1.5 优缺点

2. 堆排序 

2.1 定义

2.2 说明

 2.3 代码示例

2.4 复杂度

2.5 优缺点

---

1.选择排序

1.1 定义 

选择排序是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

1.2 说明

首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

1.3 代码实现

1）初始状态：无序区为R[0..n-1]（共n个元素），有序区为空。

2）第1趟排序

设置一个变量 i，让 i 从 0 至 n-2 循环的同时，在对比数组中元素 i 跟元素 i+1 的大小，如果R[i+1]比 R[i] 小，则用一个变量 k 来记住他的位置（即k=i+1）。等到循环结束的时候，我们应该找到了R中最小的那个数的位置了。然后进行判断，如果这个最小元素的不是R的第一个元素，就让第一个元素跟他交换一下值，使R[0..0]和R[1..n-1]分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

。。。。。。

3）第 i 趟排序

第 i 趟排序开始时，当前有序区和无序区分别为R[0..i-1]和R[i..n-1]。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，使R[0..i]和R分别变为记录个数增加 1个的新有序区和记录个数减少 1 个的新无序区。

public static void selectSort(int[] array) {
	for (int i = 0; i < array.length; i++) {
		int minIndex = i;
		for (int j = i+1; j < array.length; j++) {
			//找出比minIndex 小的值
			if (array[j] < array[minIndex]) {
				minIndex = j;
			}
		}
		//当前值与最小值交换
		int tmp = array[i];
		array[i] = array[minIndex];
		array[minIndex] = tmp;
	}
}

1.4 复杂度 

时间复杂度：O(n^2)
空间复杂度：O(1)

选择排序的交换操作介于 0 和 (n - 1)次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。

1.5 优缺点

优点：一轮比较只需交换一次

缺点：效率慢，不稳定

2. 堆排序 

2.1 定义

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。

2.2 说明

堆排序分为两种方法：

1）大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；

2）小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；

 堆排序的基本思想：

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了

 2.3 代码示例

 
public static void heapSort(int[] array) {
	//1.建堆
	createHeap(array);
	while (end > 0) {
		swap(array,0,end);
		shifDowm(array,0,end);
		end--;
    }
}
 
public static void createHeap(int[] array){
	for (int parent = (array.length-1-1) / 2; parent >= 0; parent--) {
		//向下调整为大根堆
		shifDowm(array, parent, array.length);
	}
}
 
 
public static void shifDowm(int[] array, int parent, int len) {
	int child = 2*parent + 1;
	while(child < len) {
		if (child+1 < len && array[child] < array[child+1]) {
			child++;
		}
		//此时 child 下标，就是左右孩子最大值的下标
		if (array[child] > array[parent]) {
			swap(array,child,parent);
			parent = child;
			child = 2*parent+1;
		}else {
			break;
		}
	}
}
 
public static void swap(int[] array, int i, int j) {
	int tmp = array[i];
	array[i] = array[j];
	array[j] = tmp;
}

2.4 复杂度

 时间复杂度：O(N * log N)
     
 空间复杂度：O(1)

2.5 优缺点

优点：堆排序的时间复杂度不是O(n2)，因为堆采用了额外的空间，来降低了时间复杂度。

缺点：不稳定。

堆的维护问题，实际场景中的数据是频繁发生变动的，而对于待排序序列的每次更新（增，删，改），我们都要重新做一遍堆的维护，以保证其特性，这在大多数情况下都是没有必要的。.