黑马程序员技术交流社区

标题: 关于排序 [打印本页]

---

作者: 王小五-fight    时间: 2013-4-18 15:55
标题: 关于排序


常用的排序都有哪些？看老师的视频中有冒泡和选择排序，如何去比较不同排序的效率，以及各种排序的适用范围。

---

作者: 殇_心。    时间: 2013-4-18 16:47
就说几种比较常用的排序算法吧。
冒泡排序：讲排序是都会讲到这个的。简单容易实现。时间复杂度为O(n²)，适应数据量比较少的情况。

选择排序：对冒泡排序的一种优化。优化了空间复杂度。但是时间复杂度还是O(n²)。和冒泡一样，适应数据量小的情况。

快速排序。Arrays中的sort方法就是快排。对于大的、乱数串列一般相信是最快的已知排序 。
就讲这么几种吧。实在太多了。

比较排序算法，甚至说各种算法，都是从时间复杂度，空间复杂度来说的。

---

作者: 李大伟    时间: 2013-4-18 17:20

殇_心。 发表于 2013-4-18 16:47
就说几种比较常用的排序算法吧。
冒泡排序：讲排序是都会讲到这个的。简单容易实现。时间复杂度为O(n²)， ...

补充一点，sort是按自然排序，要是倒序排的话 ，得取反，

---

作者: gerenvip    时间: 2013-4-18 23:02
排序算法有：
冒泡排序：比较简单，如果不追求效率的话，可以使用这个。序列的初始状态为"正序"，则冒泡排序过程只需进行一趟排序，在排序过程中只需进行n-1次比较，且不移动记录；反之，若记录序列的初始状态为"逆序"，则需进行n(n-1）/2次比较和记录移动。因此冒泡排序总的时间复杂度为O(n*n)。

选择排序：相对来说也比较简单，最好情况是，已经有序，交换0次；最坏情况是，逆序，交换n-1次，n值较小时，选择排序比冒泡排序快。

简单插入排序：简单插入排序效率还可以，每趟排序后，前面的序列都基本有序。
希尔排序：不需要大量的辅助空间，也基于插入排序。由于使用了增量，对中等大小规模表现良好。
归并排序：采用采用分治法，稳定的排序，一般用于对总体无序，但是各子项相对有序的数列
快速排序：快速排序是总体排序性能最好的一种排序方法，但是用到了递归，它有一个特点，就是越无序性能越高，如果元素已经基本无序，最好别用快速排序
堆排序：是一个树形选择排序，一般用的少
基数排序：基数排序的效率不错，O (nlog(r))，一般来说优于比较性排序。
这些算法在c语言版的数据结构上都有明确的讲解，你可以找这本书看看，清华大学，严蔚敏 数据结构，c语言版

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2