当前位置:首页 > 高性能开发 > 数据结构与算法

算法跟数据结构~排序算法

优良自学吧提供算法跟数据结构~排序算法,算法和数据结构~排序算法排序算法种类 排序是指将元素集合按照规定的顺序排列。通常有两种排序方法,升序排列和降序排列。例如,

算法和数据结构~排序算法

排序算法种类

排序是指将元素集合按照规定的顺序排列。通常有两种排序方法,升序排列和降序排列。例如,对整数集{5,2,7,1}进行升序排列,结果为{1,2,5,7},对其进行降序排列结果为{7,5,2,1}。总的来说,排序的目的是使数据能够以更有意义的形式表现出来。虽然排序最显著的应用是排列数据以显示它,但它往往可以用来解决其他的问题,特别是作为某些已成型算法的一部分。

总的来说,排序算法分为两大类:比较排序和线性时间排序。比较排序依赖于比较和交换来将元素移动到正确的位置上。令人惊讶的是,并不是所有的排序算法都依赖于比较。对于那些确实依赖于比较来进行排序的算法来说,它们的运行时间往往不可能小于O(nlgn)。对于线性时间排序,从它的名字就可以看出,它的运行时间往往与它处理的数据元素个数成正比,即为O(n)。遗憾的是,线性时间排序依赖于数据集合中的某些特征,所以我们并不是在所有的场合都能够使用它。某些排序算法只使用数据本身的存储空间来处理和输出数据(这些称为就地排序),而有一些则需要额外的空间来处理和输出数据(虽然可能最终结果还是会拷贝到原始的内存空间中)。
  搜索就是在一个数据集中找到一个元素的位置,它可用于任何任务中。一种最简单的、不需要费任何脑筋的搜索方法是:简单地从数据集的一端查找到另一端。这就是所谓的线性搜索。通常,线性搜索用在那些对随机访问支持得不太好的数据结构中,例如:链表(见第5章)。另一种方法是使用二分查找,这会在本章中介绍。还有一些搜索方法专门用于特定的数据结构,例如哈希表。

插入排序

插入排序虽然不是最有效的排序方法,但它简单,并且不需要额外的存储空间。其最佳应用场景是对一个小的数据集合进行递增排序。

算法跟数据结构~排序算法

算法跟数据结构~排序算法

描 述 利用插入排序将数组data中的元素进行排序。data中元素的个数由size决定。而每个元素的大小由esize决定。函数指针compare会指 向一个用户定义的函数来比较元素大小。在递增排序中,如果key1>key2,函数返回1;如果key1=key2,函数返回0;如果 key1<key2,函数返回-1。在递减排序中,返回值相反。当issort返回时,data包含已排序的元素。
复杂度 O(n2),n为要排序的元素的个数。

快速排序

在一般情况下,一致认为快速排序是最好的一种排序算法,而且不需要额外的存储空间。其最佳应用场合是应用于大型数据集。

算法跟数据结构~排序算法

算法跟数据结构~排序算法

描述 利用快速排序将数组data中的元素进行排序。数组中的元素个数由size决定。而每个元素的大小由esize决定。参数i和k定义当前进行排序的两个部分,其值分别初始化为0和size-1。函数指针compare会指向一个用户定义的函数来比较元素大小。其函数功能与issort中描述的一样。当qksort返回时,data包含已排序的元素。
复杂度 O(nlg n),n为要被排序的元素的个数。

归并排序

归并排序基本上与快速排序算法的性能相同,但它需要使用两倍于快速排序的存储空间。而具有讽刺意味的是,其最佳应用场合是在超大数据集中,因为归并排序的原理就是对原始的乱序数据不断进行对半分割。

算法跟数据结构~排序算法

算法跟数据结构~排序算法

描述 利用归并排序将数组data中的元素进行排序。数组中的元素个数由size决定。而每个元素的大小由esize决定。参数i和k定义当前进行排序的两个部分,其值分别初始化为0和size-1。函数指针compare会指向一个用户定义的函数来比较元素大小。其函数功能与issort中描述的一样。当mgsort返回时,data中包含已排序的元素。
复杂度 O(nlg n),n为要排序的元素的个数。

计数排序

计数排序是一种稳定的线性时间排序算法,当知道数据集中整数的最大值的情况下会经常用到此算法。它主要用来实现基数排序

算法跟数据结构~排序算法

算法跟数据结构~排序算法

描述 利用计数排序将数组data中的整数进行排序。data中的元素个数由size决定。参数k为data中最大的整数加1。当ctsort返回时,data中包含已排序的元素。
复杂度 O(n+k),n为要排序的元素的个数,k为data中最大的整数加1。

基数排序

基数排序是逐位对元素进行排序的线性时间排序算法。基数排序适用于固定大小的元素集,并且其中的元素易于分割,且易于用整数表示。

算法跟数据结构~排序算法

算法跟数据结构~排序算法

描述 利用计数排序将数组data中的整数进行排序。数组data中整数的个数由size决定。参数p指定每个整数包含的位数,k指定基数。当rxsort返回时,data包含已排序的整数。
复杂度 O(pn+pk),n为要排序的元素的个数,k为基数,p为位的个。

 

感谢各位的阅读!今天主要吃掉这个排序算法,也是面试时经常会被问到的,哈哈!

1楼笑对当空
总感觉快速排序的结果不太对啊,假设如下的数组,,6 2 3 1 5 7 4 8,1 2 3 6 5 4 7 8,1 2 3 6 4 5 7 8,结果就是1 2 3 6 4 5 7 8了啊 是不是我理解错了

(本文来自互联网,不代表搜站(http://www.ylzx8.cn/)的观点和立场)
本站所有内容来自互联网,若本站收录的信息无意侵犯了贵司版权,请给我们来信(ylzx8cn@163.com),我们会及时处理和回复,谢谢