算法学习00_排序概述篇

问题定义

《算法导论》中对于排序问题定义如下

输入：一个ｎ个数的序列 <a_1, a_2, \cdots, a_n>.
输出：输入序列的一个重排<a_1', a_2',\cdots, a_n'>使得a_1' \leq a_2'\leq ... \leq a_n。
实际待排序的数很少是单独的数值，他们通常是称为记录（record）的数据集的一部分。每个记录包含一个关键字，就是排序问题中要重排的值。记录的剩余部分由卫星数据(satellite data)组成，通常与关键字是一同存取。

九种经典排序算法

9种经典排序算法

排序算法的性质

时间复杂度

对于算法的时间复杂度有严格的数学定义，不去细究，感性上的认识，大Ｏ表示算法耗费的时间和输入规模的关系。

稳定性

排序前后相同的元素相对位置不变的性质称为稳定性。如下序列中存在两个相同元素２，对于稳定的排序算法，排序后两个元素相对位置不变，否则不稳定。
｛１，-1, 2, 2, 3, 4｝
稳定性和算法的实际实现相关，同一个算法虽然理论上可以做到稳定，但是由于具体实现细节不同可能导致其不稳定。

原址排序

原址排序是指算法排序过程仅有常数个元素存储在输入数组之外。

最后编辑于 ：
©著作权归作者所有,转载或内容合作请联系作者
平台声明：文章内容（如有图片或视频亦包括在内）由作者上传并发布，文章内容仅代表作者本人观点，简书系信息发布平台，仅提供信息存储服务。

推荐阅读更多精彩内容

  • （转）八大排序算法
    概述 排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    蚁前阅读 5,250评论 0赞 52
  • 八大排序算法 (转载)
    概述：排序有内部排序和外部排序，内部排序是数据记录在内存中进行排序，而外部排序是因排序的数据很大，一次不能容纳全部...
    每天刷两次牙阅读 3,757评论 0赞 15
  • [算法总结] 十大排序算法
    本文首发于我的个人博客：尾尾部落 排序算法是最经典的算法知识。因为其实现代码短，应该广，在面试中经常会问到排序算法...
    繁著阅读 4,595评论 3赞 118
  • 玉玛茜（言情）
    1. 遇到玉玛茜那天，是我工作的第一天，也是我分手的第一天。 这天晚上，我和女朋友——现在应该称为前女友——像往常...
    常夏娃娃阅读 453评论 0赞 3
  • 2018-04-21python运算符(部分)和进制转换
    Python算术运算符 //和/的区别：//是地板除floor，只得到商的整数部分。下例：做浮点运算时 注意：Py...
    开子的私家地阅读 468评论 1赞 0