基本排序算法原理和优化

本文主要是介绍基本排序算法原理和优化，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

（原创）

本文讨论基本排序算法的原理和优化

1.插入排序（insertion sort）
新元素，插入到已排好序的序列中去，得到新的有序列

2.选择排序（selection sort）
每轮选最值

3.归并排序 merge sort
分为两个过程
（1）不断分割，直至单元素
（2）合并两个有序列的方法
先不断分割，再用合并的方法不断合并

4.堆排序 heap sort
（1）建树，且是max-heap，父节点>=子节点
（2）root和尾节点交换，root节点值归入有序组
（3）尾结点交换到root后的新树，再进行heapify得到新max-heap
（4）重复（2）

5.希尔排序 shell sort
插入排序的改进，
每次对隔gap的元素（list[i] 和 list[i+gap]）比较大小， 使隔gap的子序列是有序的。
不断二分gap至1，重复上面过程

6.冒泡排序
每趟相邻两元素比较，交换出最大值到最右。

7.快速排序
（1）基本原理
选一个中介，调整数列，使中介左边部分小于中介，右边部分大于等于中介
再对左右两部分递归

（2）工业优化要点

* 各函数（整数操作，指针操作，控制流，比较函数，交换函数）的耗时分析
* 双向由两个指针来遍历，而不是用一个指针单向遍历，减少交换次数
* 选取中介值的取样，尽可能的做到分割的数量差不多
* 相同元素很多的情况考虑，三段分法
* 小数组（小于20）直接用插入排序
* 多线程技术
等

这篇关于基本排序算法原理和优化的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！