排序——数据结构与算法 总结8

目录

8.1 排序相关概念

8.2 插入排序

8.2.1 直接插入排序:

8.2.2 折半插入排序:

8.2.3 希尔排序:

8.3 交换排序

8.3.1 冒泡排序:

8.3.2 快速排序:

8.4 选择排序

8.4.1 简单选择排序

8.4.2 堆排序

8.5 归并排序

8.6 排序算法复杂度


8.1 排序相关概念

  • 排序码:排序的依据,也称关键码
  • 排序是对线性结构的一种操作
  • 排序算法的稳定性:假定在待排序的记录序列中存在多个具有相同关键码的记录,若经过排序,这些记录的相对次序保持不变,则称这种排序算法稳定,否则为不稳定。
  • 根据排序过程中所有记录是否全部放在内存中,排序方法分为

    (1) 内排序:过程中,待排序的所有记录全部放在内存中

    (2) 外排序:过程中,需要在内外存之间交换数据

  • 根据排序方法是否建立在关键码比较的基础上,排序方法分为:

    (1) 基于比较:通过关键码之间的比较和记录的移动实现。(包括插入排序、交换排序、选择排序和归并排序)

    (2) 不基于比较:根据待排序数据的特点所采取的其他方法。(基数排序)

8.2 插入排序

8.2.1 直接插入排序:

    基本思路:有将数组分为有序区和无序区,初始时有序区只有一个元素,将无序区的元素一个一个插入有序区,直到所有元素都在有序区内。

# 直接插入排序
def InsertSort(R):
    for i in range(1,len(R)):
        if R[i]<R[i-1]:
            temp = R[i]  # 取出无序区的第一个元素
            j = i-1  # 前面都是有序的,在有序区中找插入的位置
            while True:
                R[j+1] = R[j]  # 将大于temp的元素后移,空出一个插入的位置
                j-=1
                if j<0 or R[j]<=temp:
                    break
            R[j+1] = temp
    return R

8.2.2 折半插入排序:

    折半插入排序和直接插入排序思路差不多,不过在将无序区元素插入有序区时用折半的方法插入。只是优化了插入的部分。

8.2.3 希尔排序:

    基本思路:先将整个待排序记录序列分隔成若干个子序列,在子序列内分别进行直接插入排序,待整个序列基本有序后,再对整体记录进行一次直接插入排序。

    步骤:

    (1) 相邻d个位置的元素分为一组,d=n/2(d是增量)

    (2) 将排序序列分为d个组,在各组内进行直接插入排序

    (3) 递减d=d/2,重复第二步,直到d=0为止

希尔算法的时间复杂度难以分析,一般认为其平均时间复杂度为O(n1.58)。希尔排序的速度通常要比直接插入排序快。

希尔排序是一种不稳定的排序算法

8.3 交换排序

8.3.1 冒泡排序:

    基本思路:两个元素反序时进行交换

    冒小泡:从后往前看,如果后面的比前面的小就交换。

若某一趟没有出现元素交换,说明所有元素已排好序了。

# 冒泡排序
def BubbleSort(R):
    for i in range(len(R)-1):
        exchange = False
        for j in range(len(R)-1,i,-1):
            if R[j]<R[j-1]:
                R[j],R[j-1] = R[j-1],R[j]
                exchange=True
        if exchange == False:
            return R

8.3.2 快速排序:

    先选择一个基准(一般是第一个元素),将待排序记录划分为两部分,左侧关键码小于基准,右侧关键码大于基准,将基准值与左侧最后一个值交换位置,使得基准值在中间。然后分别对左右部分重复上述过程,直到排好。

【例题】

快速排序过程可以用递归树表示

#快速排序
def quickSort(lst,l,r):
    if r<=l:
        return
    q = partition(A,l,r)
    quickSort(A,l,q-1)
    quickSort(A,q+1,r)

def partition(A,l,r): #将元素进行随机划分
    p = randint(A[l],A[r])
    A[p],A[r] = A[r],A[p]
    i = l
    for j in range(l,r-1):
        if A[j]<=A[r]:
            A[i],A[j] = A[j],A[i]
            i+=1
    A[i],A[r] = A[r],A[i]
    return i

8.4 选择排序

8.4.1 简单选择排序

    分为无序区和有序区,每趟在无序区中选出最小的记录minj,minj和有序区后一个数字交换

    是一种不稳定的排序方法

# 简单选择排序
def SelectSort(R):
    for i in range(len(R)-1):
        minj = i
        for j in range(i+1,len(R)):
            if R[j]<R[minj]:  # 从无序区选最小元素
                minj = j
        if minj!=i:
            R[i],R[minj] = R[minj],R[i]

8.4.2 堆排序

    堆是完全二叉树

    堆的存储是顺序的

    堆的定义:大根堆,小根堆

    大根堆:父结点的关键字大于子结点的关键字

步骤:

(1)根据序列用广度优先构建一个完全二叉树,上滤(自底向上)调整为大根堆

(2)输出堆顶元素,然后用堆尾元素代替堆顶

(3)从根节点筛选,使其形成一个堆(此时的根节点就是之前的堆尾元素)

    筛选:将根节点与左右孩子的较大者进行交换,一直进行到所有子树均为堆或将调整结点交换到叶子位置。

(4)重复二三步骤(n-1次),得到有序序列

【例题】

8.5 归并排序

基础思路:将两个位置相邻的有序子序列归并为一个有序序列

归并要做 \left \lceil log_2n \right \rceil 趟,每趟归并时间为O(n)

#归并排序,给列表A中下标从l到r的区间排序
def mergeSort(A,l,r):
    if r-l<=1:#边界条件处理
        return
    mid = (l+r)//2
    mergeSort(A,l,mid)#递归调用
    mergeSort(A,mid,r)
    merge(A,l,mid,r)#递推到当前层

def merge(A,l,mid,r): #合并数组A[l,m-1]和A[m,r-1]
    l = A[l,mid-1]
    r = A[mid,r-1]
    k = 0
    i = 0
    j = 0
    while k<=r-l:
        if l[i]<=r[j]:
            i +=1
            A[K] = l[i]
        else:
            A[K] = r[j]
            j+=1
        k+=1

8.6 排序算法复杂度

基于比较排序算法的平均时间复杂度不可能优于O(nlog_2n)

相关推荐

  1. 数据结构算法-排序算法

    2024-07-09 22:08:02       23 阅读

最近更新

  1. docker php8.1+nginx base 镜像 dockerfile 配置

    2024-07-09 22:08:02       4 阅读
  2. Could not load dynamic library ‘cudart64_100.dll‘

    2024-07-09 22:08:02       5 阅读
  3. 在Django里面运行非项目文件

    2024-07-09 22:08:02       4 阅读
  4. Python语言-面向对象

    2024-07-09 22:08:02       4 阅读

热门阅读

  1. react中jsx的语法规则

    2024-07-09 22:08:02       8 阅读
  2. transformer的了解

    2024-07-09 22:08:02       8 阅读
  3. Pytest中的钩子函数

    2024-07-09 22:08:02       9 阅读
  4. Vue-插值表达式

    2024-07-09 22:08:02       8 阅读
  5. json数据

    2024-07-09 22:08:02       9 阅读
  6. 小型简易GIT服务器搭建和使用

    2024-07-09 22:08:02       8 阅读
  7. 开源许可(Open Source License)

    2024-07-09 22:08:02       8 阅读
  8. 使用 HAProxy 进行 MySQL 负载均衡

    2024-07-09 22:08:02       8 阅读
  9. 【Tools】了解人工通用智能 (AGI):未来的智能体

    2024-07-09 22:08:02       8 阅读