IT数码 购物 网址 头条 软件 日历 阅读 图书馆
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
图片批量下载器
↓批量下载图片,美女图库↓
图片自动播放器
↓图片自动播放器↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
 
   -> 数据结构与算法 -> 【Java版算法思想(排序)】选择&冒泡&快排 -> 正文阅读

[数据结构与算法]【Java版算法思想(排序)】选择&冒泡&快排

本文代码已上传github: https://github.com/chenruoyu0319/data-structure-for-java/tree/main/%E9%80%89%E6%8B%A9%26%E5%86%92%E6%B3%A1%26%E5%BF%AB%E6%8E%92%EF%BC%88%E6%8E%92%E5%BA%8F%EF%BC%89

一、选择排序

选择排序的思路和插入排序非常相似,也分已排序和未排序区间。但选择排序每次会从未排序区间中找到最小的元素,将其放到已排序区间的末尾(即未排序区间的第一个)。但是不像插入排序会移动数组,选择排序会每次对元素进行交换,如以下例子:

4 5 6 3 2 1

第一次: 1 5 6 3 2 4

第二次: 1 2 6 3 5 4

每次确保排完一个数

分析:

1.时间复杂度:O(N^2)

2.空间复杂度:O(n)

3.交换次数: 比较多

4.稳定性:不稳定

二、冒泡排序

核心思路:冒泡排序只会操作相邻的两个数据。每次冒泡操作都会对相邻的两个元素进行比较,看是否满足大小关系要求。如果不满足就让它俩互换。一次冒泡会让至少一个元素移动到它应该在的位置,重复n次,就完成了n个数据的排序工作。

举例说明:4 5 6 3 2 1,从小到大排序。

1 2 3 4 5 6进行排序:什么样的情况下不做任何交换了呢,那就是所有的数都在它应该在的位置;O(n)

第一次冒泡的结果:4 5 6 3 2 1->4 5 3 6 2 1 - > 4 5 3 2 6 1 -> 4 5 3 2 1 6,哪个元素的位置确定了,6

第二次冒泡的结果:4 5 3 2 1 6->4 3 5 2 1 6 -> 4 3 2 5 1 6 -> 4 3 2 1 5 6

第三次冒泡的结果:4 3 2 1 5 6->3 4 2 1 5 6 -> 3 2 4 1 5 6 -> 3 2 1 4 5 6

第四次冒泡的结果:3 2 1 4 5 6->2 3 1 4 5 6 -> 2 1 3 4 5 6

第五次冒泡的结果:2 1 3 4 5 6->1 2 3 4 5 6

分析:

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

2.空间复杂度:O(n)

3.交换次数:挺大的

4.稳定性:稳定

三、快速排序

在这里插入图片描述

45 28 80 90 50 16 100 10

基准数:一般就是取要排序序列的第一个。

第一次排序基准数:45

从后面往前找到比基准数小的数进行对换:

10 28 80 90 50 16 100 45

从前面往后面找比基准数大的进行对换:

10 28 45 90 50 16 100 80 进行了一次部分排序

下一次部分排序

10 28 16 90 50 45 100 80

再下一次部分排序

10 28 16 45 50 90 100 80

以基准数分为3部分,左边的比之小,右边比之大:

{10 28 16} 45 {50 90 100 80}

到此第一次以45位基准数的排序完成。

四、对快速排序的分析

1.时间复杂度:nlogn 最坏的情况就是O(n^2)

2.空间复杂度:O(n)

3.稳定性:不稳定

4.快排和归并的对比:

(1)归并排序的处理过程是由下到上的,先处理子问题,然后再合并。

(2)快排其实就是从上到下,先分区,在处理子问题,不用合并。

5.快排的优化:

三数取中(选基准)+插排(优化)+三向切分聚集重复值(优化)的时间复杂度同STL中的Sort近似。

最理想的方法是,选择的基准恰好能把待排序序列分成两个等长的子序列

1、随机选取基准:在待排序列是部分有序时,固定选取枢轴使快排效率底下,要缓解这种情况,就引入了随机**选取枢轴。

思想:取待排序列中任意一个元素作为基准。

2、三数取中:使用左端、右端和中心位置上的三个元素比较,大小为中值**的作为枢纽元。

注:使用三数取中选择枢轴优势还是很明显的,但是还是处理不了重复数组

3、**引入插入排序:**在数组长度大于某一个阈值范围时,我们进行递归快排;当数据长度小于阈值时,我们进行插入排序。

4、**三向切分法(聚集重复值):**在一次分割结束后,可以把与Key相等的元素聚在一起,继续下次分割时,不用再对与key相等元素分割。

具体过程有两步:一在划分过程中将与基准值相等的元素放入数组两端;二划分结束后,再将两端的元素移到基准值周围。

主要用于具有大量重复数据的情况,可以大大提高效率,因为正常的快排同样会把这些重复数进行递归。

五、各种排序对比

排序名称时间复杂度是否稳定额外空间开销
插入排序O(n^2)稳定O(1)
冒泡排序O(n^2)稳定O(1)
选择排序O(n^2)不稳定O(1)
希尔排序O(n^2)不稳定O(1)
归并排序O(nlogn)稳定O(n)
快速排序O(nlogn)不稳定O(1)

这么多种排序算法我们究竟应该怎么选择呢?:

1.分析场景:稳定还是不稳定

2.数据量:数据量小的时候选什么?比如就50个数,优先选插入或冒泡

大数据量(5000*5000=25000000),优先选择快排或归并

3.分析空间:

综上所述,没有一个固定的排序算法,都是要根据情况分析的。但是如果你不会分析的情况下,就选择归并或者快排。

实例:C++ qsort:快排+插入排序

,优先选插入或冒泡

大数据量(5000*5000=25000000),优先选择快排或归并

3.分析空间:

综上所述,没有一个固定的排序算法,都是要根据情况分析的。但是如果你不会分析的情况下,就选择归并或者快排。

实例:C++ qsort:快排+插入排序

jdk里面有Arrays.sort:基础类型比如int double 用的快排,对象排序,用的是归并+timeSort。

  数据结构与算法 最新文章
《算法系列》之 数组
Python描述 LeetCode 剑指 Offer II 091. 粉
【八大排序①】插入排序(直接插入排序、希
【恋上数据结构与算法】理论 三: 链表:Li
LeetCode 剑指 Offer II 091.粉刷房子 - 原
2022-06-27 数据结构与算法-递归、冒泡、插
AcWing 848. 有向图的拓扑序列(拓扑排序模
排序算法-C++
C语言求最大公约数
2021.12.09 - SX09-08.跳跃游戏 II
上一篇文章      下一篇文章      查看所有文章
加:2021-12-08 14:04:10  更:2021-12-08 14:05:23 
 
开发: C++知识库 Java知识库 JavaScript Python PHP知识库 人工智能 区块链 大数据 移动开发 嵌入式 开发工具 数据结构与算法 开发测试 游戏开发 网络协议 系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑 笔记本 显卡 显示器 固态硬盘 硬盘 耳机 手机 iphone vivo oppo 小米 华为 单反 装机 图拉丁
360图书馆 购物 三丰科技 阅读网 日历 万年历 2022年6日历 -2022/6/30 16:13:07-
图片自动播放器
↓图片自动播放器↓
TxT小说阅读器
↓语音阅读,小说下载,古典文学↓
一键清除垃圾
↓轻轻一点,清除系统垃圾↓
图片批量下载器
↓批量下载图片,美女图库↓
  网站联系: qq:121756557 email:121756557@qq.com  IT数码