数据结构与算法_排序_不稳定性算法

发布时间:2024年01月21日

不稳定性算法

目录

前言

一、什么是不稳定性算法?

二、不稳定性算法

1.选择排序

2.快排插入

总结



前言

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

一、什么是不稳定性算法?

具有相同关键字的纪录经过排序后, 相对位置发生改变, 这样的算法是不稳定性算法

二、不稳定性算法

1.选择排序

选择排序的工作原理:
第一次从 待排序的数据元素 中选出最小(或最大)的一个元素,存放在 序列的起始位置
然后再从剩余的 未排序元素 中寻找到最小(大)元素,然后放到已排序的序列的末尾. 以
此类推,直到 全部待排序的数据元素 的个数为零

# 定义函数实现插入排序
def insert_sort(my_list):
    n = len(my_list)   #获得长度
    for i in range(1,n): #从一开始 有一个有序数列表
        for j in range(i,0,-1):  #倒着比较
            if my_list[j]< my_list[j-1]:
                my_list[j-1],my_list[j] = my_list[j],my_list[j-1]   #无序的列表大于有序的就交换
            else:  # 会增加效率
                break

2.快排插入

基本思想:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都
要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以 递归 进行,以此达到整个数据变成有序
序列

?

?

?代码示例:

def quickly_sort(my_list,start,end):
    # 递归出口
    if start >= end:
        return
    # 定义分界值
    mid = my_list[start]
    left = start
    right = end
    # 通过循环,获取到列表的每个数据
    while left < right:
        # 将大于等于分界值的 放到右边    
        while my_list[right] >= mid and left < right:
            right -= 1
        my_list[left]= my_list[right]
        # 将小于等于分界值的放到左边
        while my_list[left] < mid and left < right:
            left += 1
        my_list[right] = my_list[left]

    my_list[left] = mid
    quickly_sort(my_list,start,left-1)
    quickly_sort(my_list,right+1,end)


总结

算法思想的本身是独立于编程语言的,所以你写代码去实现算法的时候很多细节可以做不同的处理.采用不稳定算法不管你具体实现时怎么写代码,最终相同元素位置总是不确定的 (可能位置没变也可能变了).

文章来源:https://blog.csdn.net/m0_66672931/article/details/135646401
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。