c语言数据结构沉底法排序(数据结构C语言排序方法)

快速排序是由东尼·霍尔所发展的一种排序算法。在平均状况下,排序 n 个项目要Ο(n log n)次比较。在最坏状况下则需要Ο(n2)次比较,但这种状况并不常见。事实上,快速排序通常明显比其他Ο(n log n) 算法更快,因为它的内部循环(inner loop)可以在大部分的架构上很有效率地被实现出来。

c语言数据结构沉底法排序(数据结构C语言排序方法)(1)

算法步骤:

1 从数列中挑出一个元素,称为 "基准"(pivot)。

2 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大地摆在基准的后面(相同的数可以到任一边)。在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。

3 递归(recursive)的把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。虽然一直递归下去,但是这个算法总会退出,因为在每次的迭代(iteration)中,它至少会把一个元素摆到它最后的位置去。

C代码的实现如下:

c语言数据结构沉底法排序(数据结构C语言排序方法)(2)

下面开始单步分析,这里用一个数组的数据来分析

c语言数据结构沉底法排序(数据结构C语言排序方法)(3)

首先将0作为比较的基准,由于右边所有的数据都比0大,所以数据不做 移动。 接下来将8作为比较基准,从最右边开始和8比较。 此时6比8小,将6移动到8前面,其他数据依次后移。

c语言数据结构沉底法排序(数据结构C语言排序方法)(4)

接着再将2和8比较,2比8小,继续将2移动到8前面,其他的数据依次后移。

c语言数据结构沉底法排序(数据结构C语言排序方法)(5)

这样将8小的数据移动到8的前面,比8大的数据在8后面保持不变。移动完成后如下:

c语言数据结构沉底法排序(数据结构C语言排序方法)(6)

接下来比较的基准变为数字6,将比6小的数据移动到6前面。 从最右边开始查找,找到1比6小,将1移动到6前面。

c语言数据结构沉底法排序(数据结构C语言排序方法)(7)

然后继续依次寻找比6小的数字,移动到6的前面,移动完成后如下:

c语言数据结构沉底法排序(数据结构C语言排序方法)(8)

然后比较的基准变为数字5,从最右边开始寻找比5小的数移动到5前面。查找到的数据为2。

c语言数据结构沉底法排序(数据结构C语言排序方法)(9)

依次查找其他比5小的数据,移动完成后如下:

c语言数据结构沉底法排序(数据结构C语言排序方法)(10)

到这里可以看到数据排序已经完成了。 整体运行流程如下:

下面测试一下最坏情况下的排序情况

c语言数据结构沉底法排序(数据结构C语言排序方法)(11)

可以看到最坏情况下排序的次数并没有增多,反而感觉还减少了。 再看一下最好情况下的排序情况:

c语言数据结构沉底法排序(数据结构C语言排序方法)(12)

最好情况下数据也要进行比较9次。

c语言数据结构沉底法排序(数据结构C语言排序方法)(13)

下来随机生成一个包含10000个数字的数组,测试下执行时间。

可以看到对10000个数字排序需要的时间为120ms。

c语言数据结构沉底法排序(数据结构C语言排序方法)(14)

下面用一张动图来演示一下快速排序的过程:

c语言数据结构沉底法排序(数据结构C语言排序方法)(15)

另外,对现在我们的大多数朋友来说还是学编程技术最重要!栽一棵树最好的时间是十年前,其次是现在。对于准备学习编程的小伙伴,如果你想更好地提升你的编程核心能力(内功)不妨从现在开始!

编程学习书籍分享:

c语言数据结构沉底法排序(数据结构C语言排序方法)(16)

编程学习视频分享:

c语言数据结构沉底法排序(数据结构C语言排序方法)(17)

整理分享(多年学习的源码、项目实战视频、项目笔记,基础入门教程)

欢迎转行和学习编程的伙伴,利用更多的资料学习成长比自己琢磨更快哦!

想学习C/C 编程,或者对编程感兴趣的话可以【私信】笔者粉丝群和大家一起交流~

,

免责声明:本文仅代表文章作者的个人观点,与本站无关。其原创性、真实性以及文中陈述文字和内容未经本站证实,对本文以及其中全部或者部分内容文字的真实性、完整性和原创性本站不作任何保证或承诺,请读者仅作参考,并自行核实相关内容。文章投诉邮箱:anhduc.ph@yahoo.com

    分享
    投诉
    首页