排序算法

博客园: 十大经典排序算法(动图演示)

目录


1. 冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数列,一次比较两个元素,如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

Error: Markdown不支持gif的播放,请查看目录原始文件

2. 选择排序(Selection Sort)

选择排序(Selection-sort)是一种简单直观的排序算法。它的工作原理:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

Error: Markdown不支持gif的播放,请查看目录原始文件

3. 插入排序(Insertion Sort)

插入排序(Insertion-Sort)的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

Error: Markdown不支持gif的播放,请查看目录原始文件

4. 希尔排序(Shell Sort)

1959年Shell发明,第一个突破 O(n^2) 的排序算法,是简单插入排序的改进版。它与插入排序的不同之处在于,它会优先比较距离较远的元素。希尔排序又叫缩小增量排序

先将整个待排序的记录序列分割成为若干子序列,分别进行直接插入排序。

Error: Markdown不支持gif的播放,请查看目录原始文件

5. 快速排序(Quick Sort)

快速排序的基本思想:通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

核心

  1. 找中轴
  2. 左侧递归,右侧递归

所谓“分而治之”,利用递归的方式解决问题。

Error: Markdown不支持gif的播放,请查看目录原始文件

ps: 对于"快速排序"的动图展示,个人表示并不容易理解——如果类似归并排序,分成上下两排来展示,可能效果更好。相比而言,代码更容易理解。

def quick_sort(arr):
    """ 非就地排序,占用了更多的空间复杂度:(2^n - 1) * n + LogN
        当然,非就地排序更容易理解——不用研究那两个向中间对冲的“哨兵”
    """
    if len(arr) < 2:
        return arr

    pivot, left, right = arr[0], [], []
    for i in arr[1:]:
        if i < pivot:
            left.append(i)
        else:
            right.append(i)

    return quick_sort(left) + [pivot] + quick_sort(right)

5.1. 非就地排序

随机的选择一个pivot(一般可以选择数组首位,或者末位、中间位),然后逐一将其他元素分为“大于pivot”与“小于pivot”的两组。这个过程的目的,是让pivot这个中轴数归位。最后通过递归,重复这个过程。

分析下这个算法的空间复杂度,来自两部分:

  1. 引入了辅助数组:left、right
  2. 递归过程返回值占用的空间

至少第一步是可以避免的。这就是“就地快排”,但理解更有难度。

5.2. 就地快速排序

下面我们用图解的方式来演示这个排序过程:

假设下面这个数组是待排序数组:

[6, 1, 2, 7, 9, 3, 4, 5, 10, 8]

按照快速排序的思想,首先得把这组数分成相互独立的两部分,其中一部分比中的数比另一部分的数都小。如何实现这一步呢?

方法其实很简单:首先选取待排序数组的第一个数为基准数,也就是6,然后分别从初始序列“(6, 1, 2, 7, 9, 3, 4, 5, 10, 8)”两端开始“探测”。先从右往左找一个小于6的数,再从左往右找一个大于6的数,然后交换他们。这里可以用两个变量i和j,分别指向序列最左边和最右边。我们为这两个变量起个好听的名字“哨兵i”和“哨兵j”。刚开始的时候让哨兵i指向序列的最左边(即i=1),指向数字6。让哨兵j指向序列的最右边(即j=10),指向数字8。

首先哨兵 j 开始出动。因为此处设置的基准数是最左边的数,所以需要让哨兵 j 先出动,这一点非常重要(请自己想一想为什么)。哨兵 j 一步一步地向左挪动(即 j--),直到找到一个小于 6 的数停下来。接下来哨兵 i 再一步一步向右挪动(即 i++),直到找到一个数大于 6 的数停下来。最后哨兵 j 停在了数字 5 面前,哨兵 i 停在了数字 7 面前。

如果选取最左边的数arr[left]作为基准数,那么先从右边开始可保证i,j在相遇时,相遇数是小于基准数的,交换之后temp所在位置的左边都小于temp。但先从左边开始,相遇数是大于基准数的,无法满足temp左边的数都小于它。所以进行扫描,要从基准数的对面开始

现在交换哨兵 i 和哨兵 j 所指向的元素的值。交换之后的序列为(6, 1, 2, 5, 9, 3, 4, 7, 10, 8)。

接下来开始哨兵 j 继续向左挪动(再友情提醒,每次必须是哨兵 j 先出发)。他发现了 4(比基准数 6 要小,满足要求)之后停了下来。哨兵 i 也继续向右挪动的,他发现了 9(比基准数 6 要大,满足要求)之后停了下来。此时再次进行交换,交换之后的序列为(6, 1, 2, 5, 4, 3, 9, 7, 10, 8)。

哨兵 j 继续向左挪动,他发现了 3(比基准数 6 要小,满足要求)之后又停了下来。哨兵 i 继续向右移动,糟啦!此时哨兵 i 和哨兵 j 相遇了,哨兵 i 和哨兵 j 都走到 3 面前。说明此时 “探测” 结束。3 比 6 小所以我们将基准数 6 和 3 进行交换。交换之后的序列为(3, 1, 2, 5, 4, 6, 9, 7, 10, 8)。

此时第一趟排序结束,我们已经把待排序数组分成了以 6 为基准,左边一列序列,右边一序列,左边序列的数比右边序列的数都小。不过此时左右两部分中的数各自的排序仍然是混乱的,还有继续排序。

快速排序的排序过程已经通过上面的图解讲解清楚了,接下来左右两部分的数据继续按照快速排序的方式来排序。

其中左边的序列是(3, 1, 2, 5, 4),按照上面的排序图解哨兵 j 停下来的时候在 2 上面,哨兵 i 停下来的时候在 5 的上面,但此时哨兵 i 已经跑过哨兵 j 到他前面去了,所以此时不应该在把两个哨兵所对应的数交换,而应该把我们的基准数 3 和 2 交换,所以此时左侧的序列经过一次快速排序后变成了这样(2, 1, 3, 5, 4)。

右侧的序列经过一次快速排序后变成了这样(8, 7, 9, 10)。

合并基准数 6 以及左右两侧的序列:

[ 2, 1 || 3 || 5, 4  ||| 6 |||  8, 7 || 9 || 10 ]

对于排序仍然混乱的部分继续以快速排序进行排序,最终的排序应该是这样的

[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

细心的同学可能已经发现,快速排序的每一轮处理其实就是将这一轮的基准数归位,直到所有的数都归位为止,排序就结束了。下面上个霸气的图来描述下整个算法的处理过程。

快速排序之所比较快,因为相比冒泡排序,每次交换都是折半进行的。因此总的比较和交换次数就少了,速度自然就提高了。当然在最坏的情况下,仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是 O(N^2) ,它的平均时间复杂度为 O(N*logN)

5.3. 随机化快速排序

快排在选取主元的时候,每次都选取最右边的元素。当序列为有序时,会发现划分出来的两个子序列一个里面没有元素,而另一个则只比原来少一个元素。为了避免这种情况,引入一个随机化量来破坏这种有序状态。

实际上,这个过程很容易实现。pivot, left, right = arr[0], [], [] 前面增加一行乱序的代码:

pivot_idx = random.randint(1, len(arr))
arr[pivot_idx], arr[0] = arr[0], arr[pivot_idx]

5.4. 复杂度计算

快速排序的期望复杂度是O(nlogn),但最坏情况下可能就会变成O(n^2),最坏情况就是每次将一组数据划分为两组的时候,分界线都选在了边界上,使得划分了和没划分一样,最后就变成了普通的选择排序了。

快速排序的空间复杂度可以理解为递归的深度,而递归的实现依靠栈,平均需要递归logN次,所以平均空间复杂度为O(logN)。

6. 归并排序(Merge Sort)

归并排序也是一种非常高效的排序方式,其也用了分治的思想,具体的代码可以写成递归的形式。

我们首先将整个序列两两分开,然后每组中的两个元素排好序。接着就是组与组和合并,这个只需将两组所有的元素遍历一遍,即可按顺序合并。以此类推,最终所有组合并为一组时,整个数列就已经排好序了。

Error: Markdown不支持gif的播放,请查看目录原始文件

def merge_sort(arr):
    def merge(arr1, arr2):
        result = []
        while arr1 and arr2:
            arr = arr1 if arr1[0] < arr2[0] else arr2
            result.append(arr.pop(0))
        arr = arr1 if arr1 else arr2
        return result + arr

    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    return merge(merge_sort(arr[:mid]), merge_sort(arr[mid:]))

空间复杂度:虽然同样是通过递归实现的排序,然而与快速排序不同,每一层递归,result临时数组占用的空间总和为 O(1) ,经过 (logN)^2 层后,空间复杂度为 O(n)

7. 堆排序(Heap Sort)

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

Error: Markdown不支持gif的播放,请查看目录原始文件

8. 计数排序(Counting Sort)

计数排序不是基于比较的排序算法,其核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数

Error: Markdown不支持gif的播放,请查看目录原始文件

9. 桶排序(Bucket Sort)

桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。桶排序 (Bucket sort)的工作的原理:假设输入数据服从均匀分布,将数据分到有限数量的桶里,每个桶再分别排序(有可能再使用别的排序算法或是以递归方式继续使用桶排序进行排)。

10. 基数排序(Radix Sort)

基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

Error: Markdown不支持gif的播放,请查看目录原始文件

推荐这些文章:

17.快速排序

public static void quickSort(int[] arr,int left, int right) {
int l = left; //左下标
int r = right; //右下标
//pivot 中轴值
int pivot = arr[(left + right) / 2];
int temp = 0; //临时变量,作为交换时使用
//while循环的目的是让比pivot 值小放到左边
//比pivot 值大放到右边
while( l < r) {
//在pivot的左边一直找,找到大于等于piv...

js实现快速排序

算法思想都是大致分为三步
1、找基准pivot
2、遍历数组,小于基准的放在left,大于基准的放在right
3、递归
js实现

function quick(arr){
if(arr.length<=1){
return arr;
}//如果数组<=1,则直接返回
var pivotIndex=Math.floor(arr.length/2);
//找基准,并把基准从原数组中删除
var povet=arr.spilce(pivotIndex,1)[0];
//定义左右数组
var left = [];...

python实现快速排序(算法4)

时间复杂度:

最好:nlog n
最坏:n*n
平均:nlog n

空间复杂度:log n
稳定性:不稳定

递归实现
def quick_sort(arr, first, last):
if first >= last:
return
pivot = partition2(arr, first, last)
quick_sort(arr, first, pivot - 1)
quick_sort(arr, pivot + 1, last)

# 经典,好理解
def partition2(arr, lo, hi):
i ...

快速排序java实现

import java.util.*;public class Main { public static void quick_sort(int q[],int l,int r) { if(l>=r){ return; } //1.选择一个数作为分界点,将数组分为两个部分,左边都小于等于它,右边都大于等于它 int x=q[l+r>>1]; //定义两个指针,i指向的数小于等于x就往右移,直到大于它,j同理 int i=l-1,j=r+1; while(i<j){ do{ ...

排序算法总结——时空复杂度,稳定性

排序的稳定性:只两个相同的值,在排完序后依然保持其排序前的先后顺序。
 
1.基于比较的排序的时空复杂度和稳定性:
此类排序着重分析其在交换的时候是否会破坏其排序的稳定性(一般来说存在大范围的交换的排序算法就会破坏其稳定性)
总结:

 
 
2.不基于比较的排序
对于计数排序和基数排序这两种排序,其时间复杂度都为O(N),
计数排序的空间复杂度取决于数据的范围,基数排序的空间复杂度为O(N)
两者都为稳定的排序

...

golang 排序 及 列表数组去重

intList := []int{2, 4, 3, 5, 7, 6, 9, 8, 1, 0}floatList := []float64{4.2, 5.9, 12.3, 10.0, 50.4, 99.9, 31.4, 27.81828, 3.14}stringList := []string{"a", "cs", "b", "d", "f", "i", "z", "x", "w", "y"}sort.Sort(sort.IntSlice(intList))//从小到大 [0 1 2 3 4 5 6 7 8 9]sort.Sort(sort.Float64Slice(floatList))//...

文章标题:排序算法
文章链接:https://www.dianjilingqu.com/4360.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>