- 假设数组长度为n,准备n+1个桶
- 遍历该数组,将最小值放入到第1个位置,将最大值放入到最后一个位置
- 将剩下的数等分成等分成n-1份依次放入剩下对应范围的桶中,
- 最后这n+1个桶中至少有一个空桶,说明桶内的数值差不是最大差值,我们去桶间找最大差值
- 对于每个桶,我们都保存了每个桶的最小值和最大值,从第2个桶开始,每次计算当前桶的最小值与前一个桶(要有元素)的最大值的差,过程中我们动态更新最大差值
基本介绍
堆是一个完全二叉树,因此我们可以利用节点的特性去使用一个数组模拟一颗完全二叉树:
i*2+1
, 右子节点的下标为i*2+2
建立堆的时间复杂度:O(log1) + O(log2) + … + O(logN) 近似于 O(N),因此建立堆的时间复杂度为O(N)
堆有大根堆以及小根堆,没有规定堆中左子树的根必须大于(或小于)右子树的根。
堆排序的两个基本步骤:(具体说明看代码注释)
思路:从左向右每次两两比较相邻元素,如果前一个元素大于后一个元素,那么就交换这两个元素,一趟下来肯定有一个元素放到了最后的位置
1 | func BubbleSort(nums []int) []int { |
思路:每次选择一个当前未排序的最小元素放到当前未排序的第一个位置上
1 | func SelectSort(nums []int) []int { |
直接插入排序是简单排序中性能最好的
平均时间复杂度:O(n^n / 4)
最好时间复杂度:O(n)
最坏时间复杂度:O(n^n)
思路:将每次要插入的当前元素依次与左边元素比较,如果左边元素大于当前元素则交换,直到左边元素小于等于当前元素。
1 | package main |
思路:选取数组中的第1个元素作为划分元素,划分为两部分,左边一部分比该元素小,右边一部分比该元素大
1 | package quickSortV1 |
虽然经典快速排序性能相对其他排序性能较高,但仍然有一定的瓶颈,例如如果是一个有序的数组。
此外快速排序可以从以下几点进行改进:
nums[low]
,之后每次在右边找到小的元素就将其赋值给nums[low]
,每次在左边找到大的元素可以直接赋值给nums[high]