Java教程

排序算法

本文主要是介绍排序算法,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

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

目录
  • 1. 冒泡排序(Bubble Sort)
  • 2. 选择排序(Selection Sort)
  • 3. 插入排序(Insertion Sort)
  • 4. 希尔排序(Shell Sort)
  • 5. 快速排序(Quick Sort)
    • 5.1. 非就地排序
    • 5.2. 就地快速排序
    • 5.3. 随机化快速排序
    • 5.4. 复杂度计算
  • 6. 归并排序(Merge Sort)
  • 7. 堆排序(Heap Sort)
  • 8. 计数排序(Counting Sort)
  • 9. 桶排序(Bucket Sort)
  • 10. 基数排序(Radix Sort)


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的播放,请查看目录原始文件

这篇关于排序算法的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!