数据结构与算法_排序

稳定算法

前言

一、什么是排序和排序算法？

排序:使一串集录,按照其中的某个或某些关键字的大小递增递减.

排序算法:使记录递增递减的方法.

二、稳定性算法

 1.什么是稳定性算法?

具有相同关键字的记录经过排序后,相对位置保持不变,这样的算法算稳定性算法.

稳定性算法举例:冒泡排序、插入排序、归并排序和基数排序

1.冒泡排序

 代码演示:

def bubble_sore(alist):
    """冒泡排序"""
    #数列的长度
    n  = len(alist)
    #外层循环控制轮数
    for i in range(0,n-1):
        #计数
        count=0
        #内层循环控制比较次数(相邻位置两个元素比较次数)
        for j in range(0,n-i-1):
            比较相邻的两个数字,符合要求交换位置
            if alist[j]>alist[j+1]:
                alist[j],alist[i+1]=alist[i+1],alist[i]
                count+=1
        # 若遍历完一遍历完之后,数字没有交换,说明序列有序,退出外层循环
        if count == 0:
            break

2.插入排序

代码示例:

def insert_sort(alist):
    n = len(alist)
    # 外层循环控制轮次
    for i in range(1, n):
        # 内层循环控制 插入位置
        for j in range(i, 0, -1)
             # alist[i]为待插入的数据
             # 若待插入数据小于有序数据,则插入; 若待插入数据大于有序
             #数据,则break
            print("要插入的数 pk 要比较的数:", alist[i], alist[i - 1])
            if alist[i] < alist[i-1]:
                alist[i], alist[i-1] = alist[i-1], alist[i]
            else:
                break

总结