牛客网常见算法思路 (二)排序_牛客项目经历怎么排序

有用麻烦点个赞哦

经典排序算法

空间复杂度
O(1)
冒泡、选择、插入、希尔、堆
O(logN)~O(N)
快速
O(N)
归并
O(M)
计数、基数

1、选择实现的排序算法1

要求：已知一个几乎有序的数组，=> 如果把数组排好序，每个元素的移动距离不超过该K，且k相对于数组长度来说很小，请问什么排序比较好。
首先看O(n)
基数排序、基数排序,不基于比较的排序算法限制，不适用所有情况，不考虑。
看O(n²)
冒泡，排序，与数组原始序列无关
插入排序（可以做到很好的程度）
看O(nlogn)
快速排序 与数组原始顺序无关，随机选择数进行数组划分
归并排序 与数组原始无关

答案：改进后的堆排序
因为移动的值小于K，所以最小值必定在a[0]-a[k-1]里，以a[0]-a[k-1]建立小根堆，弹出堆顶，放在a[0]上;以a[1]-a[k]建立小根堆，弹出堆顶为第二小的值，放在a[1]如此类推

2、选择实现的排序算法2

要求：判断数组中是否有重复值，必须保证额外空间的复杂度为O(1)
若无空间复杂度限制，用hash表实现
hash的空间复杂度为O(n),空间复杂度为O(n)

思路：先排序，再判断，如果有相等的值会放在一起，考察在限制空间复杂度时如何实现最快的排序
堆排序看似不错但是大部分基于递归实现的，递归时空间复杂度O(logN)

答案：非递归版本的堆排序。

3、

要求：把两个有序数组合并为一个数组，第一个数组空间正好可以容纳两个数组元素

思路：从后往前进行比较，数组一二的末端比较(此时指的是数组一有数的末尾，实际上末尾为数组一有数部分+数组二)，更大的数放实际末尾，且读取的指针向前一位再进行比较，如此类推
关键：从后往前读，从前往后读会覆盖数组一的有用部分

4、

要求：荷兰国旗问题，只包含0.1.2的整数数组进行排序，要求使用交换、原地排序，而不是利用计数进行排序

思路：过程与快排的划分过程类似
时间复杂度O(N)，额外空间复杂度O(1)
左边设置0区域 右边设置2区域，从左到右读，根据读到的数与0区后一位或者2区前一位进行，同时扩大相应区域，再读取下一位（和2区前一位交换的要读当前数字而不是下一位数字）

5、

要求：排好序的矩阵找数，有返回true，无返回false
0 1 2 5
2 3 4 7
4 4 4 8
5 7 7 9
思路，从左到有增加，从上到下增加。从右上角的5开始，比需要的数小则向左移动，比需要的数大则向下移动。

6、

要求：需要排序的最短子数组长度
[1,5,4,3,2,6,7] 返回4 因为只有[5,4 3 2]要排序

思路：最优解时间复杂度O(n),额外空间复杂度O(1)
先从左到右读最大数，记录最后一次 读到的数小于记录的最大数时的位置（上表数组是2，当时最大值是5，2在数组的位置是[4]）
再从右往左读最小数，记录最后一次 读到的数大于记录的最小数时的位置（上表数组是5，当时最小值是2，5数组的位置是[1]）
所1-4有4个数，所以返回4

7、

给定一个整形数组arr，返回如果排序之后，相邻两数的最大差值，如排序后为
1 2 3 4 7 8 9
最大差值来自于4和7，返回3

思路：最优解时间复杂额外空间复杂均为O(N),思想来自桶排序
先遍历数组，找到最小值1最大值9，共7个数，分为7个等量区间，最大值单独分在一个桶中（共8个桶）

此时1号桶会有最小值，n+1号桶会有最大值，中间必然有空桶，只需要考虑空桶两边的数，每个桶的最小值-上一个桶的非空最大值，记录最大差值即可。

有用麻烦点个赞哦