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

选择排序与堆排序

 博主主页: 码农派大星.

    数据结构专栏:Java数据结构

 数据库专栏:MySQL数据库

关注博主带你了解更多数据结构知识


1.选择排序

第一种方法:直接定义一个 i下标 j下标(j=i+1) ,再定义minIdex下标 让 minIdex == i, 开始遍历数组,过程中 如果j下标的值大于minIdex下标的值就交换,然后i++,j++.

 private static void swap(int[] arrary,int i,int j){int tmp = arrary[i];arrary[i] = arrary[j];arrary[j] = tmp;}public static void selectSort1(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,minIndex,i);}
return arrary;}

第二种方法:

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

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

选择排序效果图

 private static void swap(int[] arrary,int i,int j){int tmp = arrary[i];arrary[i] = arrary[j];arrary[j] = tmp;}public static void selectSort2(int[] array){int left = 0;int right = array.length -1;while (left < right){int mindIndex = left;int maxIndex = left;for (int i = left+1; i <= right; i++) {if (array[i] < array[mindIndex]) {mindIndex = i;}if (array[i] > array[maxIndex]) {maxIndex = i;}}swap(array,mindIndex,left);if (maxIndex == left) {maxIndex = mindIndex;}swap(array,maxIndex,right);left++;right--;}
return arrary;}

总结:

1. 直接选择排序思考非常好理解,但是效率不是很好。

2. 时间复杂度:O(n^{2})

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

4. 稳定性:不稳定

2.堆排序

堆排序(Heapsort)是指利用堆积树(堆)这种数据结构所设计的一种排序算法,它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆,排降序建小堆。

 private static void createBigHeap(int[] array) {for (int parent = (array.length-1-1) / 2; parent >= 0; parent--) {siftDown(parent,array,array.length);}}private static void siftDown(int parent,int[] array,int end) {int child = 2*parent+1;while (child < end) {if(child + 1 < end && array[child] < array[child+1]) {child++;}//child下标 就是左右孩子最大值的下标if(array[child] > array[parent]) {swap(array,child,parent);parent = child;child = 2*parent+1;}else {break;}}}public static void heapSort(int[] array) {createBigHeap(array);int end = array.length-1;while (end >= 0) {swap(array,0,end);siftDown(0,array,end);end--;}}

总结:

1. 堆排序使用堆来选数,效率就高了很多。

2. 时间复杂度:O(N*logN)

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

4. 稳定性:不稳定

相关文章:

  • Rust开源Web框架Salvo源码编译
  • Vue中引入组件需要哪三步
  • PostgreSQL的扩展(extensions)-常用的扩展之pg_store_plans
  • Windows系统使用Docker部署Focalboard团队协作工具详细流程
  • 521源码-免费下载-WordPress全能自动采集与发布插件 – WP-AutoPostPro 汉化版
  • Docker搭建mysql性能测试环境
  • 授人以渔 选购篇十四:电动车(电动自行车)选购要点
  • 重生之while在鸣潮学习HTML标签
  • 【ai】pycharm设置软件仓库编译运行基于langchain的chatpdf
  • 疯狂“造人”!美国两党共推新法案,5年培养100万AI及量子人才
  • 推荐3款好用的AI智能写作工具
  • 【算法专题】双指针算法之 移动零
  • Qt for android 串口库使用
  • 国产32位MCU的发展与机遇
  • 【数组】Leetcode 57. 插入区间【中等】
  • JavaScript 如何正确处理 Unicode 编码问题!
  • Android系统模拟器绘制实现概述
  • Essential Studio for ASP.NET Web Forms 2017 v2,新增自定义树形网格工具栏
  • ES学习笔记(12)--Symbol
  • GitUp, 你不可错过的秀外慧中的git工具
  • JavaScript 事件——“事件类型”中“HTML5事件”的注意要点
  • Mybatis初体验
  • PaddlePaddle-GitHub的正确打开姿势
  • SpiderData 2019年2月23日 DApp数据排行榜
  • Zepto.js源码学习之二
  • 阿里云爬虫风险管理产品商业化,为云端流量保驾护航
  • 阿里云应用高可用服务公测发布
  • 创建一种深思熟虑的文化
  • 关于Flux,Vuex,Redux的思考
  • 湖南卫视:中国白领因网络偷菜成当代最寂寞的人?
  • 快速构建spring-cloud+sleuth+rabbit+ zipkin+es+kibana+grafana日志跟踪平台
  • 力扣(LeetCode)21
  • 使用阿里云发布分布式网站,开发时候应该注意什么?
  • 手机app有了短信验证码还有没必要有图片验证码?
  • 小程序测试方案初探
  • elasticsearch-head插件安装
  • 不要一棍子打翻所有黑盒模型,其实可以让它们发挥作用 ...
  • ​Python 3 新特性:类型注解
  • #### go map 底层结构 ####
  • (09)Hive——CTE 公共表达式
  • (DFS + 剪枝)【洛谷P1731】 [NOI1999] 生日蛋糕
  • (Forward) Music Player: From UI Proposal to Code
  • (java)关于Thread的挂起和恢复
  • (JSP)EL——优化登录界面,获取对象,获取数据
  • (二十四)Flask之flask-session组件
  • (附源码)ssm跨平台教学系统 毕业设计 280843
  • (论文阅读23/100)Hierarchical Convolutional Features for Visual Tracking
  • (五)IO流之ByteArrayInput/OutputStream
  • (一)使用Mybatis实现在student数据库中插入一个学生信息
  • (转)【Hibernate总结系列】使用举例
  • (转)EXC_BREAKPOINT僵尸错误
  • (转)Oracle 9i 数据库设计指引全集(1)
  • ./include/caffe/util/cudnn.hpp: In function ‘const char* cudnnGetErrorString(cudnnStatus_t)’: ./incl
  • .net 4.0 A potentially dangerous Request.Form value was detected from the client 的解决方案
  • .net Application的目录