1.冒泡排序——把大的数向前移动,好像水中的气泡,随着慢慢向水面浮起会逐渐增大。
时间复杂度O(N2),空间复杂度O(1),步骤:
①、比较相邻的元素。如果第一个比第二个大,就交换他们两个。
②、对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数(也就是第一波冒泡完成)。
③、针对所有的元素重复以上的步骤,除了最后一个。
④、持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
2.选择排序——每一次从待排序的数据中选出最小的,存放在最前面,直到全部排完。
时间复杂度O(N2),空间复杂度O(1),步骤:
①、从待排序序列中,找到关键字最小的元素
②、如果最小元素不是待排序序列的第一个元素,将其和第一个元素互换
③、从余下的 N - 1 个元素中,找出关键字最小的元素,重复①、②步,直到排序结束
3.插入排序——每一步将一个待排序的数据,插入到前面已经排好的有序序列中,直到完成所有元素。
时间复杂度O(N2),空间复杂度O(1)
4.希尔排序
时间复杂度O(NlogN),空间复杂度O(1)
在插入排序中,如果一个很小的数在很靠近右边的位置,那么想让这个很小的数插入到左边已排好序列,那么序列中的数据项都必须向右移动一位,这个步骤就是将近执行了N次复制,虽然不是每个数据项都必须移动N个位置,但是每个数据项平均移动了N/2次,总共就是N2/2。希尔排序是基于插入排序的,它在插入排序中增加了一个新特性,大大的提高了插入排序的执行效率。希尔排序通过加大插入排序中元素的间隔,并在这些有间隔的元素中进行插入排序,从而使数据项能够大跨度的移动。当这些数据项排过一趟序后,希尔排序算法减小数据项的间隔再进行排序,依次进行下去,最后间隔为1时,就是我们上面说的简单的直接插入排序。
一种希尔的变形方法是用2.2来整除获取每一个间隔,对于n=100的数组,会产生序列45,20,9,4,1。
5.快速排序——快速排序是对冒泡排序的一种改进,由C. A. R. Hoare在1962年提出的一种划分交换排序,采用的是分治策略(一般与递归结合使用),以减少排序过程中的比较次数。
时间复杂度O(NlogN),空间复杂度O(1),步骤:
①、先通过第一趟排序,将数组原地划分为两部分,其中一部分的所有数据都小于另一部分的所有数据。原数组被划分为2份
②、通过递归的处理, 再对原数组分割的两部分分别划分为两部分,同样是使得其中一部分的所有数据都小于另一部分的所有数据。 这个时候原数组被划分为了4份
③、就1,2被划分后的最小单元子数组来看,它们仍然是无序的,但是! 它们所组成的原数组却逐渐向有序的方向前进。
④、这样不断划分到最后,数组就被划分为多个由一个元素或多个相同元素组成的单元,这样数组就有序了。
具体来说就是设置基准元素,左右游标:
基准元素:它是将数组划分为两个子数组的过程中,用于界定大小的值,以它为判断标准,将小于它的数组元素“划分”到一个“小数值的数组”中,而将大于它的数组元素“划分”到一个“大数值的数组”中,这样,我们就将数组分割为两个子数组,而其中一个子数组的元素恒小于另一个子数组里的元素。
左游标:它一开始指向待分割数组最左侧的数组元素,在排序的过程中,它将向右移动。左游标向右扫描, 跨过所有小于基准元素的数组元素, 直到遇到一个大于或等于基准元素的数组元素, 在那个位置停下。
右游标:它一开始指向待分割数组最右侧的数组元素,在排序的过程中,它将向左移动。右游标向左扫描, 跨过所有大于基准元素的数组元素, 直到遇到一个小于或等于基准元素的数组元素,在那个位置停下。
当左右游标相遇了,那么此时说明探测结束,将相遇位置和基准元素位置进行交换。
基准元素设定:为了找到一个数组中的中值数据,一般是取数组中第一个、中间的、最后一个,选择这三个数中位于中间的数。
6.归并排序——归并两个有序数组A和B,就生成了第三个有序数组C。数组C包含数组A和B的所有数据项。
时间复杂度O(NlogN),空间复杂度O(N),说明:把一个数组分成两半,排序每一半,把每一半都分为四分之一,对每个四分之一进行排序,然后把它们归并成一个有序的一半。类似的,如何给每个四分之一数组排序呢?把每个四分之一分成八分之一,对每个八分之一进行排序,以此类推,反复的分割数组,直到得到的子数组是一个数据项,那这就是这个递归算法的边界值,也就是假定一个数据项的元素是有序的。
7.桶排序
时间复杂度O(N),空间复杂度O(N),桶排序需要两个辅助空间:桶空间和桶内的元素链表空间。精髓就是将待排序数据按区间切分装入桶,然后在桶内进行插入排序,最后按序合并桶内数据即可。缺点:需要已知最大最小值,且数据均匀分布的。优点:算法简单。
8.基数排序
时间复杂度O(N),空间复杂度O(N),其实也是桶排序,不同的是桶划分的方法是按基数,如10进制数则可划分为0,1,2,3,4,5,6,7,8,9共10个桶,先按待排序数据的个位数把数据放入各个桶中,然后按桶序取出到序列中,此时序列中的数据的个位数已经是有序的了,然后再把序列中的数按十位数把数据依次放入对应的桶中,然后按桶的次序再取出到序列中,此时序列中的数据的十位数和个位数都已经是有序的了,以此类推,直到所有的基数都排完。优点:桶内不需要插入排序,算法更简单。缺点:待排序数据的位数需大致相同。
9.计数排序
时间复杂度O(N),空间复杂度O(N),对于整数排序,先获取待排序数据的最大最小值min,max,生成计数数组int[max-min+1],int[0]=min,int[max-min]=max;然后遍历待排序数据,每遍历一个数据再技术数组对应的小标数据中加1,最后遍历计数数组得出排序结果。
相关推荐
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
排序算法总结.doc 排序算法总结.doc 排序算法总结.doc
C#排序算法总结:交换排序:最基础的冒泡排序,冒泡排序的优化版选择排序和快速排序,插入排序:直接插入排序和折半插入排序。
八大排序算法总八大排序算法总八大排序算法总八大排序算法总结
常用排序算法总结,包含:冒泡排序、鸡尾酒排序、选择排序、插入排序、二分插入排序、希尔排序、归并排序、堆排序、快速排序等排序算法总结。
排序算法总结和比较 介绍各种排序算法的特点及原理,大致总结了我们常见的所有的排序算法的特点
常用排序算法总结及C源程序常用排序算法总结及C源程序常用排序算法总结及C源程序常用排序算法总结及C源程序常用排序算法总结及C源程序常用排序算法总结及C源程序常用排序算法总结及C源程序
排序算法总结
常用排序算法总结 数据结构 ppt 课件知识 排序的复杂性 。
八大排序算法总结,包括排序原理、要点和实现,快速排序实现除外。
常用排序算法总结,包括插入排序(InsertionSort),冒泡排序(BubbleSort),选择排序(SelectionSort),快速排序(QuickSort), * 二路归并排序(MergeSort),堆排序(HeapSort)。有每一种排序算法的复杂度分析以及实现...
经典算法是计算机专业核心课程之一.计算机算法的优劣,对于计算机硬件的...本文对递归算法、分治算法、动态规划算法、贪心算法等经典的算法进行研究,着重阐述算法的设计思想、优缺点及其应用,并对算法的发展进行了探索.
深入浅出的全面介绍 精妙总结 可以把握与运用排序
10种排序算法总结.doc
几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
文档格式是chm文档,方便查看,点击即可快速浏览排序算法,里面的程序可以直接拿来用,实现语言是标准的C程序。
2019年排序算法总结范文.pdf2019年排序算法总结范文.pdf2019年排序算法总结范文.pdf2019年排序算法总结范文.pdf2019年排序算法总结范文.pdf
最经典的8大排序算法总结,插入排、冒泡排序、快速排序、简单选择排序、归并排序、二叉树排序、基数排序等。
经典排序算法总结和源码,用C++实现 是学习排序的好文档啊