搜寻演算法Sorting algorithm
介绍原因
因为icebear在搜寻过程中会将人气质较高的料理排在搜寻结果的前半段,所以需要用到排序演算法,因此icebear在这里介绍几个常见的演算法。
- 简介
排序演算法是一种能将一串资料依照特定排序方式进行排列的演算法,最常用到的排序方式是数值顺序以及字典顺序。
有效的排序演算法在像是搜寻演算法与合并演算法中非常重要,才能让这些演算法得到正解。
排序演算法也用在处理文字资料以及产生人类可读的输出结果。排序演算法的输出必须遵守下列两个基本原则:
- 输出结果为递增或递减序列
- 输出结果是原输入的一种排列、或是重组
- 排序法分类
- 时间复杂度 : 依据串列(list)的大小(n)计算最差、平均、和最好表现。一般而言,好的表现是O(nlogn),坏的表现是O(n^2)。
一个排序理想的表现是O(n),但平均而言不可能达到。基於比较的排序演算法对大多数输入而言至少需要O(nlogn)。使用具有强大计算能力的计算机,能令时间复杂度趋近於O(n),但不等於O(n)。
- 记忆体使用量
- 稳定性:稳定的排序演算法会让原本有相等键值的纪录维持相对次序。也就是当纪录X=Y,且在原本的串列中X出现在Y之前时,在排序过的串列中X也将会是在Y之前。
- 其他 : 依据排序的方法:插入、交换、选择、合并等等。
- 常见排序演算法
-
泡沫排序(BubbleSort)
- 资料物件 :阵列
- 稳定性 : 阵列(Y)
- 时间复杂度 :
- 平均 : O(n^2)
- 额外空间复杂度 :O(1)
- 运作方式 :
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最後一对。这步做完後,最後的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最後一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较
-
选择排序 (Selectionsort)
- 资料物件 :阵列、链结串列
- 稳定性 :阵列(N)、链结串列(Y)
- 时间复杂度 :
- 平均 : O(n^2)
- 额外空间复杂度 :O(1)
- 运作方式 :
首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
然後,再从剩余未排序元素中继续寻找最小(大)元素,然後放到已排序序列的末尾。
以此类推,直到所有元素均排序完毕。
-
插入排序(InsertionSort)
- 资料物件 : 阵列、链结串列
- 稳定性 : 阵列(Y)、链结串列(Y)
- 时间复杂度 :
- 平均 : O(n^2)
- 额外空间复杂度 :O(1)
- 运作方式 :
- 从第一个元素开始,该元素(A)可以认为已经被排序
- 取出下一个元素,在已经排序的元素序列中从後向前扫描
- 如果A大於新元素,将A移到下一位置
- 重复步骤3,直到找到已排序的元素小於或者等於新元素的位置(X)
- 将新元素插入到X後
- 重复步骤2~5
-
堆积排序(HeapSort)
- 资料物件 :阵列
- 稳定性 : 阵列(N)
- 时间复杂度 :
- 平均:O(nlogn)
- 额外空间复杂度 :O(1)
- 运作方式 :
在堆积的资料结构中,堆积中的最大值总是位於根节点(在优先伫列中使用堆积的话堆积中的最小值位於根节点)。堆积中定义以下几种操作:
- 最大堆积调整(Max Heapify):将堆积的末端子节点作调整,使得子节点永远小於父节
- 建立最大堆积(Build Max Heap):将堆积中的所有数据重新排序
- 堆积排序(HeapSort):移除位在第一个数据的根节点,并做最大堆积调整的递回运算
-
合并排序(MergeSort)
- 资料物件 :阵列、链结串列
- 稳定性 : 阵列()、链结串列()
- 时间复杂度 :
- 平均 :
- 阵列 :O(〖nlog〗^2 n)
- 链结串列 : O(nlogn)
- 额外空间复杂度 :
- 阵列 :O(1)
- 链结串列 :
- O(1)
- O(n)+ O(logn) ->如果非从上到下
- 运作方式 :
- 递回法(Top-down)
- 申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并後的序列
- 设定两个指标,最初位置分别为两个已经排序序列的起始位置
- 比较两个指标所指向的元素,选择相对小的元素放入到合并空间,并移动指标到下一位置
- 重复步骤3直到某一指标到达序列尾
- 将另一序列剩下的所有元素直接复制到合并序列尾
- 迭代法(Bottom-up)
- 原理如下(假设序列共有n个元素)
- 将序列每相邻两个数字进行合并操作,形成(n/2)个序列,排序後每个序列包含两/一个元素
- 若此时序列数不是1个则将上述序列再次合并,形成(n/4)个序列,每个序列包含四/三个元素
- 重复步骤2,直到所有元素排序完毕,即序列数为1
-
快速排序(QuickSort)
- 资料物件 :阵列、链结串列
- 稳定性 : 阵列(N)、链结串列(Y)
- 时间复杂度 :
- 平均 : O(nlogn)
- 最坏 : O(n^2)
- 额外空间复杂度 : O(logn)
- 运作方式 :
- 挑选基准值:从数列中挑出一个元素,称为「基准」(pivot)。
- 分割:重新排序数列,所有比基准值小的元素摆放在基准前面 ;所有比基准值大的元素摆在基准後面(与基准值相等的数可以到任何一边)。在这个分割结束之後,对基准值的排序就已经完成。
- 回排序子序列:利用递回将基准值左右的子序列排序。
好啦 !! Icebear的简介基本上就到这里了,明天就要开始MySQL的学习了 !!