五、复杂度
不稳定，时间复杂度是O(nlogn)~O(n^2)，空间复杂度是O(1)
堆排序（Heap Sort）
一、概念
1.1什么是堆
- 分为大顶堆和小顶堆
- 符合完全二叉树
- 父节点大于（或小于）子节点
- 第一个非叶子节点：n/2-1（向下取整）
二、排序思想
- 首先将待排序的数组构造成一个大根堆，此时，整个数组的最大值就是堆结构的顶端
- 将顶端的数与末尾的数交换，此时，末尾的数为最大值，剩余待排序数组个数为n-1
- 将剩余的n-1个数再构造成大根堆，再将顶端数与n-1位置的数交换，如此反复执行，便能得到有序数组
三、图示过程
最大值和末尾的最小值交换位置
重复以上操作
四、代码
4.1代码
public class HeapSort { public static void heapSort(int[] arr) { // 构建初始大根堆 buildMaxHeap(arr); // 从最后一个非叶子节点开始，依次向上调整堆 for (int i = arr.length - 1; i > 0; i--) { swap(arr, 0, i); // 将堆顶元素（最大值）与最后一个元素交换 maxHeapify(arr, 0, i); // 调整堆 } } private static void buildMaxHeap(int[] arr) { // 从最后一个非叶子节点开始，依次向上调整堆 for (int i = arr.length / 2 - 1; i >= 0; i--) { maxHeapify(arr, i, arr.length); } } private static void maxHeapify(int[] arr, int i, int heapSize) { int left = 2 * i + 1; // 左子节点下标 int right = 2 * i + 2; // 右子节点下标 int largest = i; // 最大值下标 // 找到左、右子节点中的最大值 if (left < heapSize && arr[left] > arr[largest]) { largest = left; } if (right < heapSize && arr[right] > arr[largest]) { largest = right; } // 如果最大值不是当前节点，交换最大值和当前节点，继续向下调整 if (largest != i) { swap(arr, i, largest); maxHeapify(arr, largest, heapSize); } } private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } public static void main(String[] args) { int[] arr = {5, 2, 6, 0, 3, 9, 1, 7, 4, 8}; heapSort(arr); for (int i : arr) { System.out.print(i + " "); } } }
4.2运行结果
排序前的数组为：[5, 2, 6, 0, 3, 9, 1, 7, 4, 8]
排序后的数组为：[0, 1 ,2 ,3 ,4 ,5 ,6 ,7 ,8, 9]
4.3解释
代码中的buildMaxHeap()方法用于构建初始大根堆，maxHeapify()方法用于调整堆，heapSort()方法实现了堆排序算法。main()方法中用一个示例数组进行测试，并输出排序结果
直接选择排序（Selection Sort）
一、概念
- 1.选择排序是一种简单直观的排序算法
2.无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候，数据规模越小越好。 - 3.唯一的好处可能就是不占用额外的内存空间
二、实现思路
- 1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
- 2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
- 3.重复第二步，直到所有元素均排序完毕。
三、图示过程
四、代码
4.1代码
//Selection Sort选择排序 public class Selection { public static void main(String[] args) { int[] arr = {23,34,21,243,67,432,23,34}; System.out.println(Arrays.toString(selection(arr))); } //选择排序 public static int[] selection(int[] arr) { int temp = 0; //定义数据交换时的第三方变量 for (int i = 0; i < arr.length - 1; i++) { int min = i; for (int j = i + 1; j < arr.length; j++) { if (arr[min] > arr[j]) { //如果arr[j]的值小于arr[min] min = j; //保存j的索引 } } temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; System.out.println("第" + (i + 1) + "轮插入" + Arrays.toString(arr)); } return arr; } }
4.2运行结果
排序前的数组为：[23,34,21,243,67,432,23,34]
排序后的数组为：[21,23,23,34,34,67,243,432]
五、代码优化
5.1代码方案一
第一种：使用一个if判断 i == arr.length-2 ，直接去掉最后一轮对比
问题，如果倒数第二轮排序 最后一位元素比倒数第二位元素小，那么去掉最后一轮排序，最终结果是没有排序完成的
//Selection Sort选择排序 public class Selection { public static void main(String[] args) { int[] arr = {23,34,21,243,67,432,23,34}; System.out.println(Arrays.toString(selection(arr))); } //选择排序 public static int[] selection(int[] arr) { int temp = 0; //定义数据交换时的第三方变量 for (int i = 0; i < arr.length - 1; i++) { if( i == arr.length-2){ //如果i=数组的最后两个值 break; //退出循环 } int min = i; for (int j = i + 1; j < arr.length; j++) { if (arr[min] > arr[j]) { //如果arr[j]的值小于arr[min] min = j; //保存j的索引 } } temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; System.out.println("第" + (i + 1) + "轮插入" + Arrays.toString(arr)); } return arr; } }
5.2代码方案二
第二种优化：
if(i != min ) { //判断只有在min=i时才会运行下面的代码
这种优化方法省略了很多不必要的代码运行，并优化最后一轮是否需要对比
//Selection Sort选择排序 public class Selection { public static void main(String[] args) { int[] arr = {23,34,21,243,67,432,23,34}; System.out.println(Arrays.toString(selection(arr))); } //选择排序 public static int[] selection(int[] arr) { int temp = 0; //定义数据交换时的第三方变量 for (int i = 0; i < arr.length - 1; i++) { int min = i; for (int j = i + 1; j < arr.length; j++) { if (arr[min] > arr[j]) { //如果arr[j]的值小于arr[min] min = j; //保存j的索引 } } if(i != min ) { //判断只有在min=i时才会运行下面的代码 temp = arr[i]; arr[i] = arr[min]; arr[min] = temp; System.out.println("第" + (i + 1) + "轮插入" + Arrays.toString(arr)); } } return arr; } }
六、复杂度
是一种不稳定排序，时间复杂度是O(n^2)，空间复杂度是O(1)
结构化：各个排序对比表格
