动力节点首页 全国咨询热线:400-8080-105

绑定手机号,登录
手机号

验证码

微信登录
手机号登录
手机号

验证码

30天自动登录
微信登录与注册
微信扫码登录与注册

扫码关注微信公众号完成登录与注册
手机号登录
首页 > 文章

数据结构排序算法的简单介绍

08-03 10:57 440浏览
举报 T字号
  • 大字
  • 中字
  • 小字

排序算法的评价

稳定性

稳定排序算法会依照相等的关键(换言之就是值)维持纪录的相对次序。也就是一个排序算法是稳定的,就是当有两个有相等关键的纪录R和S,且在原本的串行中R出现在S之前,在排序过的串行中R也将会是在S之前。

计算复杂度(最差、平均、和最好表现)

依据串行(list)的大小(n),一般而言,好的表现是O(nlogn),且坏的行为是O(n2)。对于一个排序理想的表现是O(n)。仅使用一个抽象关键比较运算的排序算法总平均上总是至少需要O(nlogn)。

所有基于比较的排序的时间复杂度至少是 O(nlogn)。

数据结构排序算法的简单介绍

常见排序算法

常见的稳定排序算法有:

· 冒泡排序(Bubble Sort) — O(n²)

· 插入排序(Insertion Sort)— O(n²)

· 桶排序(Bucket Sort)— O(n); 需要 O(k) 额外空间

· 计数排序 (Counting Sort) — O(n+k); 需要 O(n+k) 额外空间

· 合并排序(Merge Sort)— O(nlogn); 需要 O(n) 额外空间

· 二叉排序树排序 (Binary tree sort) — O(n log n) 期望时间; O(n²)最坏时间; 需要 O(n) 额外空间

· 基数排序(Radix sort)— O(n·k); 需要 O(n) 额外空间

常见的不稳定排序算法有:

· 选择排序(Selection Sort)— O(n²)

· 希尔排序(Shell Sort)— O(nlogn)

· 堆排序(Heapsort)— O(nlogn)

· 快速排序(Quicksort)— O(nlogn) 期望时间, O(n²) 最坏情况; 对于大的、乱数串行一般相信是最快的已知排序

冒泡排序

冒泡排序是最简单最容易理解的排序算法之一,其思想是通过无序区中相邻记录关键字间的比较和位置的交换,使关键字最小的记录如气泡一般逐渐往上“漂浮”直至“水面”。 冒泡排序的复杂度,在最好情况下,即正序有序,则只需要比较n次。故,为O(n) ,最坏情况下,即逆序有序,则需要比较(n-1)+(n-2)+……+1,故,为O(n²)。

插入排序

插入排序也是一个简单的排序算法,它的思想是,每次只处理一个元素,从后往前查找,找到该元素合适的插入位置,最好的情况下,即正序有序(从小到大),这样只需要比较n次,不需要移动。因此时间复杂度为O(n) ,最坏的情况下,即逆序有序,这样每一个元素就需要比较n次,共有n个元素,因此实际复杂度为O(n²) 。

快排

快排是经典的 divide & conquer 问题,如下用于描述快排的思想、伪代码、代码、复杂度计算以及快排的变形。

快排的思想

如下的三步用于描述快排的流程:

· 在数组中随机取一个值作为标兵

· 对标兵左、右的区间进行划分(将比标兵大的数放在标兵的右面,比标兵小的数放在标兵的左面,如果倒序就反过来)

· 重复如上两个过程,直到选取了所有的标兵并划分(此时每个标兵决定的区间中只有一个值,故有序)

复杂度分析

在最好的情况下,每次 partition 都会把数组一分为二,所以时间复杂度 T(n) = 2T(n/2) + O(n)

解为 T(n) = O(nlog(n))

在最坏的情况下,数组刚好和想要的结果顺序相同,每次 partition 到的都是当前无序区中最小(或最大)的记录,因此只得到一个比上一次划分少一个记录的子序列。T(n) = O(n) + T(n-1)

解为 T(n) = O(n²)

在平均的情况下,快排的时间复杂度是 O(nlog(n))

变形

可以利用快排的 PARTITION 思想求数组中第K大元素这样的问题,步骤如下:

在数组中随机取一个值作为标兵,左右分化后其顺序为X

如果 X == Kth 说明这就是第 K 大的数

如果 X > Kth 说明第 K 大的数在标兵左边,继续在左边寻找第 Kth 大的数

如果 X < Kth 说明第 K 大的数在标兵右边,继续在右边需找第 Kth - X 大的数

这个问题的时间复杂度是 O(n)

T(n) = n + n/2 + n/4 + ... = O(n)

动力节点在线课程涵盖零基础入门,高级进阶,在职提升三大主力内容,覆盖Java从入门到就业提升的全体系学习内容。全部Java视频教程免费观看,相关学习资料免费下载!对于火爆技术,每周一定时更新!如果想了解更多相关技术,可以到动力节点在线免费观看数据结构视频教程哦!

0人推荐
共同学习,写下你的评论
0条评论
代码小兵696
程序员代码小兵696

118篇文章贡献392976字

相关课程 更多>

作者相关文章更多>

推荐相关文章更多>

Java面试题及答案整理

代码小兵66904-21 20:01

6道经典算法面试题

杨晶珍05-12 16:39

简述Spring MVC的核心组件

代码小兵49806-11 16:26

SpringMVC 中的组件

代码小兵49806-11 16:28

Spring常见面试题

代码小兵92504-17 16:07

发评论

举报

0/150

取消