1T数据快速排序！十种经典排序算法总结
作 者：雕爷的架构之路
原文链接：
1 冒泡排序每次循环都比较前后两个元素的大小 ， 如果前者大于后者 ， 则将两者进行交换 。 这样做会将每次循环中最大的元素替换到末尾 ， 逐渐形成有序集合 。 将每次循环中的最大元素逐渐由队首转移到队尾的过程形似“冒泡”过程 ， 故因此得名 。
一个优化冒泡排序的方法就是如果在一次循环的过程中没有发生交换 ， 则可以立即退出当前循环 ， 因为此时已经排好序了（也就是时间复杂度最好情况下是
文章插图
的由来） 。
public int[] bubbleSort(int[] array) {if (array == null || array.length < 2) {return array;}for (int i = 0; i < array.length - 1; i++) {boolean flag = false;for (int j = 0; j < array.length - 1 - i; j++) {if (array[j] > array[j + 1]) {//这里交换两个数据并没有使用中间变量 ， 而是使用异或的方式来实现array[j] = array[j] ^ array[j + 1];array[j + 1] = array[j] ^ array[j + 1];array[j] = array[j] ^ array[j + 1];flag = true;}}if (!flag) {break;}}return array;}2 选择排序每次循环都会找出当前循环中最小的元素 ， 然后和此次循环中的队首元素进行交换 。
public int[] selectSort(int[] array) {if (array == null || array.length < 2) {return array;}for (int i = 0; i < array.length; i++) {int minIndex = i;for (int j = i + 1; j < array.length; j++) {if (array[j] < array[minIndex]) {minIndex = j;}}if (minIndex > i) {array[i] = array[i] ^ array[minIndex];array[minIndex] = array[i] ^ array[minIndex];array[i] = array[i] ^ array[minIndex];}}return array;}3 插入排序插入排序的精髓在于每次都会在先前排好序的子集合中插入下一个待排序的元素 ， 每次都会判断待排序元素的上一个元素是否大于待排序元素 ， 如果大于 ， 则将元素右移 ， 然后判断再上一个元素与待排序元素...以此类推 。 直到小于等于比较元素时就是找到了该元素的插入位置 。 这里的等于条件放在哪里很重要 ， 因为它是决定插入排序稳定与否的关键 。
public int[] insertSort(int[] array) {if (array == null || array.length < 2) {return array;}for (int i = 1; i < array.length; i++) {int temp = array[i];int j = i - 1;while (j >= 0j--;}array[j + 1] = temp;}return array;}4 希尔排序希尔排序可以认为是插入排序的改进版本 。 首先按照初始增量来将数组分成多个组 ， 每个组内部使用插入排序 。 然后缩小增量来重新分组 ， 组内再次使用插入排序...重复以上步骤 ， 直到增量变为1的时候 ， 这个时候整个数组就是一个分组 ， 进行最后一次完整的插入排序即可结束 。
在排序开始时的增量较大 ， 分组也会较多 ， 但是每个分组中的数据较少 ， 所以插入排序会很快 。 随着每一轮排序的进行 ， 增量和分组数会逐渐变小 ， 每个分组中的数据会逐渐变多 。 但因为之前已经经过了多轮的分组排序 ， 而此时的数组会趋近于一个有序的状态 ， 所以这个时候的排序也是很快的 。 而对于数据较多且趋向于无序的数据来说 ， 如果只是使用插入排序的话效率就并不高 。 所以总体来说 ， 希尔排序的执行效率是要比插入排序高的 。
希尔排序执行示意图：
文章插图
具体的实现代码如下：
public int[] shellSort(int[] array) {if (array == null || array.length < 2) {return array;}int gap = array.length >>> 1;while (gap > 0) {for (int i = gap; i
推荐阅读
- 西部数据在CES 2021推出多款4TB容量的旗舰级SSD
- WhatsApp收集用户数据新政惹众怒，“删除WhatsApp”在土耳其上热搜
- “千店同开”引质量担忧，小米回应
- 未来想进入AI领域，该学习Python还是Java大数据开发
- 企业|技术快速迭代倒逼知识产权“贴身”服务，上海首家AI商标品牌指导站入驻徐汇西岸
- 黑客窃取250万个人数据 意大利运营商提醒用户尽快更换SIM卡
- 阳狮报告：4成受访者认为自己的数据比免费服务更有价值
- 中消协点名大数据网络杀熟 反对利用消费者个人数据画像
- 学习大数据是否需要学习JavaEE
- 意大利运营商Ho Mobile被曝数据泄露