设为首页 加入收藏

TOP

算法1 七大排序之:冒泡排序和快速排序
2018-01-17 13:05:05 】 浏览:126
Tags:算法 七大 排序 冒泡 快速

排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列;老师查看上课出勤情况时,会按学生学号顺序点名;高考录取时,会按成绩总分降序依次录取等。排序是数据处理中经常使用的一种重要的运算,它在我们的程序开发中承担着非常重要的角色。


排序分为以下四类共七种排序方法:


交换排序:


  ① 冒泡排序 
  ② 快速排序


选择排序:


  ③ 直接选择排序 
  ④ 堆排序


插入排序:


  ⑤ 直接插入排序 
  ⑥ 希尔排序


合并排序:


  ⑦ 合并排序


这篇文章主要总结的是交换排序(即冒泡排序和快速排序),交换排序的基本思想是:两两比较待排序元素,如果发现两个元素的次序相反时即进行交换,直到所有元素都没有反序时为止。我会从以下几个方面进行总结:


1、冒泡排序及算法实现


2、快速排序及算法实现


3、冒泡排序VS快速排序


什么是冒泡排序呢?冒泡排序是一种简单的排序方法,它的基本思想是:通过相邻两个元素之间的比较和交换,使较大的元素逐渐从前面移向后面(升序),就像水底下的气泡一样逐渐向上冒泡,所以被称为“冒泡”排序。冒泡排序的最坏时间复杂度为O(n2),平均时间复杂度为O(n2)


下面以一张图来展示冒泡排序的全过程,其中方括号内为下一轮要排序的元素,方括号后面的第一个元素为本轮排序浮出来的最大元素。



冒泡排序算法的代码实现:


BubbleSort.java


测试结果:



快速排序(Quick Sort) 是对冒泡排序的一种改进方法,在冒泡排序中,进行元素的比较和交换是在相邻元素之间进行的,元素每次交换只能移动一个位置,所以比较次数和移动次数较多,效率相对较低。而在快速排序中,元素的比较和交换是从两端向中间进行的,较大的元素一轮就能够交换到后面的位置,而较小的元素一轮就能交换到前面的位置,元素每次移动的距离较远,所以比较次数和移动次数较少,速度较快,故称为“快速排序”。


快速排序的基本思想是:通过一轮排序将待排序元素分割成独立的两部分, 其中一部分的所有元素均比另一部分的所有元素小,然后分别对这两部分的元素继续进行快速排序,以此达到整个序列变成有序序列。快速排序的最坏时间复杂度为O(n2),平均时间复杂度为O(n*log2n)   



快速排序算法的代码实现:


QuickSort.java 


测试结果:



代码如下:


BubbleVsQuick.java 


测试结果:



可见,快速排序的速度比冒泡排序更快。


】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
上一篇算法2 七大排序之:直接选择排序.. 下一篇算法1 七大排序之:冒泡排序和快..

最新文章

热门文章

Hot 文章

Python

C 语言

C++基础

大数据基础

linux编程基础

C/C++面试题目