算法之排序算法的算法思想和使用场景总结

1. 概述

排序算法是计算机技术中最基本的算法,许多复杂算法都会用到排序。尽管各种排序算法都已被封装成库函数供程序员使用,但了解排序算法的思想和原理,对于编写高质量的软件,显得非常重要。

本文介绍了常见的排序算法,从算法思想,复杂度和使用场景等方面做了总结。

2. 几个概念

(1)排序稳定:如果两个数相同,对他们进行的排序结果为他们的相对顺序不变。例如A={1,2,1,2,1}这里排序之后是A = {1,1,1,2,2} 稳定就是排序后第一个1就是排序前的第一个1,第二个1就是排序前第二个1,第三个1就是排序前的第三个1。同理2也是一样。不稳定就是他们的顺序与开始顺序不一致。

(2)原地排序:指不申请多余的空间进行的排序,就是在原来的排序数据中比较和交换的排序。例如快速排序,堆排序等都是原地排序,合并排序,计数排序等不是原地排序。

总体上说,排序算法有两种设计思路,一种是基于比较,另一种不是基于比较。《算法导论》一书给出了这样一个证明:“基于比较的算法的最优时间复杂度是O(N lg N)”。对于基于比较的算法,有三种设计思路,分别为:插入排序,交换排序和选择排序。非基于比较的排序算法时间复杂度为O(lg N),之所以复杂度如此低,是因为它们一般对排序数据有特殊要求。如计数排序要求数据范围不会太大,基数排序要求数据可以分解成多个属性等。

3. 基于比较的排序算法

正如前一节介绍的,基于比较的排序算法有三种设计思路,分别为插入,交换和选择。对于插入排序,主要有直接插入排序,希尔排序;对于交换排序,主要有冒泡排序,快速排序;对于选择排序,主要有简单选择排序,堆排序;其它排序:归并排序。

3.1  插入排序

(1) 直接插入排序
特点:稳定排序,原地排序,时间复杂度O(N*N)
思想:将所有待排序数据分成两个序列,一个是有序序列S,另一个是待排序序列U,初始时,S为空,U为所有数据组成的数列,然后依次将U中的数据插到有序序列S中,直到U变为空。

适用场景:当数据已经基本有序时,采用插入排序可以明显减少数据交换和数据移动次数,进而提升排序效率。

(2)希尔排序

特点:非稳定排序,原地排序,时间复杂度O(n^lamda)(1 < lamda < 2), lamda和每次步长选择有关。

思想:增量缩小排序。先将序列按增量划分为元素个数近似的若干组,使用直接插入排序法对每组进行排序,然后不断缩小增量直至为1,最后使用直接插入排序完成排序。

适用场景:因为增量初始值不容易选择,所以该算法不常用。

3.2  交换排序

(1)冒泡排序

特点:稳定排序,原地排序,时间复杂度O(N*N)
思想:将整个序列分为无序和有序两个子序列,不断通过交换较大元素至无序子序列首完成排序。

适用场景:同直接插入排序类似

(2)快速排序

特点:不稳定排序,原地排序,时间复杂度O(N*lg N)
思想:不断寻找一个序列的枢轴点,然后分别把小于和大于枢轴点的数据移到枢轴点两边,然后在两边数列中继续这样的操作,直至全部序列排序完成。

适用场景:应用很广泛,差不多各种语言均提供了快排API

3.3  选择排序

(1)简单选择排序

特点:不稳定排序(比如对3 3 2三个数进行排序,第一个3会与2交换),原地排序,时间复杂度O(N*N)

思想:将序列划分为无序和有序两个子序列,寻找无序序列中的最小(大)值和无序序列的首元素交换,有序区扩大一个,循环下去,最终完成全部排序。

适用场景:交换少

(2) 堆排序

特点:非稳定排序,原地排序,时间复杂度O(N*lg N)
思想:小顶堆或者大顶堆
适用场景:不如快排广泛

3.4  其它排序

(1) 归并排序

特点:稳定排序,非原地排序,时间复杂度O(N*N)
思想:首先,将整个序列(共N个元素)看成N个有序子序列,然后依次合并相邻的两个子序列,这样一直下去,直至变成一个整体有序的序列。
适用场景:外部排序

4. 非基于比较的排序算法

非基于比较的排序算法主要有三种,分别为:基数排序,桶排序和计数排序。这些算法均是针对特殊数据的,不如要求数据分布均匀,数据偏差不会太大。采用的思想均是内存换时间,因而全是非原地排序。

4.1 基数排序

特点:稳定排序,非原地排序,时间复杂度O(N)

思想:把每个数据看成d个属性组成,依次按照d个属性对数据排序(每轮排序可采用计数排序),复杂度为O(d*N)

适用场景:数据明显有几个关键字或者几个属性组成

4.2  桶排序

特点:稳定排序,非原地排序,时间复杂度O(N)

思想:将数据按大小分到若干个桶(比如链表)里面,每个桶内部采用简单排序算法进行排序。

适用场景:0

4.3  计数排序

特点:稳定排序,非原地排序,时间复杂度O(N)

思想:对每个数据出现次数进行技术(用hash方法计数,最简单的hash是数组!),然后从大到小或者从小到大输出每个数据。

使用场景:比基数排序和桶排序广泛得多。

5.  总结

对于基于比较的排序算法,大部分简单排序(直接插入排序,选择排序和冒泡排序)都是稳定排序,选择排序除外;大部分高级排序(除简单排序以外的)都是不稳定排序,归并排序除外,但归并排序需要额外的存储空间。对于非基于比较的排序算法,它们都对数据规律有特殊要求 ,且采用了内存换时间的思想。排序算法如此之多,往往需要根据实际应用选择最适合的排序算法。

(0)

相关推荐

  • java 数据结构基本算法希尔排序

    C语言数据结构基本算法希尔排序 前言: 基本思想:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的下标相差d.对每组中全部元素进行直接插入排序, 然后再用一个较小的增量(d/2)对它进行分组,在每组中再进行直接插入排序.当增量减到1时,进行直接插入排序后,排序完成. 实现代码: public class ShellSort { /** * 原理:算法先将要排序的一组数按某个增量d(n/2,n为要排序数的个数)分成若干组,每组中记录的 * 下标相差d.对每组

  • 算法之排序算法的算法思想和使用场景总结

    1. 概述 排序算法是计算机技术中最基本的算法,许多复杂算法都会用到排序.尽管各种排序算法都已被封装成库函数供程序员使用,但了解排序算法的思想和原理,对于编写高质量的软件,显得非常重要. 本文介绍了常见的排序算法,从算法思想,复杂度和使用场景等方面做了总结. 2. 几个概念 (1)排序稳定:如果两个数相同,对他们进行的排序结果为他们的相对顺序不变.例如A={1,2,1,2,1}这里排序之后是A = {1,1,1,2,2} 稳定就是排序后第一个1就是排序前的第一个1,第二个1就是排序前第二个1,第

  • C++实现十大排序算法及排序算法常见问题

    目录 前言 0 概述 1 冒泡排序 2 选择排序 3 插入排序 4 希尔排序 5 归并排序 6 堆排序 7 快速排序 8 计数排序 9 桶排序 10 基数排序 总结 前言 本文为C++实现的十大排序算法及基于排序算法解决的一些常见问题,每一种算法均实际运行,确保正确无误.文中内容为自己的一些理解,如有错误,请大家指正. 0 概述 在十种排序算法中,前七种是比较类排序,后三种是非比较类排序,每种算法的最好.最坏.平均时间复杂度,空间复杂度以及稳定性如下表所示.稳定性是指排序前后相等的元素相对位置保

  • C语言数据结构与算法之排序总结(一)

    目录 一.前言 二.基本概念 1.排序 2.排序方法的稳定性 3.内部和外部排序 三.插入类排序 1.直接插入排序 2.折半插入排序 3.希尔排序 四.交换类排序 1.冒泡排序 2.快速排序 五.总结比较 一.前言 学习目标: 排序和查找密不可分,将待处理的数据按关键值大小有序排列后,查找更加快速准确 理解各种排序算法的定义和特点,并能将代码灵活运用 掌握各种排序方法时间复杂度与空间复杂度 理解排序稳定和不稳定的概念                 重点和难点: 希尔.快速.堆.归并排序这几种快

  • 图解Java经典算法希尔排序的原理与实现

    目录 希尔排序 算法思想 图解 代码实现(Java) 希尔排序 希尔排序时插入排序的一种,也称缩小增量排序,是直接插入排序的一种更高效的改进版本.希尔排序是非稳定排序算法. 算法思想 希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序,随着增量逐渐减少,每组包含的数越来越多当增量减至1时,整个序列恰好被分成一组,算法完成. 我们以增序排序为例,希尔排序基本步骤:选择初始增量gap=length/2,缩小增量继续以gap=gap/2的方式进行,直到增量gap=1为止,增量的每次变

  • Python实现桶排序与快速排序算法结合应用示例

    本文实例讲述了Python实现桶排序与快速排序算法结合应用的方法.分享给大家供大家参考,具体如下: #-*- coding: UTF-8 -*- import numpy as np from QuickSort import QuickSort def BucketSort(a, n): barrel = {} for i in xrange(0,n): barrel.setdefault(i, []) min = np.min(a) max = np.max(a) for x in a: f

  • Python排序搜索基本算法之归并排序实例分析

    本文实例讲述了Python排序搜索基本算法之归并排序.分享给大家供大家参考,具体如下: 归并排序最令人兴奋的特点是:不论输入是什么样的,它对N个元素的序列排序所用时间与NlogN成正比.代码如下: # coding:utf-8 def mergesort(seq): if len(seq)<=1: return seq mid=int(len(seq)/2) left=mergesort(seq[:mid]) right=mergesort(seq[mid:]) return merge(lef

  • Python排序搜索基本算法之堆排序实例详解

    本文实例讲述了Python排序搜索基本算法之堆排序.分享给大家供大家参考,具体如下: 堆是一种完全二叉树,堆排序是一种树形选择排序,利用了大顶堆堆顶元素最大的特点,不断取出最大元素,并调整使剩下的元素还是大顶堆,依次取出最大元素就是排好序的列表.举例如下,把序列[26,5,77,1,61,11,59,15,48,19]排序,如下: 基于堆的优先队列算法代码如下: def fixUp(a): #在堆尾加入新元素,fixUp恢复堆的条件 k=len(a)-1 while k>1 and a[k//2

  • Python排序搜索基本算法之插入排序实例分析

    本文实例讲述了Python排序搜索基本算法之插入排序.分享给大家供大家参考,具体如下: 插入排序生活中非常常见,打扑克的时候人的本能就在用插入排序:把抽到的一张插入到手上牌的正确位置上.有两种插入排序方法,一种基于比较,另一种基于交换.代码如下: 1.基于比较的插入排序: # coding:utf-8 def insertionSort(seq): length=len(seq) for i in range(1,length): tmp=seq[i] for j in range(i,0,-1

  • Python排序搜索基本算法之选择排序实例分析

    本文实例讲述了Python排序搜索基本算法之选择排序.分享给大家供大家参考,具体如下: 选择排序就是第n次把序列中最小的元素排在第n的位置上,一旦排好就是该元素的绝对位置.代码如下: # coding:utf-8 def selectionSort(seq): length=len(seq) for i in range(length): mini=min(seq[i:]) if seq[i]>mini: j=seq.index(mini,i) seq[i],seq[j]=seq[j],seq[

随机推荐