1T数据快速排序！十种经典排序算法总结( 四 )
private static final int THRESHOLD = 47;public int[] quickSort(int[] array) {if (array == null || array.length < 2) {return array;}return quickSort(array, 0, array.length - 1);}private int[] quickSort(int[] array, int start, int end) {// 如果当前需要排序的数据量小于等于THRESHOLD则走插入排序的逻辑 ， 否则继续走快速排序if (end - start <= THRESHOLD - 1) {return insertSort(array);}// left和right指针分别指向array的第一个和最后一个元素int left = start, right = end;/*取最左边、最右边和最中间的三个元素的中间值作为基准数据 ， 以此来尽量避免每次都取第一个值作为基准数据、时间复杂度可能退化为O(n^2)的情况出现*/int middleOf3Indexs = middleOf3Indexs(array, start, end);if (middleOf3Indexs != start) {swap(array, middleOf3Indexs, start);}// temp存放的是array中需要比较的基准数据int temp = array[start];while (left < right) {// 首先从right指针开始比较 ， 如果right指针位置处数据大于temp ， 则将right指针左移while (left < right}// 如果找到一个right指针位置处数据小于temp ， 则将right指针处数据赋给left指针处if (left < right) {array[left] = array[right];left++;}// 然后从left指针开始比较 ， 如果left指针位置处数据小于temp ， 则将left指针右移while (left < right}// 如果找到一个left指针位置处数据大于temp ， 则将left指针处数据赋给right指针处if (left < right) {array[right] = array[left];right--;}}// 当left和right指针相等时 ， 此时循环跳出 ， 将之前存放的基准数据赋给当前两个指针共同指向的数据处array[left] = temp;// 一次替换后 ， 递归交换基准数据左边的数据if (start < left - 1) {array = quickSort(array, start, left - 1);}// 之后递归交换基准数据右边的数据if (right + 1 < end) {array = quickSort(array, right + 1, end);}return array;}private int middleOf3Indexs(int[] array, int start, int end) {int mid = start + ((end - start) >>> 1);if (array[start] < array[mid]) {if (array[mid] < array[end]) {return mid;} else {return array[start] < array[end] ? end : start;}} else {if (array[mid] > array[end]) {return mid;} else {return array[start] < array[end] ? start : end;}}}private void swap(int[] array, int i, int j) {array[i] = array[i] ^ array[j];array[j] = array[i] ^ array[j];array[i] = array[i] ^ array[j];}8 计数排序以上的七种排序算法都是比较排序 ， 也就是基于元素之间的比较来进行排序的 。 而下面将要介绍的三种排序算法是非比较排序 ， 首先是计数排序 。
计数排序会创建一个临时的数组 ， 里面存放每个数出现的次数 。 比如一个待排序的数组是[3, 3, 5, 2, 7, 4, 2] ， 那么这个临时数组中记录的数据就是[2, 2, 1, 1, 0, 1] 。 表示2出现了两次、3出现了两次、4出现了一次、5出现了一次、6出现了零次、7出现了一次 。 那么最后只需要遍历这个临时数组中的计数值就可以了 。
public int[] countingSort(int[] array) {if (array == null || array.length < 2) {return array;}//记录待排序数组中的最大值int max = array[0];//记录待排序数组中的最小值int min = array[0];for (int i : array) {if (i > max) {max = i;}if (i < min) {min = i;}}int[] temp = new int[max - min + 1];//记录每个数出现的次数for (int i : array) {temp[i - min]++;}int index = 0;for (int i = 0; i < temp.length; i++) {//当输出一个数之后 ， 当前位置的计数就减一 ， 直到减到0为止while (temp[i]-- > 0) {array[index++] = i + min;}}return array;}
推荐阅读
- 西部数据在CES 2021推出多款4TB容量的旗舰级SSD
- WhatsApp收集用户数据新政惹众怒，“删除WhatsApp”在土耳其上热搜
- “千店同开”引质量担忧，小米回应
- 未来想进入AI领域，该学习Python还是Java大数据开发
- 企业|技术快速迭代倒逼知识产权“贴身”服务，上海首家AI商标品牌指导站入驻徐汇西岸
- 黑客窃取250万个人数据 意大利运营商提醒用户尽快更换SIM卡
- 阳狮报告：4成受访者认为自己的数据比免费服务更有价值
- 中消协点名大数据网络杀熟 反对利用消费者个人数据画像
- 学习大数据是否需要学习JavaEE
- 意大利运营商Ho Mobile被曝数据泄露