排序
分析排序算法的3大指标有哪些，对应适用场景？
- 执行效率
- 时间复杂度
- 比较和交换的次数
- 内存消耗--空间复杂度
- 原地排序：空间复杂度是 O(1) 的排序算法。
- 稳定性
- 稳定性：待排序数组中值相同的元素再排序后相对前后顺序保持不变。 -- 适用场景根据多个元素进行排序的场景，如：按照金额从小到大对订单数据排序。对于金额相同的订单，我们希望按照下单时间从早到晚有序，如何快速实现？
方案：先按照时间进行排序，然后按照金额再次进行排序。
时间复杂度为O(
) -- 适合小规模数据的排序
冒泡排序
思路
数组中相邻元素两两比较，如果前面 > 后面元素则进行替换。
实现
插入排序
思路
将数组分为已排序区间和未排序区间，每次将未排序区间首位插入已排序区间相应位置。
实现
选择排序
思路
将数组分为已排序区间和未排序区间，每次将未排序区间中的最小元素插入到已排序区间的尾部。
实现
时间复杂度为O(
) -- 适合大规模数据的排序
前置知识点--递归
写递归代码的关键就是找到如何将大问题分解为小问题的规律，并且基于此写出递推公式，然后再推敲终止条件，最后将递推公式和终止条件翻译成代码
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？
注意：给定 n 是一个正整数。
示例 1：
输入： 2
输出： 2
解释： 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2：
输入： 3
输出： 3
解释： 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
- 2 阶 + 1 阶
class Solution { //递推公式 f(n) = f(n-1)+f(n-2); // 终止条件 f(1) = 1;f(2) = 2; private Map<Integer,Integer> recursionMap = new HashMap<Integer,Integer>(); public int climbStairs(int n) { if(n == 1){ return 1; } if(n == 2){ return 2; } if(recursionMap.containsKey(n)){ return recursionMap.get(n); } int sum = climbStairs(n-1) + climbStairs(n-2); recursionMap.put(n,sum); return sum; } }
归并排序
思路
将数组分为前后两部分分别排序，然后将排序完成数组合并即可。
递推公式
merge_sort(p…r) = merge(merge_sort(p…q), merge_sort(q+1…r))
实现
快速排序
思路
随机选取一个元素为分区点，小于分区点的元素放到分区点左侧，将大于分区点元素放到分区点右侧，分区点在中间
递推公式
quick_sort(left,right) = quick_sort(left,pivot-1) + quick_sort(pivot+1,right);
实现
class Solution {
/**
* quickSort
* 快速排序 -- 分治思想
* 思想：将数组分为三部分，小于分区点的区间，分区点和大于分区点的区间，然后将数据依次与分区点的进行比较，如果数据 < 分区点则移动到分区点的左边，反则移动到分区点的右边。
* 依次递归上述操作即可
*
* 递归公式：quick_sort(left,right) = quick_sort(left,pivot-1) + quick_sort(pivot+1,right);
* 递归终止条件：left >= right
*
* @param array
*/
private static void quickSort(int[] array, int left, int right) {
if(left >= right){
return;
}
// 分区点下标
int privotIndex = partition(array,left,right);
quickSort(array,left,privotIndex-1);
quickSort(array,privotIndex+1,right);
}
/**
* 获取分区点函数
* 整理数据，最终数据整理为 array[left]<= array[privotIndex] <= array[right]
* 思路：参考选择排序，将数组分为已排序区间和未排序区间，每次取未排序区间的第一个元素与分区点比较，如果 < 分区点元素则将其添加到已处理区间的尾部。
* @param array
* @param left
* @param right
* @return 暂定返回right节点
*/
public static int partition(int[] array, int left, int right) {
//分区点下标
int privot = array[right];
//已处理区间尾部下标
int j = left;
for (int i = left; i < right; i++) {// i:未排序区间第一个元素
if(array[i] < privot){
int temp = array[i];
array[i] = array[j];
array[j] = temp;
j++;
}
}
int temp = array[j];
array[j] = array[right];
array[right] = temp;
return j;
}
}
时间复杂度为O(
) -- 线性排序
桶排序
思路
核心思想是将要排序的数据分到几个有序的桶里，每个桶里的数据再单独进行排序。桶内排完序之后，再把每个桶里的数据按照顺序依次取出，组成的序列就是有序的了。
限制条件
- 要排序的数据需要很容易就能划分成 m 个桶，并且，桶与桶之间有着天然的大小顺序。这样每个桶内的数据都排序完之后，桶与桶之间的数据不需要再进行排序。
- 数据在各个桶之间的分布是比较均匀的
适用场景
桶排序比较适合用在外部排序中--外部排序就是数据存储在外部磁盘中，数据量比较大，内存有限，无法将数据全部加载到内存中 -- 磁盘日志按照时间排序
实现
基数排序
思路
计数排序其实是桶排序的一种特殊情况。当要排序的 n 个数据，所处的范围并不大的时候，比如最大值是 k，我们就可以把数据划分成 k 个桶。每个桶内的数据值都是相同的，省掉了桶内排序的时间。
限制条件
- k 远小于 n
- 非负数排序
适用场景
计数排序只能用在数据范围不大的场景中，如果数据范围 k 比要排序的数据 n 大很多，就不适合用计数排序了。而且，计数排序只能给非负整数排序，如果要排序的数据是其他类型的，要将其在不改变相对大小的情况下，转化为非负整数。-- 考生分数查询
实现
计数排序
思路
限制条件
- 基数排序对要排序的数据是有要求的，需要可以分割出独立的“位”来比较，而且位之间有递进的关系，如果 a 数据的高位比 b 数据大，那剩下的低位就不用比较了。除此之外，每一位的数据范围不能太大，要可以用线性排序算法来排序，否则，基数排序的时间复杂度就无法做到 O(n) 了。
适用场景
手机号排序
实现
总结
排序算法总结
线性排序算法的时间复杂度比较低，适用场景比较特殊。所以如果要写一个通用的排序函数，不能选择线性排序算法。如果对小规模数据进行排序，可以选择时间复杂度是 O(n2) 的算法；如果对大规模数据进行排序，时间复杂度是 O(nlogn) 的算法更加高效。所以，为了兼顾任意规模数据的排序，一般都会首选时间复杂度是 O(nlogn) 的排序算法来实现排序函数。
网友评论