排序算法(2)

简介: 排序算法(2)

概要

接上回

在上篇说过经典的排序算法,有冒泡,插入,选择;归并,快排。其中讲了冒泡,插入,选择;这一回写归并和快排。

原理及实现

原理是很好玩的,如果不喜欢,先记住,总有一天会用得上的。

原理挺有意思的,喜欢就去研究,不喜欢就记住一些常用的,以备不时之需。先聊聊归并吧。

归并排序

本来想找个定义,看了下维基百科,也不是很满意的概念,如下:

定义

归并排序(英语:Merge sort,或mergesort),是建立在归并操作上的一种有效的排序算法,效率为𝑂(𝑛log𝑛)(大O符号)。1945年由约翰·冯·诺伊曼首次提出。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用,且各层分治递归可以同时进行。

定义是这样的,怎么理解呢?采用分治递归,意思就是先平均分成2份,然后比较排序;递归这种操作,就是将2份中任何一份继续采用分治法(分治法这里不细聊,以后会写文章的),分成2份,直到不能再分为止;

性能

  1. 归并排序是稳定的排序算法;数组长度就那么长,一直在分割,然后继续分割直到不能再分,然后采用合并数组;
  2. 时间复杂度:O(nlogn)
  3. 空间复杂度:O(nlogn)

代码Python

dfrom typing import List
def merge_sort(a: List[int]):
    merge_sort_between(a, 0, len(a) - 1)
def merge_sort_between(a: List[int], low: int, high: int):
    # The indices are inclusive for both low and high.
    if low < high:
        mid = low + (high - low) // 2
        merge_sort_between(a, low, mid)
        merge_sort_between(a, mid + 1, high)
        merge(a, low, mid, high)
def merge(a: List[int], low: int, mid: int, high: int):
    # a[low:mid], a[mid+1, high] are sorted.
    i, j = low, mid + 1
    tmp = []
    while i <= mid and j <= high:
        if a[i] <= a[j]:
            tmp.append(a[i])
            i += 1
        else:
            tmp.append(a[j])
            j += 1
    start = i if i <= mid else j
    end = mid if i <= mid else high
    tmp.extend(a[start:end + 1])
    a[low:high + 1] = tmp

快速排序

归并说完了,来看看快排。定义如下:

定义

快速排序(英语:Quicksort),又称分区交换排序(partition-exchange sort),是一种排序算法,最早由东尼·霍尔提出。在平均状况下,排序𝑛个项目要𝑂(𝑛log𝑛)(大O符号)次比较。在最坏状况下则需要𝑂(n 2 n^2n2)次比较,但这种状况并不常见。事实上,快速排序Θ(𝑛log𝑛)通常明显比其他算法更快,因为它的内部循环可以在大部分的架构上很有效率地达成。

按照定义,对一定长度的数据,选一个基准值,然后所有数据一个一个跟基准值比较,然后交互i,j的位置。还是分治和递归的思想,一直这么分,partion。

接下来看看代码,如下:

代码

from typing import List
import random
def quick_sort(a: List[int]):
    quick_sort_between(a, 0, len(a) - 1)
def quick_sort_between(a: List[int], low: int, high: int):
    if low < high:
        # get a random position as the pivot
        k = random.randint(low, high)
        a[low], a[k] = a[k], a[low]
        m = partition(a, low, high)  # a[m] is in final position
        quick_sort_between(a, low, m - 1)
        quick_sort_between(a, m + 1, high)
def partition(a: List[int], low: int, high: int):
    pivot, j = a[low], low
    for i in range(low + 1, high + 1):
        if a[i] <= pivot:
            j += 1
            a[j], a[i] = a[i], a[j]  # swap
    a[low], a[j] = a[j], a[low]
    return j

小结

学习总结

归并,排序都采用了分治的思想。时间复杂度归并O(nlogn),空间复杂度归并的比较大,达到O(n);快排时间复杂度O(nlogn),快排极端情况达到O(n 2 n^2n2),但是概率很小,而且可以通过合理的选用基准值来避免,适用范围较广。

相关文章
|
Java 物联网 Linux
在Linux上明明用rpm成功安装了软件,在卸载时却提示未安装
在Linux上明明用rpm成功安装了软件,在卸载时却提示未安装
1331 0
|
7月前
|
移动开发 小程序
【02】支付宝支付商户申请下户到配置完整流程-申请签约产品-添加应用审核-设定经营类目-填写网站备案信息-申请+配置完整流程-优雅草卓伊凡
【02】支付宝支付商户申请下户到配置完整流程-申请签约产品-添加应用审核-设定经营类目-填写网站备案信息-申请+配置完整流程-优雅草卓伊凡
217 0
【02】支付宝支付商户申请下户到配置完整流程-申请签约产品-添加应用审核-设定经营类目-填写网站备案信息-申请+配置完整流程-优雅草卓伊凡
|
8月前
|
Devops 网络安全 CDN
微软警告:Azure CDN将关闭,需尽快迁移以避免服务中断
微软警告:Azure CDN将关闭,需尽快迁移以避免服务中断
|
7月前
|
弹性计算 运维 负载均衡
课时3:阿里云专有网络VPC:让网络更加独立
阿里云专有网络VPC提供独立、安全的云上网络环境,支持自定义IP地址网段和灵活的路由配置。通过高速通道实现优质网络链路,可用性达99.95%,满足企业高要求的数据传输需求。VPC结合弹性公网IP、负载均衡SLB、Net网关等功能,帮助企业轻松管理网络资源,降低运维成本,实现高效、安全的混合云架构部署。
164 0
|
11月前
|
安全 Linux Shell
用户和组高级操作
本文介绍了Linux系统中用户和组管理的基本操作,包括使用`usermod`命令修改用户属性、使用`passwd`和`usermod`命令禁用和恢复用户账户、使用`userdel`命令删除用户账户、使用`groupadd`、`groupdel`和`groupmod`命令管理组群,以及使用`gpasswd`命令为组群添加用户。此外,还介绍了`su`和`sudo`命令的使用方法,帮助用户在不同身份之间切换。
166 4
|
存储 关系型数据库 MySQL
|
消息中间件 监控 Kafka
实时计算 Flink版产品使用问题之处理Kafka数据顺序时,怎么确保事件的顺序性
实时计算Flink版作为一种强大的流处理和批处理统一的计算框架,广泛应用于各种需要实时数据处理和分析的场景。实时计算Flink版通常结合SQL接口、DataStream API、以及与上下游数据源和存储系统的丰富连接器,提供了一套全面的解决方案,以应对各种实时计算需求。其低延迟、高吞吐、容错性强的特点,使其成为众多企业和组织实时数据处理首选的技术平台。以下是实时计算Flink版的一些典型使用合集。
|
存储 缓存 负载均衡
基于C++的高性能分布式缓存系统设计
基于C++的高性能分布式缓存系统设计
426 1
|
存储 Ubuntu 机器人
机械臂手眼标定详解
这篇文章是关于机械臂手眼标定的详细教程,包括了使用ROS1 Noetic和Realsense D415相机在Ubuntu 20.04环境下进行标定的步骤和配置方法。
1335 0
机械臂手眼标定详解
|
移动开发 小程序 前端开发
【经验分享】如何实现在支付宝小程序内的骨架屏效果
【经验分享】如何实现在支付宝小程序内的骨架屏效果
266 7