【排序2】-交换排序

👻交换排序

  • 🎄1、基本思想及特点
  • 🎄2、冒泡排序
  • 🎄3、快速排序(挖坑法)
  • 🎄4、快速排序优化
    • 🎊4.1 三数取中法选key
    • 🎊4.2 递归到小的子区间时,可以考虑使用插入排序
  • 🎄5、 快速排序非递归
  • 🎄6、快速排序总结

🎄1、基本思想及特点

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

🎄2、冒泡排序

冒泡排序(Bubble Sort)是排序算法里面比较简单的一个排序。它重复地走访要排序的数列,一次比较两个数据元素,如果顺序不对则进行交换,并一直重复这样的走访操作,直到没有要交换的数据元素为止。

如图
在这里插入图片描述
🪄代码示例:

public static void bubbleSort(int[] array) {
        //i代表趟数 10 -》 9for (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 == false) {
                return;
            }
        }
    }

✌️【冒泡排序的特性总结】

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

🎄3、快速排序(挖坑法)

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

🔍快速排序的主要思想可以概括为以下步骤:
1、选择基准元素:从待排序的数组中选择一个元素作为基准元素(通常可以选择数组的第一个元素,但最好的选择是三数取中)。
2、分区:将数组中小于基准元素的元素放在基准元素的左边,大于基准元素的元素放在基准元素的右边,形成两个子数组。
3、递归排序:对基准元素左边的子数组和右边的子数组分别进行递归调用快速排序。
4、合并:将左边子数组、基准元素和右边子数组按顺序合并起来,形成排序后的数组。

如图
在这里插入图片描述
在这里插入图片描述
🪄代码示例

public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }
      
        int pivot = partition(array,start,end);

        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
}
private static int partition(int[] array, int left, int right) {
	int i = left;
	int j = right;
	int pivot = array[left];
	while (i < j) {
		while (i < j && array[j] >= pivot) {
		j--;
		} 
		array[i] = array[j];
		while (i < j && array[i] <= pivot) {
		i++;
		} 
		array[j] = array[i];
	} 
	array[i] = pivot;
	return i;
}

🎄4、快速排序优化

🎊4.1 三数取中法选key

private static int middleNum(int[] array,int left,int right) {
        int mid = left+((right-left) >> 1);
        //int mid = (left+right)/2;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }
    }

🎊4.2 递归到小的子区间时,可以考虑使用插入排序

public static void insertSort2(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;
        }
    }

🪄全部代码示例

public static void quickSort(int[] array) {
        quick(array,0,array.length-1);
    }
private static void quick(int[] array,int start,int end) {
        if(start >= end) {
            return;
        }

        if(end-start+1 <= 15) {
            insertSort2(array, start, end);
            return;
        }

        //1. 三数取中  index是中间大的数字 的 下标
        int index = middleNum(array,start,end);
        swap(array,index,start);

        int pivot = partition(array,start,end);//

        quick(array,start,pivot-1);
        quick(array,pivot+1,end);
}
private static int partition(int[] array,int left,int right) {
        int tmp = array[left];
        while (left < right) {
            while (left < right && array[right] >= tmp) {
                right--;
            }
            if(left >= right) {
                break;
            }
            array[left] = array[right];
            while (left < right && array[left] <= tmp) {
                left++;
            }
            if(left >= right) {
                break;
            }
            array[right] = array[left];
        }
        array[left] = tmp;
        return left;
}

 public static void insertSort2(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 middleNum(int[] array,int left,int right) {
        int mid = left+((right-left) >> 1);
        //int mid = (left+right)/2;
        if(array[left] < array[right]) {
            if(array[mid] < array[left]) {
                return left;
            }else if(array[mid] > array[right]) {
                return right;
            }else {
                return mid;
            }
        }else {
            if(array[mid] < array[right]) {
                return right;
            }else if(array[mid] > array[left]) {
                return left;
            }else {
                return mid;
            }
        }
}

🎄5、 快速排序非递归

🪄代码示例

void quickSortNonR(int[] a, int left, int right) {
	Stack<Integer> st = new Stack<>();
	st.push(left);
	st.push(right);
	while (!st.empty()) {
		right = st.pop();
		left = st.pop();
		if(right - left <= 1)
			continue;
		int div = PartSort1(a, left, right);
		// 以基准值为分割点,形成左右两部分:[left, div)[div+1, right)
		st.push(div+1);
		st.push(right);
		st.push(left);
		st.push(div);
	}
}

🎄6、快速排序总结

🔍

  1. 快速排序整体的综合性能和使用场景都是比较好的,所以才敢叫快速排序
  2. 时间复杂度:O(N*logN)
  3. 空间复杂度:O(logN)
  4. 稳定性:不稳定

🎉OK!今天的分享就到这里了,后面还会分享更多排序算法,敬请关注喔!!!✌️
在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

React进阶 - 12(浅谈 state、props与render函数的关系)

本章内容 目录 一、state 与 render 函数的关系二、props 与 render函数的关系 上一节我们讲了如何使用 PropTypes及 DefaultProps来进行属性的类型校验及设置属性默认值。本节内容我们来了解一下 state、props与render函数的关系。 一、state 与 render 函数的关系 我们知道…

THM学习笔记——OSI模型和TCP/IP模型

全是文字 比较枯燥 建议视频 OSI模型由七个层次组成&#xff1a; 第7层 -- 应用层&#xff1a; OSI模型的应用层主要为在计算机上运行的程序提供网络选项。它几乎专门与应用程序一起工作&#xff0c;为它们提供一个界面以用于传输数据。当数据传递到应用层时&#xff0c;它…

大数据Doris(五十九):SQL函数之字符串函数(三)

文章目录 SQL函数之字符串函数(三) 一、​​​​​​​NULL_OR_EMPTY (VARCHAR str)

防御保护---防火墙(安全策略、NAT策略实验)

防御保护---防火墙&#xff08;安全策略、NAT策略实验&#xff09; 1.实验需求2.实验说明及思路3.实验配置3.1 配置IP地址以及VLAN3.2 配置防火墙IP地址及划分区域3.3 配置防火墙安全策略3.4 配置防火墙NAT策略 1.实验需求 1.生产区在工作时间内可以访问服务器区&#xff0c;仅…

Adobe XD 57.1.12.2软件安装教程(附软件下载地址)

软件简介&#xff1a; 软件【下载地址】获取方式见文末。注&#xff1a;推荐使用&#xff0c;更贴合此安装方法&#xff01; Adobe XD 57.1.12.2是一款功能强大的图形化界面UI/UX设计工具&#xff0c;它集成了原型设计、界面设计和交互设计等功能。无论是网站还是移动应用程序…

代码随想录算法训练营第14天| Leetcode 102.二叉树的层序遍历、226.翻转二叉树、101.对称二叉树

目录 Leetcode 102.二叉树的层序遍历 Leetcode 226.翻转二叉树 Leetcode 101.对称二叉树 Leetcode 102.二叉树的层序遍历 题目链接&#xff1a;Leetcode 102.二叉树的层序遍历 题目描述&#xff1a;给你二叉树的根节点root &#xff0c;返回其节点值的 层序遍历 。 &#xff…

Unity学习之坦克游戏制作(2)游戏场景的制作

文章目录 1. 基础场景的搭建2. 游戏主面板2.1 拼出面板2.2 创建新面板2.3 设置面板复用2.4 退出界面 3. 坦克基类3.1 创建基类脚本3.1.1 基类基本属性3.1.2 抽象开火函数3.1.3 受伤虚函数3.1.4 死亡虚函数 4 玩家——基础移动旋转摄像机跟随4.1 玩家对象脚本4.2 控制坦克移动4.…

【Docker】实战案例 - CI/CD

作者主页&#xff1a; 正函数的个人主页 文章收录专栏&#xff1a; Docker 欢迎大家点赞 &#x1f44d; 收藏 ⭐ 加关注哦&#xff01; CI/CD 持续集成(Continuous integration) 是一种软件开发实践&#xff0c;每次集成都通过自动化的构建&#xff08;包括编译&#xff0c;发…

Dockerfile里ADD * 保留原来的目录结构

1、问题 给新模块写Dockerfile&#xff0c;很多静态资源分散在各个目录&#xff0c;于是Dockerfile里我直接一句&#xff1a; ADD ./* /dest/镜像出来后&#xff0c;启动容器&#xff0c;进入容器种后发现&#xff1a;文件拷贝成功&#xff0c;但原来的目录结构都不在了&…

Rabbitmq调用FeignClient接口失败

文章目录 一、框架及逻辑介绍1.背景服务介绍2.问题逻辑介绍 二、代码1.A服务2.B服务3.C服务 三、解决思路1.确认B调用C服务接口是否能正常调通2.确认B服务是否能正常调用A服务3.确认消息能否正常消费4.总结 四、修改代码验证1.B服务异步调用C服务接口——失败2.将消费消息放到C…

2024水资源、智慧城市与绿色发展国际会议(ICWRSCGD 2024)

2024水资源、智慧城市与绿色发展国际会议(ICWRSCGD 2024) 会议简介 2024年国际水资源、智慧城市与绿色发展大会&#xff08;ICWRSCGD 2024&#xff09;将在中国杭州举行。会议聚焦“水资源、智慧城市、绿色发展”这一最新研究领域&#xff0c;致力于促进世界顶级创新者、科学…

01 Redis的特性+下载安装启动

1.1 NoSQL NoSQL&#xff08;“non-relational”&#xff0c; “Not Only SQL”&#xff09;&#xff0c;泛指非关系型的数据库。 键值存储数据库 &#xff1a; 就像 Map 一样的 key-value 对。如Redis文档数据库 &#xff1a; NoSQL 与关系型数据的结合&#xff0c;最像关系…

代码随想录算法训练营第十一天 | 二叉树基础

代码随想录算法训练营第十一天 | 二叉树基础 文章目录 代码随想录算法训练营第十一天 | 二叉树基础1 二叉树的理论基础1.1 二叉树的类型1.2 二叉树的存储方式1.3 二叉树的遍历方式1.4 二叉树的定义 2 二叉树的递归遍历2.1 前序遍历2.2 中序遍历2.3 后序遍历 3 二叉树的迭代遍历…

C++特殊类的设计

目录 一、不能被拷贝的类 二、只能在堆上创建对象的类 三、只能在栈上创建对象的类 四、不能被继承的类 五、只能创建一个对象的类(单例模式) 下面说几种特殊要求的类的设置&#xff0c;主要学习其中所运用的一些思想&#xff0c;融会贯通 一、不能被拷贝的类 C98可以将拷…

高质量谷歌seo外链平台有哪些?

明确的说&#xff0c;没有任何必要&#xff0c;这里说的没必要指的是没必要寻找什么高质量的外链平台 所谓高质量的外链平台是什么&#xff1f;你期待在这种平台发外链能获得什么效果&#xff1f;高质量的外链平台&#xff0c;无非就是网站排名高&#xff0c;能发相关的外链的平…

iOS推送通知

文章目录 一、推送通知的介绍1. 简介2. 通知的分类 二、本地通知1. 本地通知的介绍2. 实现本地通知3. 监听本地通知的点击 三、远程通知1. 什么是远程通知2. 为什么需要远程通知3. 远程通知的原理4. 如何做远程通知5. 远程通知证书配置6. 获取远程推送要用的 DeviceToken7. 测试…

外贸SOHO产品怎么选?海洋建站选品方法?

外贸SOHO应该如何选产品&#xff1f;跨境电商独立站选品策略&#xff1f; 越来越多的人选择通过外贸SOHO创业&#xff0c;将业务拓展到国际市场。然而&#xff0c;面对琳琅满目的外贸SOHO产品&#xff0c;许多初创企业主可能会感到困惑。海洋建站将为您提供一些建议&#xff0…

直播核心岗位基础内容

一.直播间核心岗位 1.直播间前端岗位 前端岗位分工 &#xff08;1&#xff09;主播岗位职责 &#xff08;2&#xff09;场控岗位职责 &#xff08;3&#xff09;助理岗位职责 中端岗位分工 &#xff08;1&#xff09;运营岗位职责 &#xff08;2&#xff09;中控岗位职责 …

2024年Java SpringBoot 计算机软件毕业设计题目推荐

博主介绍&#xff1a;✌全网粉丝30W,csdn特邀作者、博客专家、CSDN新星计划导师、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和学生毕业项目实战,高校老师/讲师/同行交流合作✌ 主要内容&#xff1a;SpringBoot、Vue、SSM、HLM…

Hbuilder从gitlab上面拉取项目

要先下载TortoiseGit-2.15.0.0-64bit这个软件 在HBuilder中从GitLab上拉取项目&#xff0c;请按照以下步骤操作&#xff1a; 1. 打开HBuilder&#xff0c;点击左上角的“文件”菜单&#xff0c;然后选择“新建”->“项目”。 2. 在弹出的对话框中&#xff0c;选择“从Git导…