算法归纳（三）
排序及其汇总
1）、冒泡：O(N^2) 最好：O(N) 空间复杂度：O(1) 稳定
在要排序的一组数中，对当前还未排好序的范围内的全部数，自上而下对相邻的两个数依次进行比较和调整，让较大的数往下沉，较小的往上冒。
最好情况是因为队列有序。
（2）、选择：O(N^2) 空间复杂度：O(1) 不稳定
每趟从待排序的记录序列中选择关键字最小的记录放置到已排序表的最前位置，直到全部排完。
序列5 8 5 2 9， 我们知道第一遍选择第1个元素5会和2交换，那么原序列中2个5的相对前后顺序就被破坏了，所以选择排序不是一个稳定的排序算法。
（3）、直接插入：O(N^2) 最好：O(N) 空间复杂度：O(1) 稳定
每步将一个待排序的记录，按其顺序码大小插入到前面已经排序的子序列的合适位置，直到全部插入排序完为止。
最好情况是因为队列有序。
（4）、归并排序：O(nlogn) 空间复杂度：O(N) 稳定
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。
空间复杂度是因为需要一个辅助数组，可以定义为全局变量。
（5）、快速排序：O(nlogn) 最坏：O(N^2) 空间复杂度：O(logn) 不稳定
先从数列中取出一个数作为基准数，把比基准数大的放到它的右边，小的放到它的左边，再对左右两边重复上述步骤，直到整个序列有序。
经典快排容易出现最坏情况，跟数据状况有关系。
最坏情况是因为队列有序。
改进后的快速排序(荷兰国旗问题)：一次搞定多个数
随机快排：估计的时候不能说有最差情况，成为了一个概率事件，只能以长期期望的方式算出他的时间复杂度O(nlogn)。
随机快排最常用，是因为常数项少，当指标相同拼常数项，mergeSort输给快排就是因为常数项的问题。
空间浪费在划分点，数据需要被划分多少次，断点就需要多少个。最差情况下断点需要O(N)，最好情况下断点需要O(logn)
时间复杂度O(N*logN)，额外空间复杂度O(logN)
（6）、堆排序：O(N*logN) 空间复杂度：O(1)
1）、建堆时间复杂度：建立堆的过程，新加入节点时间复杂度log1+log2+log3+log4+log(n-1)=O(N)
左孩子坐标：2*i+1
右孩子坐标：2*i+2
优先级队列结构，就是堆结构（PriorityQueue）
堆结构的heapInsert与heapify
2）、两种建立堆的方法HeapInsert&Heapify
①第一种方法HeapInsert
它可以假定我们事先不知道有多少个元素，通过不断往堆里面插入元素进行调整来构建堆。
它的大致步骤如下：
首先增加堆的长度，在最末尾的地方加入最新插入的元素。 比较当前元素和它的父结点值，如果比父结点值大，则交换两个元素，否则返回。 重复步骤2.
这种插入建堆的时间复杂度是O(NlogN)
②第二种方法Heapify（重构堆）
从最后一个非叶子节点一直到根结点进行堆化的调整。如果当前节点小于某个自己的孩子节点（大根堆中），那么当前节点和这个孩子交换。Heapify是一种类似下沉的操作，HeapInsert是一种类似上浮的操作。
这种建堆的时间复杂度是O(N)
（7）、其他知识
排序算法的稳定性及其汇总
冒泡、插入、归并稳定。
选择、快速、堆排序不稳定。
稳定性的含义？值相等的情况下，相对次序得到保持。
为什么要稳定性？
由现实的例子决定，例如默认序列是按照身高排序的，再按照年龄排序的时候，希望可以保留原始身高的信息，再进行年龄排序。
有关排序问题的补充：
归并排序的额外空间复杂度可以变成O(1)，但是非常难，不需要掌握，可以搜“归并排序 内部缓存法”
快速排序可以做到稳定性问题，但是非常难，不需要掌握，可以搜“01 stable sort”
有一道题目，是奇数放在数组左边，偶数放在数组右边，还要求原始的相对次序不变，碰到这个问题，可以怼面试官。面试官非良人。
（8）、桶排序（计数排序、基数排序）
是非基于比较的排序，与被排序的样本的实际数据状况很有关系，所以实际中并不经常使用
时间复杂度O(N)，额外空间复杂度O(N)
是一种稳定的排序
public static void bucket(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
int max = arr[0];
for (int i = 1; i < arr.length; i++) {//求出待排数组的最大值
max = Math.max(max, arr[i]);
}
int[] bucket = new int[max + 1];
for (int i = 0; i < arr.length; i++) {//将数字装入对应的桶之中
bucket[arr[i]]++;
}
for (int i = 0, j = 0; j < bucket.length; j++) {
while (bucket[j]-- > 0) {
arr[i++] = j;
}
}
} （8）、给定一个数组，求如果排序之后，相邻两数的最大差值，要求时间复杂度O(N)，且要求不能用非基于比较的排序。
/*
* 准备N+1个桶，遍历数组找到最小最大值
* Min放在第一个桶，max放在最大的桶，然后把最小到最大的这个范围等分为N+1份
* 那么两边放入最大和最小，必然中间会有至少一个空桶。桶内部的差值肯定没有桶范围的大。
* 遍历完成后，计算非空桶直接的差值，用min和max计算，如果是空桶就跳过。
* 设置一个空桶的原因是，用于否定最大差值一定不来自一个桶内部，因为有空桶的存在，
* 那空桶两侧的非空桶差值，肯定大于或者等于任意桶内容最大和最小值的差值。
* */
public static int sortMax(int[] arr) {
if (arr == null || arr.length < 2) {
return 0;
}
int max = arr[0], min = arr[0];
for (int i = 1; i < arr.length; i++) {
max = Math.max(arr[i], max);
min = Math.min(arr[i], min);
}
if (max == min) {
return 0;
}
boolean[] arrFlag = new boolean[arr.length+1];
int[] bucketMax = new int[arr.length+1];
int[] bucketMin = new int[arr.length+1];
for (int i = 0; i < arr.length; i++) {
//获取当前数字应该存入的桶的下标
int index = bucket(arr[i], arr.length, min, max);
bucketMin[index] = arrFlag[index] ? Math.min(bucketMin[index], arr[i]) : arr[i];
bucketMax[index] = arrFlag[index] ? Math.max(bucketMax[index], arr[i]) : arr[i];
arrFlag[index] = true;
}
int res = 0;//要返回的最大差值
int lastMaX = bucketMax[0];//存储上一个桶的最大值
int i = 1;
while (i <= arr.length) {
if (arrFlag[i]) {
res = Math.max(res, bucketMin[i] - lastMaX);
lastMaX = bucketMax[i];
}
i++;
}
return res;
}
public static int bucket(int num, int len, int min, int max) {
return (int) ((num - min) * len / (max - min));
} （9）、工程中的综合排序算法
少于60个数的直接用插入排序。
基础类型用快速排序，因为基础类型相同分数无差异。
自定义类型用归并排序，因为关乎多类数据，需要保持原始排序。
（10）、快速排序与归并排序的比较：
①二者都运用了递归和分治的两种重要思想
②归并排序的思想：总共分为两步，分与治，先使子序列有序，再将子序列合并，需要有一个辅助数组。
快速排序的思想：原地排序，每次选择一个数字作为基准数，一次排序搞定一个或者多个数字（基准数的位置），快速排序因为一些错误使时间的消耗成为平方级。
就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；
最优的情况下空间复杂度为：O(logn) ，每一次都平分数组的情况，需要的空间是树的高度
最差的情况下空间复杂度为：O( n ) ，退化为冒泡排序的情况
③归并排序：O(nlogn) 空间复杂度：O(N) 稳定
快速排序：O(nlogn) 最坏：O(N^2) 空间复杂度：O(logn) 不稳定
阿里巴巴公司福利 301人发布
投递阿里巴巴等公司10个岗位 >
查看12道真题和解析