排序【七大排序】

文章目录

  • 1. 排序的概念及引用
    • 1.1 排序的概念
    • 1.2 常见的排序算法
  • 2. 常见排序算法的实现
    • 2.1 插入排序
      • 2.1.1基本思想:
      • 2.1.2 直接插入排序
      • 2.1.3 希尔排序( 缩小增量排序 )
    • 2.2 选择排序
      • 2.2.1基本思想:
      • 2.2.2 直接选择排序:
      • 2.2.3 堆排序
    • 2.3 交换排序
      • 2.3.1冒泡排序
      • 2.3.2 快速排序
    • 2.4 归并排序
      • 2.4.1 基本思想
      • 2.4.2 海量数据的排序问题
  • 3. 排序算法复杂度及稳定性分析

1. 排序的概念及引用

1.1 排序的概念

排序:所谓排序,就是使一串记录,按照其中的某个或某些关键字的大小,递增或递减的排列起来的操作。
稳定性:假定在待排序的记录序列中,存在多个具有相同的关键字的记录,若经过排序,这些记录的相对次序保持
不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在排序后的序列中,r[i]仍在r[j]之前,则称这种排序算法是稳定的;否则称为不稳定的。
在这里插入图片描述
内部排序:数据元素全部放在内存中的排序。
外部排序:数据元素太多不能同时放在内存中,根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 常见的排序算法

在这里插入图片描述

2. 常见排序算法的实现

2.1 插入排序

2.1.1基本思想:

直接插入排序是一种简单的插入排序法,其基本思想是:
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中,直到所有的记录插入完为止,得到一个新的有序序列 。实际中我们玩扑克牌时,就用了插入排序的思想。

2.1.2 直接插入排序

当插入第i(i>=1)个元素时,前面的array[0],array[1],…,array[i-1]已经排好序,此时用array[i]的排序码与array[i-1],array[i-2],…的排序码顺序进行比较,找到插入位置即将array[i]插入,原来位置上的元素顺序后移

代码实现

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;}}

直接插入排序的特性总结

  1. 元素集合越接近有序,直接插入排序算法的时间效率越高
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1),它是一种稳定的排序算法
  4. 稳定性:稳定

2.1.3 希尔排序( 缩小增量排序 )

希尔排序法又称缩小增量法。希尔排序法的基本思想是:先选定一个整数,把待排序文件中所有记录分成多个组,所有距离为的记录分在同一组内,并对每一组内的记录进行排序。然后,取,重复上述分组和排序的工作。当到达=1时,所有记录在统一组内排好序。
在这里插入图片描述
代码实现

 public static void hillSort(int[] array){int gap = array.length;while(gap > 1){gap/=2;hill(array,gap);}}public static void hill(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;}}

希尔排序的特性总结

  1. 希尔排序是对直接插入排序的优化。
  2. 当gap > 1时都是预排序,目的是让数组更接近于有序。当gap == 1时,数组已经接近有序的了,这样就会很快。这样整体而言,可以达到优化的效果。我们实现后可以进行性能测试的对比。
  3. 希尔排序的时间复杂度不好计算,因为gap的取值方法很多,导致很难去计算,因此在好些树中给出的希尔排序的时间复杂度都不固定
  4. 稳定性:不稳定

2.2 选择排序

2.2.1基本思想:

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元
素排完 。

2.2.2 直接选择排序:

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素
若它不是这组元素中的最后一个(第一个)元素,则将它与这组元素中的最后一个(第一个)元素交换
在剩余的array[i]–array[n-2](array[i+1]–array[n-1])集合中,重复上述步骤,直到集合剩余1个元素

代码实现
代码一:

public static void selectSort(int[] array){for (int i = 0; i < array.length; i++) {int min = i;for (int j = i+1; j < array.length; j++) {if(array[j] < array[min]){min = j;}}swap(array,min,i);}}public static void swap(int[] array,int i,int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}

代码二:

public static void selectSort1(int[] array){int left = 0;int right = array.length-1;while(left < right){int max = left;int min = left;for (int j = left+1; j <= right; j++) {if(array[j] < array[min]){min = j;}if(array[j] > array[max]){max = j;}}swap(array,min,left);if(left == max){max = min;}swap(array,max,right);left++;right--;}}public static void swap(int[] array,int i,int j){int tmp = array[i];array[i] = array[j];array[j] = tmp;}

【直接选择排序的特性总结】

  1. 直接选择排序思考非常好理解,但是效率不是很好。实际中很少使用
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

2.2.3 堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。
在这里插入图片描述
代码实现:

public static void heapSort(int[] array){int end = array.length-1;createHeap(array);while(end > 0){swap(array,0,end);siftDown(array,0,end);end--;}}
public static void createHeap(int[] array){for (int i = (array.length-1-1)/2; i >= 0; i--) {siftDown(array,i,array.length);}}private static void siftDown(int[] array, int parent, int length) {int child = parent*2 + 1;while(child < length){if(child+1 < length && array[child] < array[child+1]){child++;}if(array[child] > array[parent]){swap(array,child,parent);parent = child;child = child*2 +1;}else{break;}}}

【堆排序的特性总结】

  1. 堆排序使用堆来选数,效率就高了很多。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(1)
  4. 稳定性:不稳定

2.3 交换排序

基本思想:所谓交换,就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置,交换排序的特
点是:将键值较大的记录向序列的尾部移动,键值较小的记录向序列的前部移动。

2.3.1冒泡排序

代码实现:

public static void bubbleSort(int[] array){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;}}if(!flg){break;}}}

【冒泡排序的特性总结】

  1. 冒泡排序是一种非常容易理解的排序
  2. 时间复杂度:O(N^2)
  3. 空间复杂度:O(1)
  4. 稳定性:稳定

2.3.2 快速排序

快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素作为基准值,按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。

代码实现:

public static void quickSort(int[] array){quick(array,0,array.length-1);}public static void quick(int[] array,int start,int end){if(start >= end){return;}int mid= midIndex(array,start,end);swap(array,mid,start);int quickIndex = quickationHole(array,start,end);quick(array,start,quickIndex-1);quick(array,quickIndex+1,end);}public static int quickation(int[] array,int left ,int right){int tmp = left;while(left < right){while(left < right && array[right] >= array[tmp]){right--;}while(left< right && array[left] <= array[tmp]){left++;}swap(array,left, right);}swap(array,left,tmp);return left;}public static int quickationHole(int[] array,int left,int right){int tmp = array[left];while(left < right){while(left < right && array[right] >= tmp){right--;}array[left] = array[right];while(left < right && array[left] <= tmp){left++;}array[right] = array[left];}array[left] = tmp;return right;}public static int midIndex(int[] array,int start,int end){int mid = (start + end)>>>2;if(array[start] < array[end]){if(array[mid] > array[start]){return start;}else if (array[end] < array[mid]){return end;}else {return mid;}}else{if(array[mid] > array[start]){return end;}else if (array[end] < array[mid]){return start;}else {return mid;}}}

非递归实现:

public static void quickSortNor(int[] array){int start = 0;int end = array.length-1;Stack<Integer> stack = new Stack<>();int quickIndex = quickationHole(array,start,end);if(start+1 < quickIndex){stack.push(start);stack.push(quickIndex-1);}if(quickIndex+1 < end){stack.push(quickIndex+1);stack.push(end);}while(!stack.empty()){end = stack.pop();start = stack.pop();quickIndex = quickationHole(array,start,end);if(start+1 < quickIndex){stack.push(start);stack.push(quickIndex-1);}if(quickIndex+1 < end){stack.push(quickIndex+1);stack.push(end);}}}public static int quickationHole(int[] array,int left,int right){int tmp = array[left];while(left < right){while(left < right && array[right] >= tmp){right--;}array[left] = array[right];while(left < right && array[left] <= tmp){left++;}array[right] = array[left];}array[left] = tmp;return right;}

【快速排序总结】

  1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序

  2. 时间复杂度:O(N*logN)
    在这里插入图片描述

  3. 空间复杂度:O(logN)

  4. 稳定性:不稳定

2.4 归并排序

2.4.1 基本思想

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法,该算法是采用分治法(Divide andConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为二路归并。 归并排序核心步骤
在这里插入图片描述
代码实现:

public static void mergeSort(int[] array){mergeSortFun(array,0,array.length-1);}private static void mergeSortFun(int[] array, int left, int right) {if(left >= right){return;}int mid = (left + right)/2;mergeSortFun(array,left,mid);mergeSortFun(array,mid+1,right);merge(array,left,mid,right);}private static void merge(int[] array,int left,int mid,int right){int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;int[] tmparr = new int[right-left+1];int k =0;while(s1 <= e1 && s2 <= e2){if(array[s1] <= array[s2]){tmparr[k++] = array[s1++];}else{tmparr[k++] = array[s2++];}}while(s1 <= e1){tmparr[k++] = array[s1++];}while (s2 <= e2){tmparr[k++] = array[s2++];}for (int i = 0; i < tmparr.length; i++) {array[left+i] = tmparr[i];}}

非递归先实现:

public static void mergeSortNor(int[] array){int gap = 1;while(gap < array.length){for(int i = 0;i < array.length;i= i+gap*2){int left = i;int mid = left + gap -1;int right = mid + gap;if(mid >= array.length){mid = array.length-1;}if (right >= array.length) {right = array.length-1;}merge(array,left,mid,right);}gap*=2;}}private static void merge(int[] array,int left,int mid,int right){int s1 = left;int e1 = mid;int s2 = mid+1;int e2 = right;int[] tmparr = new int[right-left+1];int k =0;while(s1 <= e1 && s2 <= e2){if(array[s1] <= array[s2]){tmparr[k++] = array[s1++];}else{tmparr[k++] = array[s2++];}}while(s1 <= e1){tmparr[k++] = array[s1++];}while (s2 <= e2){tmparr[k++] = array[s2++];}for (int i = 0; i < tmparr.length; i++) {array[left+i] = tmparr[i];}}

【归并排序总结】

  1. 归并的缺点在于需要O(N)的空间复杂度,归并排序的思考更多的是解决在磁盘中的外排序问题。
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(N)
  4. 稳定性:稳定

2.4.2 海量数据的排序问题

外部排序:排序过程需要在磁盘等外部存储进行的排序
前提:内存只有 1G,需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下,所以需要外部排序,而归并排序是最常用的外部排序

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

3. 排序算法复杂度及稳定性分析

在这里插入图片描述
在这里插入图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/161228.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

uniapp小程序中给web-view页面添加授权弹窗(使用cover-view组件覆盖实现该功能)

效果图&#xff1a; web-view是承载网页的容器。会自动铺满整个小程序页面&#xff0c;个人类型的小程序暂不支持使用。 再看下面一个提示&#xff1a; 每个页面只能有一个 web-view&#xff0c;web-view 会自动铺满整个页面&#xff0c;并覆盖其他组件。 也就是说&#xff0c;…

云安全—云计算基础

0x00 前言 学习云安全&#xff0c;那么必然要对云计算相关的内容进行学习和了解&#xff0c;所以云安全会分为两个部分来进行&#xff0c;首先是云计算先关的内容。 0x01 云计算 广泛传播 云计算最早大范围传播是2006年&#xff0c;8月&#xff0c;在圣何塞【1】举办的SES&a…

七大排序 (9000字详解直接插入排序,希尔排序,选择排序,堆排序,冒泡排序,快速排序,归并排序)

一&#xff1a;排序的概念及引入 1.1 排序的概念 1.1 排序的概念 排序&#xff1a;所谓排序&#xff0c;就是使一串记录&#xff0c;按照其中的某个或某些关键字的大小&#xff0c;递增或递减的排列起来的操作。 稳定性&#xff1a;假定在待排序的记录序列中&#xff0c;存在…

DITA-OT 4.0新特性 - PDF themes,定制PDF样式的新方法

随着DITA-OT 4.0的发布&#xff0c;它提供了一种新的定制PDF样式方法&#xff0c;这种方法就是PDF theme。这篇文章来聊一聊这种定制PDF输出的新方法和实验结果。 在进入PDF theme细节之前&#xff0c;为各位读者梳理一下DITA-OT将DITA和Markdown发布成PDF的几种方法。 - 1 …

element ui 下拉框 选择月份和天数

一、背景 目前做的管理系统项目&#xff0c;期望实现功能为&#xff1a;设置出账周期和出账日&#xff0c;考虑使用element ui下拉框实现功能 二、所用技术 vue2element ui 三、实现效果 四、具体代码 <template><popup-frame :title"批量设置出账日" …

OJ第四篇

文章目录 链表分割环形链表有效的括号 链表分割 链接: 链表分割 虽然这个题牛客网中只有C,但是无所谓&#xff0c;我们只要知道C是兼容C的就可以了 至于说这个题的思路&#xff0c;我们就弄两个链表&#xff0c;把小于x的结点放到一个链表中&#xff0c;剩下的放到另一个链表…

2023年10月工作经验及问题整理总结

目录 1.window自带的base64加密解密 2.ElementUI修改鼠标移动到表格的背景色 3.vscode保存时几万个eslint错误 4.Git 拉取Gitee仓库报错&#xff1a;“fatal: unable to access ": Failed to connect to 127.0.0.1 port 1080: Connection r... 4.1本地查看Git是否使用…

Java版本spring cloud + spring boot企业电子招投标系统源代码

项目说明 随着公司的快速发展&#xff0c;企业人员和经营规模不断壮大&#xff0c;公司对内部招采管理的提升提出了更高的要求。在企业里建立一个公平、公开、公正的采购环境&#xff0c;最大限度控制采购成本至关重要。符合国家电子招投标法律法规及相关规范&#xff0c;以及审…

spark stream入门案例:netcat准实时处理wordCount(scala 编程)

目录 案例需求 代码 结果 解析 案例需求&#xff1a; 使用netcat工具向9999端口不断的发送数据&#xff0c;通过SparkStreaming读取端口数据并统计不同单词出现的次数 -- 1. Spark从socket中获取数据&#xff1a;一行一行的获取 -- 2. Driver程序执行时&#xff0c…

加固数据安全:Java助力保护Excel文件,让数据无懈可击

摘要&#xff1a;本文由葡萄城技术团队于CSDN原创并首发。转载请注明出处&#xff1a;葡萄城官网&#xff0c;葡萄城为开发者提供专业的开发工具、解决方案和服务&#xff0c;赋能开发者。 前言 Excel文件保护是常用的一种功能&#xff0c;文件保护主要有三种&#xff1a; 添…

单目3D自动标注

这里介绍两种 1. 基于SAM的点云标注 Seal&#xff1a;是一个多功能的自监督学习框架&#xff0c;能够通过利用视觉基础模型的现成知识和2D-3D的时空约束分割自动驾驶数据集点云 Scalability&#xff1a;可拓展性强&#xff0c;视觉基础模型蒸馏到点云中&#xff0c;避免2D和…

SaaS人力资源管理系统的Bug

SaaS人力资源管理系统的Bug Bug1【18】 这里我是直接把代码复制过来的&#xff0c;然后就有一个空白 这是因为它的代码有问题&#xff0c;原本的代码如下所示 <el-table-column fixed type"index" label"序号" width"50"></el-table…

Linux性能优化--性能追踪:受CPU限制的应用程序(GIMP)

10.0 概述 本章包含了一个例子&#xff1a;如何用Linux性能工具在受CPU限制的应用程序中寻找并修复性能问题。 阅读本章后&#xff0c;你将能够&#xff1a; 在受CPU限制的应用程序中明确所有的CPU被哪些源代码行使用。用1trace和oprofile弄清楚应用程序调用各种内部与外部函…

KNN-近邻算法 及 模型的选择与调优(facebook签到地点预测)

什么是K-近邻算法&#xff08;K Nearest Neighbors&#xff09; 1、K-近邻算法(KNN) 1.1 定义 如果一个样本在特征空间中的k个最相似(即特征空间中最邻近)的样本中的大多数属于某一个类别&#xff0c;则该样本也属于这个类别。 来源&#xff1a;KNN算法最早是由Cover和Hart提…

【JVM面试】从JDK7 到 JDK8, JVM为啥用元空间替换永久代?

系列文章目录 【JVM系列】第一章 运行时数据区 【面试】第二章 从JDK7 到 JDK8, JVM为啥用元空间替换永久代&#xff1f; 大家好&#xff0c;我是青花。拥有多项发明专利&#xff08;都是关于商品、广告等推荐产品&#xff09;。对广告、Web全栈以及Java生态微服务拥有自己独到…

VSS、VDD、VBAT、VSSA

引言 在学习设计TM32时&#xff0c;发现芯片除了GPIO引脚外还会引出许多引脚&#xff0c;以STM32F407ZGT6为例除了GPIO引脚还会有以下引脚 如VSS、VDD、VBAT、VSSA、NRST、VREF、VDDA、VCAP_1、VCAP_2、PDR_ON这些引脚。他们有何作用&#xff0c;电路设计中应如何连接&#x…

迅为RK3588开发板使用RKNN-Toolkit-lite2运行测试程序

1 首先也需要部署运行环境&#xff0c;将库文件放入 RK3588 开发板上&#xff0c;我们将网盘资料“iTOP-3588 开发 板 \02_ 【 iTOP-RK3588 开 发 板 】 开 发 资 料 \12_NPU 使 用 配 套 资 料 \05_Linux_librknn_api\librknn_api\aarch64”路径下的文件通过U盘拷贝到开发板的…

LLM-RAG-WEB 大模型+文件+可视化界面

注意&#xff1a;这里只是简单实现了功能和界面&#xff0c;文件对话也暂时只支持一个文件&#xff0c;如果跳到模型对话再切换回文件对话会文件会删除重置会话&#xff0c;但模型对话切换回来时保留之前会话的。 1、代码&#xff08;使用步骤说明在链接里&#xff09; 参考下…

SQLite4Unity3d安卓 在手机上创建sqlite失败解决

总结 要在Unity上运行一次出现库&#xff0c;再打包进APK内 问题 使用示例代码的创建库 var dbPath string.Format("Assets/StreamingAssets/{0}", DatabaseName); #else// check if file exists in Application.persistentDataPathvar filepath string.Format…

Wireshark新手小白基础使用方法

一、针对IP抓取 1、过滤格式&#xff1a; &#xff08;1&#xff09;、ip.src eq x.x.x.x &#xff08;2&#xff09;、ip.dst eq x.x.x.x &#xff08;3&#xff09;ip.src eq x.x.x.x or ip.dst eq x.x.x.x 二、针对端口过滤 1、过滤格式&#xff1a; &#xff08;1&a…