当前位置: 首页 > news >正文

【Java笔记】七大排序

目录

    • 1. 直接插入排序
    • 2. 希尔排序
    • 3. 选择排序
    • 4. 堆排序(重要)
    • 5. 冒泡排序
    • 6. 快速排序(重要)
      • 6.1 Hoare 法
        • 6.1.1 Hoare 法优化
      • 6.2 挖坑法(重点)
      • 6.3 快速排序的非递归写法
    • 7. 归并排序
      • 海量数据的排序问题
    • 8. 总结

1. 直接插入排序

时间复杂度: 最坏情况:O(n 2 ) 最坏情况:O(n)
空间复杂度: O(1)
稳定性: 稳定

如果一个排序本身就是稳定的排序那么他可以被实现为不稳定的排序
但是如果一个排序本身就是不稳定的排序那么他就不可能被实现为稳定的排序
当数据趋于有序使用直接插入排序最快

代码:

	// 1. 直接插入排序public static void insertSort(int[] array) {for (int i = 1; i < array.length; i++) {int tmp = array[i];int j = i - 1;for (; j >= 0; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}

过程演示:
在这里插入图片描述

2. 希尔排序

时间复杂度: O(n 1.3 ) ~ O(n 1.5 )
空间复杂度: O(1)
稳定性: 不稳定

	// 2. 希尔排序public static void shellSort(int[] array) {int gap = array.length;while (gap > 0) {gap /= 2;shell(array, gap);}}private static void shell(int[] array, int gap) {for (int i = gap; i < array.length; i++) {int tmp = array[i];int j = i - gap;for (; j >= 0 ; j -= gap) {if (array[j] > tmp) {array[j + gap] = array[j];} else {break;}}array[j + gap] = tmp;}}

演示:
在这里插入图片描述

3. 选择排序

时间复杂度: O(n 2 )
空间复杂度: O(1)
稳定性: 不稳定

方式一:

	// 3. 选择排序public static void selectSort(int[] 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;}}swap(array, i, minIndex);}}private static void swap(int[] array, int i, int minIndex) {int tmp = array[i];array[i] = array[minIndex];array[minIndex] = tmp;}

过程演示:
在这里插入图片描述
方式二:
时间复杂度: O(n 2 )

	// 方式二public static void selectSort2(int[] array) {int left = 0;int right = array.length - 1;while (left < right) {int minIndex = left;int maxIndex = left;for (int i = left + 1; i <= right; i++) {if (array[i] < array[minIndex]) {minIndex = i;}if (array[i] > array[maxIndex]) {maxIndex = i;}}swap(array, left, minIndex);// 第一个数据是最大值if (left == maxIndex) {maxIndex = minIndex;}swap(array, right, maxIndex);left++;right--;}}

过程演示:
在这里插入图片描述

4. 堆排序(重要)

时间复杂度: O(N*logN )
空间复杂度: O(1)
稳定性: 不稳定

	// 4. 堆排序public static void heapSort(int[] array) {// 创建大根堆creatHeap(array);int end = array.length - 1;while (end > 0) {// 交换swap(array, 0, end);// 向下调整siftDown(array, 0, end);end--;}}private static void creatHeap(int[] array) {for (int parent = (array.length - 1 - 1) / 2; parent >= 0; parent--) {// 向下调整siftDown(array, parent, array.length);}}private static void siftDown(int[] array, int parent, int len) {int child = 2 * parent + 1;while (child < len) {// 找到左右孩子的最大值if (child + 1 < len && array[child] < array[child + 1]){child++;}if (array[child] > array[parent]) {swap(array, child, parent);parent = child;child = 2 * parent + 1;} else {break;}}}

5. 冒泡排序

时间复杂度: O(n 2 ) 下面代码最好情况是:O(n)
空间复杂度: O(1)
稳定性: 稳定

	// 5. 冒泡排序public static void bubbleSort(int[] array) {// i 代表的是趟数for (int i = 0; i < array.length - 1; i++) {// 优化boolean flg = false;for (int j = 0; j < array.length - 1 - i; j++) {if (array[j] > array[j + 1]) {swap(array, j, j + 1);flg = true;}}// 如果flg == false,说明没有进入if语句,表示数组已经有序了,无需再排序,直接break即可if (!flg) {break;}}}

6. 快速排序(重要)

6.1 Hoare 法

时间复杂度: 最坏情况是单分支的树(1,2,3,4,5)O(n 2 ) ,但是一般不会这么用;最好情况是:O(n*logn)
空间复杂度: 最坏情况:单分支的树O(n);最好情况O(logn)
稳定性: 不稳定

	// 6. 快速排序// hoare 版public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int left, int right) {if (left >= right) {return;}// 划分int par = partition(array, left, right);quick(array, left, par - 1);quick(array, par + 1, right);}private static int partition(int[] array, int start, int end) {int i = start; // 保存start初始位置int pivot = array[start];while (start < end) {// 如果数组是1,2,3,4,5加start < end是为了防止越界while (start < end && array[end] >= pivot) {end--;}// 如果数组是5,4,3,2,1加start < end是为了防止越界while (start < end && array[start] <= pivot) {start++;}swap(array, start, end);}// start == endswap(array, i, start);return start;}

过程演示:
在这里插入图片描述

6.1.1 Hoare 法优化

三数取中法:找到三个数,分别是start、end、mid下标对应的值,找到三个数的中位数作为划分基准

	// hoare 法优化// 三数取中法找到划分基准public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int left, int right) {if (left >= right) {return;}// 优化二// 当节点数小于某一个阈值,没有必要进行递归,直接使用插入排序效率更高,因为所有排序都是越排越有序的!if (right - left + 1 < 7) {insertSort1(array, left, right);return;}// 优化一int index = midThreeNum(array, left, right);swap(array, left, index);// 划分int par = partition(array, left, right);quick(array, left, par - 1);quick(array, par + 1, right);}// 找到三个数,分别是start、end、mid下标对应的值,找到三个数的中位数作为划分基准private static int midThreeNum(int[] array, int start, int end) {int mid = (start + end) / 2;// 3 < 5  start == 3  end == 5   x == midif (array[start] < array[end]) {if (array[mid] < array[start]) {// x < 3 < 5return start;} else if (array[mid] > array[end]) {// 3 < 5 < xreturn end;} else {// 3 < x < 5return mid;}} else {// 5 > 3  start == 5  end == 3  x == midif (array[mid] > array[start]) {// x > 5 > 3return start;} else if (array[mid] < array[end]) {// 5 > 3 > xreturn end;} else {// 5 > x > 3return mid;}}}// 直接插入排序public static void insertSort1(int[] array, int start, int end) {for (int i = start + 1; i <= end; i++) {int tmp = array[i];int j = i - 1;for (; j >= start; j--) {if (array[j] > tmp) {array[j + 1] = array[j];} else {break;}}array[j + 1] = tmp;}}private static int partition(int[] array, int start, int end) {int i = start;int pivot = array[start];while (start < end) {while (start < end && array[end] >= pivot) {end--;}while (start < end && array[start] <= pivot) {start++;}swap(array, start, end);}// start == endswap(array, i, start);return start;}

6.2 挖坑法(重点)

	// 挖坑法public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int left, int right) {if (left >= right) {return;}// 划分int par = partition(array, left, right);quick(array, left, par - 1);quick(array, par + 1, right);}private static int partition(int[] array, int start, int end) {int pivot = array[start];while (start < end) {while (start < end && array[end] >= pivot) {end--;}array[start] = array[end];while (start < end && array[start] <= pivot) {start++;}array[end] = array[start];}array[start] = pivot;return start;}

过程演示:
在这里插入图片描述

6.3 快速排序的非递归写法

	// 快速排序的非递归写法public static void quicksort2(int[] array) {int left = 0;int right = array.length - 1;// 找到一个基准值int par = partition(array, left, right);Stack<Integer> stack = new Stack<>();// 判断一下par左边是否只有一个元素了,如果只有一个元素则没必要继续排序了,否则将入栈if (par > left + 1) {stack.push(left);stack.push(par - 1);}if (par < right - 1) {stack.push(par + 1);stack.push(right);}while (!stack.isEmpty()) {right = stack.pop();left = stack.pop();par = partition(array, left, right);if (par > left + 1) {stack.push(left);stack.push(par - 1);}if (par < right - 1) {stack.push(par + 1);stack.push(right);}} }

过程演示:
在这里插入图片描述

7. 归并排序

时间复杂度: O(n*logn)
空间复杂度: O(n)
稳定性: 稳定

	// 7. 归并排序public static void mergeSort(int[] array) {mergeSortFunc(array, 0, array.length - 1);}private static void mergeSortFunc(int[] array, int left, int right) {if (left == right) {return;}int mid = (left + right) / 2;// 分解mergeSortFunc(array, left, mid);mergeSortFunc(array, mid + 1, right);// 合并merge(array, left, right, mid);}private static void merge(int[] array, int left, int right, int mid) {int start1 = left;int end1 = mid;int start2 = mid + 1;int end2 = right;int[] tmpArr = new int[right - left + 1];int k = 0;// 此时2个数组都只收有一个数据while (start1 <= end1 && start2 <= end2) {if (array[start1] <= array[start2]) {tmpArr[k++] = array[start1++];} else {tmpArr[k++] = array[start2++];}}// 一个数组被遍历完while (start1 <= end1) {tmpArr[k++] = array[start1++];}while (start2 <= end2) {tmpArr[k++] = array[start2++];}// 保证tmpArr当中的元素是有序的for (int i = 0; i < tmpArr.length; i++) {array[i + left] = tmpArr[i];}}

过程演示:
在这里插入图片描述

海量数据的排序问题

外部排序:排序过程需要在磁盘等外部存储进行的排序

在内存只有 1G,需要排序的数据有 100G 的情况下

因为内存中因为无法把所有数据全部放下,所以需要外部排序,而归并排序是最常用的外部排序

  1. 先把文件切分成 200 份,每个 512 M
  2. 分别对 512 M 排序,因为内存已经可以放的下,所以任意排序方式都可以
  3. 进行 2路归并,同时对 200 份有序文件做归并过程,最终结果就有序了

8. 总结

排序方法平均时间复杂度空间复杂度稳定性
直接插入排序O(n2)O(1)稳定
希尔排序O(n 1.3 ) ~ O(n 1.5 )O(1)不稳定
选择排序O(n2)O(1)不稳定
堆排序O(nlogn)O(1)不稳定
冒泡排序O(n2)O(1)稳定
快速排序最坏O(n2),最好O(nlogn)单分支的树O(n),最好情况O(logn)不稳定
归并排序O(nlogn)O(n)稳定
http://www.lryc.cn/news/588184.html

相关文章:

  • Android Studio C++/JNI/Kotlin 示例 二
  • 清除 Android 手机 SIM 卡数据的4 种简单方法
  • 如何将数据从一部手机传输到另一部手机?
  • SSH 登录失败,封禁IP脚本
  • Oracle 学习笔记
  • 【橘子分布式】Thrift RPC(理论篇)
  • LINUX714 自动挂载/nfs;物理卷
  • 基于STM32的智能抽水灌溉系统设计(蓝牙版)
  • 前端开发中的常见问题及解决方案
  • 数据结构——优先队列(priority_queue)的巧妙运用
  • 渗透第一次总结
  • 【Python办公】Python如何批量提取PDF中的表格
  • 前端基础之《Vue(22)—安装MongoDB》
  • 【Java EE初阶 --- 网络原理】初识网络
  • 第十七节:第五部分:网络通信:TCP通信-支持与多个客户端同时通信
  • 如何使用Cisco DevNet提供的免费ACI学习实验室(Learning Labs)?(Grok3 回答)
  • 笔试——Day6
  • CISSP知识点汇总- 通信与网络安全
  • 内部文件审计:企业文件服务器审计对网络安全提升有哪些帮助?
  • 密码学中立方攻击的另类应用
  • 安全初级(一)
  • 多租户云环境下的隔离性保障:虚拟化、容器、安全组如何协同防护?
  • git 访问 github
  • 【深度学习框架终极PK】TensorFlow/PyTorch/MindSpore深度解析!选对框架效率翻倍
  • 智能Agent场景实战指南 Day 12:医疗咨询Agent设计模式
  • vue3+arcgisAPI4示例:自定义多个气泡窗口展示(附源码下载)
  • C#中发布订阅的阻塞非阻塞
  • Spring Boot + Vue2 实现腾讯云 COS 文件上传:从零搭建分片上传系统
  • QT——信号与槽
  • Zabbix在MySQL性能监控方面的运用