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

不稳定性算法

---

前言

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

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

二、不稳定性算法

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)

---

总结

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