大话数据结构第九章—排序

大话数据结构第九章—排序马上要把大话数据结构这本书看完啦,现在已经对数据结构有了一种系统上的了解,后面的事情就疯狂练习力扣上的编程题目啦,第九章是本书的最后一章,却是以前我学数据结构最先学的部分—–排序。排序网页搜索之后的排序,商品页面的排序,是如何做到的呢?本章将介绍7种排序算法:冒泡排序,简单选择排序,直接插入排序属于简单算法。快速排序,归并排序(mergesort),希尔排序,堆排序属于…

大家好,又见面了,我是你们的朋友全栈君。

马上要把大话数据结构这本书看完啦,现在已经对数据结构有了一种系统上的了解,后面的事情就疯狂练习力扣上的编程题目啦,第九章是本书的最后一章,却是以前我学数据结构最先学的部分—–排序。

排序

网页搜索之后的排序,商品页面的排序,是如何做到的呢?

本章将介绍7种排序算法:

冒泡排序,简单选择排序,直接插入排序属于简单算法。

快速排序,归并排序(merge sort),希尔排序,堆排序属于改进算法。

本文中都是升序排序哦~

 

1.冒泡排序

#bubble sorted
def bubble(array):
    if array == None or len(array) == 0:
        return -1
    for i in range(len(array)-1):
        for j in range(len(array)-1):
            if array[j] > array[j+1]:
                array[j],array[j+1] = array[j+1],array[j]
    return array

时间复杂度:o(n^2)

空间复杂度:o(1)

2.简单选择排序

选择一个数作为最小数,(比如选第一个数作为min),在后续数组中找到最小的数字,并交换位置。若没有,跳到第二个数字,继续进行比较。

代码如下:

 

#selection sort
def select(array):
    if array == None or len(array) == 0:
        return -1
    for i in range(len(array)-1):
        min_index = i
        for j in range(i,len(array)):
            if array[min_index] > array[j]:
                array[min_index],array[j] = array[j],array[min_index]
    return array

 

时间复杂度:o(n^2)

 

空间复杂度:o(1)

3.直接插入排序

插入排序Insertion Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。

所以insert需要的时间复杂度是o(n),排序(找插入空位)的时间复杂度是o(n),当然如果用binary search找空位的时间复杂度是o(logn),总体的时间复杂度为o(n^2)或者是o(nlogn)。

代码如下:

def insert(list_a):
    for i in range(1,len(list_a)):
        cur = list_a[i]
        k = i

        while cur < list_a[k-1] and k > 0:#寻找空位
           list_a[k] = list_a[k-1]
           k -= 1                        #k记录的当前空位的位置

        list_a[k] = cur#插入

    return list_a

插入排序由于需要挪动空位后的元素,所以需要游标(存储现在正在进行插入的数据元素),需要记录元素下标。寻找插入空位这个代码得记住,感觉可以用在其他地方。

前三种方法都是简单的排序算法,比较他们的最坏的时间复杂度(序列初始为逆序),直接插入算法性能比冒泡和简单选择排序的性能要好。

4 堆排序(heap)

堆是具有下列性质的完全二叉树:

每个节点的值都大于或等于其左右孩子节点的值,叫大顶堆;

每个节点的值都小于或等于其左右孩子节点的值,称为小顶堆。

堆排序算法的步骤:

以大顶堆为例

1 将待排序的序列构成大顶堆。

2 此时最大值就是堆顶的根节点,将其移走(其实是将其与堆数组的末尾元素交换,此时末尾元素就是最大值)

3 将剩余的n-1个序列重新构造成一个堆,这样就可以得到从小到大的排序的有序序列。

要解决的关键问题就是如何建立堆!

建立堆(以实现小顶堆为例)

如何用数组来表示一个完全二叉树?

完全二叉树孩子节点和父亲节点的数组索引关系是酱紫的:

left_node = parent_node * 2 + 1

right_node = parent_node * 2 + 2

parent_node = (child_node – 1) // 2

所以需要实现让完全二叉树的每个节点都小于孩子节点才能建立小顶堆。

将一个随机数组变成小顶堆的python代码如下:

def min_heap(array,i):
    left = i*2+1
    right = i*2+2
    smaller = i
    if left < len(array) and array[left] < array[smaller]:
        smaller = left
    if right < len(array) and array[right] < array[smaller]:
        smaller = right
    if smaller != i:
        array[smaller],array[i] = array[i],array[smaller]
        min_heap(array,smaller)

def build_heap(arr):
    for i in range(len(arr)//2,-1,-1):
        min_heap(arr,i)
    return arr

时间复杂度o(nlogn)。

如果你要往已经生成的小顶堆中加入数据元素:

def push(array,i):
#这里的i是输入序列的最后一位的索引值,也是你要插入的数据。
    parent = (i-1)//2
    large = i
    if parent >= 0 and array[parent] > array[i]:
        large = parent
    if large != i:
        array[large],array[i]= array[i],array[large]
        push(array,large)

时间复杂度都是o(logn)。

python中heapq包,专门完成堆的一些操作。

import heapq

heap = []                  #生成的是小顶堆

heappush(heap,item)

item = heappop(heap)

item = heap[0]

heapify(x) #将list转换为heap

item = heapreplace(heap,item) #先pop再插入item

有了这些可以应用它做一些编程题目:

比如实现堆排序,寻找序列中的最小k项,合并k个有序序列等。

5 归并排序

先分割序列,再将分割后的序列进行合并

def merge(a,b):
    c = []
    index_a,index_b = 0,0
    while index_a < len(a) and index_b < len(b):
        if a[index_a] > b[index_b]:
            c.append(b[index_b])
            index_b += 1
        elif a[index_a] <= b[index_b]:
            c.append(a[index_a])
            index_a += 1

    if index_a < len(a):
        c.extend(a[index_a:])
    if index_b < len(b):
        c.extend(b[index_b:])

    return c

def merge_sort(list_a):

    if len(list_a) == 0 or len(list_a) == 1:
        return list_a

    mid = len(list_a)//2
    a = merge_sort(list_a[:mid])
    b = merge_sort(list_a[mid:])

    return merge(a,b)

时间复杂度:o(nlogn)

6 快速排序

通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序的目的。这是不稳定的算法,因为时间复杂度最坏o(n^2),最好和平均情况是o(nlogn)。

def paixu(a,b):
    c = a+b
    p = (len(a)+len(b))//2
    end = len(a)+len(b)-1
    for start in range(p):
        for i in range(p, end + 1):
            if c[start] >= c[i] and start <= len(a) - 1:
                c[start], c[i] = c[i], c[start]
    return c


def q_paixu(a):
    if len(a) <= 1:
        return a
    else:
        p = len(a)//2
        j = q_paixu(a[0:p])
        b = q_paixu(a[p:len(a)])

    return paixu(j,b)

7 希尔排序

它就是直接插入排序的进阶、这个网址解释的很清楚。

https://blog.csdn.net/u014745194/article/details/72783357

关于这七个排序算法的稳定性和时间复杂度:

https://www.cnblogs.com/nannanITeye/archive/2013/04/11/3013737.html

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法,

冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

首先,排序算法的稳定性大家应该都知道,通俗地讲就是能保证排序前两个相等的数据其在序列中的先后位置顺序与排序后它们两个先后位置顺序相同。再简单具体一点,如果A i == A j,Ai 原来在 Aj 位置前,排序后 Ai  仍然是在 Aj 位置前。 

 

插入排序:第n趟前n+1个有序

选择排序:第n趟前n个位置正确

快速排序:第n趟有n个元素位置正确

堆排序:第n趟前或后n个位置正确

 

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/152568.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • CANalyzer_InstallationQuickStartGuide[通俗易懂]

    CANalyzer_InstallationQuickStartGuide[通俗易懂]OverviewOperatingconceptIfyouarestartingupCANalyzerforthefirsttime,anditsfunctionalityandcontrolsarestillcompletelynewtoyou,thefollowingtourwillhelpyoutobecomefamiliar…

  • ER图转关系模型_实体关系图变关系模型

    ER图转关系模型_实体关系图变关系模型(1)实体类型的转换将每个实体类型转换成一个关系模式,实体的属性即为关系的属性,实体标识符即为关系的键。(2)联系类型的转换实体间的关系是1对1在实体类型转换成两个关系模式中的任意一个关系模式的属性中加入另一个关系模式的键和联系类型的属性。实体间的联系是1对N则在N端实体类型转换成的关系模式中加入1端实体类主键。如实体间的联系是M对N单独将联系类型也转换成关系模式。将M和N端的主键都加进去。示例:该ER图转换为关系模型商店和职工是一对多关系,一个商店有多个

  • 现场校时错乱分析,开启NTP校时延迟分析以及部署建议「建议收藏」

    现场校时错乱分析,开启NTP校时延迟分析以及部署建议「建议收藏」1.问题背景描述2021年7月23日宜春现场出现一台信号机在应该跑早高峰方案的时候,实际上跑了凌晨的方案,从而造成现场车辆拥堵的问题,客户进行了投诉并要求给出解释和解决方案。2.问题排查和分析排查过程中发现宜春现场的校时配置十分混乱。现场存在NTP,GPS,平台校时三种模式同时进行校时的情况。并且现场并不止有一个平台,也就是通过平台校时这个方式的校时源有多种。所以可以得知的是,现场的信号机在较多情况下同时会接受3-5种不同的校时源进行校时。3.同时有多种不同校时源下存在的风险信号机是一个时

  • QFile和QTextStream

    QFile和QTextStreamQFile类是一个操作文件的输入/输出设备。详情请见……#include&lt;qfile.h&gt;继承了QIODevice。所有成员函数的列表。公有成员QFile()QFile(const QString &amp; name)~QFile()QStringname()constvoidsetName(const QString &amp; name)typedef…

  • MiFlash提示“错误代码”为“0xffffffff”[通俗易懂]

    MiFlash提示“错误代码”为“0xffffffff”[通俗易懂]当MiFlash提示“未指定的错误”时,我们可以根据其后的错误代码来寻求问题的解决方法。当MiFlash提示“错误代码”为“0xffffff01”时,表明“MiFlash找不到指定的文件”。对此我们可以通过以下方法来解决:右击“计算机”图标,从弹出的右键菜单中选择“属性”项。从打开的“系统属性”窗口中,点击左上角的“高级系统设置”按钮进入详细设置界面。待打开“系统属性”窗口后,切换到“高级”选项卡,点击“环境变量”按钮打开其设置对话框。从打开的“环境变量”窗口中,从“系统变量”列表中找到“Path

  • 开源运维工具

    开源运维工具 https://github.com/guohongze/adminset自动化运维平台:CMDB、CD、DevOps、资产管理、任务编排、持续交付、系统监控、运维管理、配置管理技术:centos7.2(1511)django1.11.9python2.7  https://github.com/welliamca…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号