七大排序算法之堆排、选择

本文主要是介绍七大排序算法之堆排、选择，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

选择排序

思想：循环一次找到一个最小值（最大值），缩小排序一个长度。

时间复杂度：

平均：O(N^2)

最好：O(N^2)

最坏：O(N^2)

空间复杂度：O(1)

稳定性：不稳定排序

实现代码：

public static void selectSort(int[] arr) {// 每次找出一个最小值for (int i = 0; i < arr.length; ++i) {// [0, i)是有序的// 每循环一次，在[i, length)找出一个最小的置于i位置上for (int j = i; j < arr.length; ++j) {if (arr[j] < arr[i]) {swap(arr, i, j);}}}
}// 优化版：每循环一次找到最大值和最小值
public static void selectSortPerfect(int[] arr) {int n = arr.length;int max, min = 0;for (int i = 0; i < n / 2; ++i) {max = i;min = i;for (int j = i + 1; j < n - i; ++j) {if (arr[j] < arr[min]) {min = j;}if (arr[j] > arr[max]) {max = j;}// 在[0, i)是有序的swap(arr, i, min);// 在(n-i-1, n)是有序的swap(arr, max, n - i - 1);}}
}private static void swap(int[] array, int num1, int num2) {int tmp = array[num1];array[num1] = array[num2];array[num2] = tmp;
}

堆排序

思路：

1、建堆（在原有数组上建堆），从小到大排序建大堆

2、每次选择堆顶元素方法数组最后，堆数量-1，调整堆（向下调整）

时间复杂度：

平均：O(NlgN）

最好：O(NlgN）

最坏：O(NlgN)

空间复杂度：O(1)

稳定性：不稳定排序

代码实现：

public static void heapSort(int[] array) {int size = array.length;if (size <= 1) {return;}// 1、建堆（大堆）createHeap(array, size);// 2、删除堆顶元素，放置数组最后一个for (int i = 0; i < size; ++i) {heapPop(array, size - i);}}private static void createHeap(int[] array, int size) {// 下沉式调整, 需要从后往前遍历,// 从最后一个非叶子节点开始遍历// size - 1表示最后一个元素的下标// 拿着这个下标 - 1 / 2 就得到了当前元素的父节点for (int i = (size - 2) / 2; i >= 0; --i) {adjustDown(array, size, i);}
}// 向下调整
private static void adjustDown(int[] array, int size, int parent) {int leftChild = 2 * parent + 1;// 左子树int rightChild = 2 * parent + 2;int maxChild;if (leftChild >= size) {return;}maxChild = leftChild;if (rightChild < size && array[rightChild] > array[leftChild]) {maxChild = rightChild;// 找出左右孩子的最大值}if (array[parent] > array[maxChild]) {// 满足堆条件return;}swap(array, parent, maxChild);adjustDown(array, size, maxChild);
}private static void heapPop(int[] array, int size) {swap(array, 0, size - 1);adjustDown(array, size - 1, 0);
}private static void swap(int[] array, int num1, int num2) {int tmp = array[num1];array[num1] = array[num2];array[num2] = tmp;
}

 

这篇关于七大排序算法之堆排、选择的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---