基本排序算法原理和优化

2021/12/19 14:19:28

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

(原创)

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

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)直接用插入排序
* 多线程技术

 



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


扫一扫关注最新编程教程