数据结构与算法-排序算法

  • 开发
  • 16

1.顺序查找

def linear_search(iters, val):
    for i, v in enumerate(iters):
        if v == val:
            return i
    return

2.二分查找

# 升序的二分查找
def binary_search(iters, val):
    left = 0
    right = len(iters)-1
    while left <= right:
        mid = (left + right) // 2
        if iters[mid] == val:
            return mid
        elif iters[mid] > val:
            right = mid - 1
        else:
            left = mid + 1
    else:
        return
lis = [1, 2, 3, 4]
print(binary_search(lis, 2))



# 降序的二分查找
def binary_search(iters, val):
    left = 0
    right = len(iters)-1
    while left <= right:
        mid = (left + right) // 2
        if iters[mid] == val:
            return mid
        elif iters[mid] > val:
            left = mid + 1
        else:
            right = mid - 1
    else:
        return
lis = [4, 3, 2, 1]
print(binary_search(lis, 2))

3.冒泡排序

# 升序冒泡排序
def bubble_sort(li):
    for i in range(len(li)-1): #第i趟
        exchange = False # 判断第i趟是否进行了交换
        for j in range(len(li)-1-i):
            if li[j] > li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                exchange = True
        print(li)
        if not exchange:
            return
li = [1, 4, 2, 9, 0]
bubble_sort(li)

print("===========================================")

# 降序冒泡排序
def bubble_sort(li):
    for i in range(len(li)-1): #第i趟
        exchange = False # 判断第i趟是否进行了交换
        for j in range(len(li)-1-i):
            if li[j] < li[j+1]:
                li[j], li[j+1] = li[j+1], li[j]
                exchange = True
        print(li)
        if not exchange:
            return
li = [1, 4, 2, 9, 0]
bubble_sort(li)

4.选择排序

# 升序选择排序: 非原地排序(新增一个变量存储排序后的结果)
def select_sort_sample1(li):
    li_new = []
    for i in  range(len(li)):
        min_val = min(li)
        li_new.append(min_val)
        li.remove(min_val)
    return li_new
li = [3, 1, 4, 7, 4, 8]
print(select_sort_sample1(li))

print("================================================")

# 降序选择排序: 非原地排序(新增一个变量存储排序后的结果)
def select_sort_sample2(li):
    new_li = []
    for i in range(len(li)):
        max_val = max(li)
        new_li.append(max_val)
        li.remove(max_val)
    return new_li
li = [3, 1, 4, 7, 4, 8]
print(select_sort_sample2(li))

print("=================================================")

# 升序选择排序: 原地排序
def select_sort1(li):
    for i in range(len(li)-1):
        min_loc = i
        for j in range(i+1, len(li)):
            if li[j] < li[min_loc]:
                min_loc = j
        li[i], li[min_loc] = li[min_loc], li[i]
        print(li)
li = [1, 4, 2, 8, 5]
select_sort1(li)

print("==================================================")

# 降序选择排序: 原地排序
def select_sort2(li):
    for i in range(len(li)-1):
        max_loc = i
        for j in range(i+1, len(li)):
            if li[j] > li[max_loc]:
                max_loc = j
        li[i], li[max_loc] = li[max_loc], li[i]
        print(li)
li = [1, 4, 2, 8, 5]
select_sort2(li)

5.插入排序

# 升序插入排序
def insert_sort1(li):
    for i in range(1, len(li)): #i表示摸到的牌的下标
        tmp = li[i] #存放待插入的牌
        j = i - 1 #j表示手里的牌的下标
        while j >= 0 and li[j] > tmp:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp
        print(li)
li = [1, 4, 2, 8, 5]
insert_sort1(li)

print("=======================================")

# 降序插入排序
def insert_sort2(li):
    for i in range(1, len(li)):
        tmp = li[i]
        j = i - 1
        while j >= 0 and li[j] < tmp:
            li[j+1] = li[j]
            j -= 1
        li[j+1] = tmp
        print(li)
li = [1, 4, 2, 8, 5]
insert_sort2(li)

6.快速排序

# 升序快速排序
def partition1(li, left, right):
    tmp = li[left] #存放待归位的值
    while left < right:
        while left < right and li[right] >= tmp: #从右面找比tmp小的元素
            right -= 1 #往左走一步
        li[left] = li[right] #把右边的值写到左边
        while left < right and li[left] <= tmp: #从左面找比tmp大的元素
            left += 1 #往右走一步
        li[right] = li[left] #把左边的值写到右边
    li[left] = tmp
    return left

def quick_sort1(li, left, right):
    if left < right: #至少两个元素
        mid = partition1(li, left, right)
        quick_sort1(li, left, mid-1)
        quick_sort1(li, mid+1, right)

li = [4, 3, 5, 5, 8, 7]
quick_sort1(li, 0, len(li)-1)
print(li)

print("======================================================")

# 降序快速排序
def partition2(li, left, right):
    tmp = li[left]
    while left < right:
        while left < right and li[right] <= tmp:
            right -= 1
        li[left] = li[right]
        while left < right and li[left] >= tmp:
            left += 1
        li[right] = li[left]
    li[left] = tmp
    return left

def quick_sort2(li, left, right):
    if left < right:
        mid = partition2(li, left, right)
        quick_sort2(li, left, mid-1)
        quick_sort2(li, mid+1, right)

li = [4, 3, 5, 5, 8, 7]
quick_sort2(li, 0, len(li)-1)
print(li)

7.堆排序

# 升序堆排序
def shift(li, low, high):
    # 建大根堆
    """
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个元素位置
    :return:
    """
    i = low #i最开始指向根节点
    j = 2 * i + 1 #j开始是左孩子
    tmp = li[low] #把堆顶存起来
    while j <= high: # j位置有效
        if j + 1 <= high and li[j+1] > li[j]: #如果右孩子有且比较大
            j = j + 1 #j指向右孩子
        if li[j] > tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            li[i] = tmp
            break
    else:
        li[i] = tmp # 把tmp放到叶子节点上

def heap_sort(li):
    n = len(li)
    for i in range((n-2)//2, -1, -1):
        # (n - 2) // 2表示最后一个有孩子节点的节点的下标
        # i表示建堆的时候要进行调整的二叉树的根的下标
        shift(li, i, n-1)
    # 建堆完成
    print("大根堆:{}".format(li))
    for i in range(n-1, -1, -1):
        # i指向当前堆的最后一个元素
        li[0], li[i] = li[i], li[0]
        shift(li, 0, i-1) # i-1是最新的high
import random
li = [i for i in range(10)]
random.shuffle(li)
print("初始列表:{}".format(li))
heap_sort(li)
print("排序列表:{}".format(li))

print("============================================")

# 降序堆排序
def shift1(li, low, high):
    # 建小根堆
    """
    :param li: 列表
    :param low: 堆的根节点位置
    :param high: 堆的最后一个节点的位置
    :return:
    """
    i = low # 最开始指向根节点
    j = 2 * i + 1 # 左孩子节点
    tmp = li[low]
    while j <= high:
        if j + 1 <= high and li[j + 1] < li[j]:
            j = j + 1
        if li[j] < tmp:
            li[i] = li[j]
            i = j
            j = 2 * i + 1
        else:
            li[i] = tmp
            break
    else:
        li[i] = tmp

def heap_sort1(li):
    n = len(li)
    for i in range((n-2)//2, -1, -1):
        shift1(li, i, n-1)
    print("小根堆:{}".format(li))
    # 建堆完成
    for i in range(n-1, -1, -1):
        li[0], li[i] = li[i], li[0]
        shift1(li, 0, i - 1)
import random
li = [i for i in range(10)]
random.shuffle(li)
print("初始列表:{}".format(li))
heap_sort1(li)
print("排序列表:{}".format(li))

8.归并排序

# 升序归并排序
def merge(li, low, mid, high):
    # 对两个有序列表进行合并
    """
    :param li: 列表
    :param low:
    :param mid:
    :param high:
    :return:
    """
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high: #只要两边都有数
        if li[i] < li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high+1] = ltmp

def merge_sort(li, low, high):
    if low < high: # 至少有两个元素
        mid = (low + high) // 2
        merge_sort(li, low, mid)
        merge_sort(li, mid + 1, high)
        merge(li, low, mid, high)

import random
li = [i for i in range(10)]
random.shuffle(li)
merge_sort(li, 0, len(li) - 1)
print(li)

print("================================================")

# 降序归并排序
def merge1(li, low, mid, high):
    # 对两个有序列表进行合并
    """
    :param li: 列表
    :param low:
    :param mid:
    :param high:
    :return:
    """
    i = low
    j = mid + 1
    ltmp = []
    while i <= mid and j <= high: #只要两边都有数
        if li[i] > li[j]:
            ltmp.append(li[i])
            i += 1
        else:
            ltmp.append(li[j])
            j += 1
    while i <= mid:
        ltmp.append(li[i])
        i += 1
    while j <= high:
        ltmp.append(li[j])
        j += 1
    li[low:high+1] = ltmp

def merge_sort1(li, low, high):
    if low < high: # 至少有两个元素
        mid = (low + high) // 2
        merge_sort1(li, low, mid)
        merge_sort1(li, mid + 1, high)
        merge1(li, low, mid, high)

import random
li = [i for i in range(10)]
random.shuffle(li)
merge_sort1(li, 0, len(li) - 1)
print(li)

9.希尔排序

# 升序希尔排序
def insert_sort_gap(li, gap):
    for i in range(gap, len(li)): #i表示摸到的牌的下标
        tmp = li[i] #存放待插入的牌
        j = i - gap #j表示手里的牌的下标
        while j >= 0 and li[j] > tmp:
            li[j + gap] = li[j]
            j -= gap
        li[j+gap] = tmp

def shell_sort(li):
    d = len(li) // 2
    while d >= 1:
        insert_sort_gap(li, d)
        d //= 2

li = [1, 4, 2, 8, 5]
shell_sort(li)
print(li)

10.计数排序

# 升序计数排序
# 限制: 数值有确定的范围
def count_sort(li, max_count=100):
    count = [0 for _ in range(max_count+1)]
    for val in li:
        count[val] += 1
    li.clear()
    for ind, val in enumerate(count):
        for i in range(val):
            li.append(ind)
import random
li = [random.randint(0, 100) for i in range(1000)]
count_sort(li)
print(li)

11.桶排序

# 升序桶排序
def bucket_sort(li, n=100, max_num=10000):
    buckets = [[] for i in range(n)]  # 创建桶
    for var in li:
        i = min(var // (max_num // n), n - 1)  # i表示var放到第几个桶里
        buckets[i].append(var)  # 把var放桶里
        for j in range(len(buckets[i]) - 1, 0, -1):
            if buckets[i][j] < buckets[i][j - 1]:
                buckets[i][j], buckets[i][j - 1] = buckets[i][j - 1], buckets[i][j]
            else:
                break
    sorted_li = []
    for buc in buckets:
        sorted_li.extend(buc)
    return sorted_li

import random
li = [random.randint(0, 10000) for i in range(100)]
print(bucket_sort(li))

12.基数排序

def redix_sort(li):
    """
    :param li: 列表
    :return:
    限制于正整数的基数排序
    """
    max_num = max(li)
    it = 0  # 0 -> 按个位分桶  1 -> 按十位分桶 2 -> 按百位分桶...
    while 10 ** it <= max_num:
        buckets = [[] for _ in range(10)]
        for var in li:
            digit = (var // 10 ** it) % 10  # it->0 取个位; it->1 取十位; it->2 取百位...(若该数位上没有数字, 取零)
            buckets[digit].append(var)
        # 分桶完成
        li.clear()
        for buc in buckets:
            li.extend(buc)
        # 把数重新写回li
        it += 1

import random
li = [random.randint(0, 10000) for i in range(100)]
redix_sort(li)
print(li)

阅读全部

相关推荐

  3. 数据结构与算法-排序算法

    2024-03-26 08:48:16       17 阅读

最近更新

  4. TCP协议是安全的吗?

    2024-03-26 08:48:16       18 阅读

  12. 阿里云服务器执行yum，一直下载docker-ce-stable失败

    2024-03-26 08:48:16       19 阅读

  13. 【Python教程】压缩PDF文件大小

    2024-03-26 08:48:16       18 阅读

  18. 通过文章id递归查询所有评论（xml）

    2024-03-26 08:48:16       20 阅读

热门阅读

  6. MD5加密

    MD5加密

    2024-03-26 08:48:16      18 阅读

  8. 【ES6】Set和Map数据结构

    2024-03-26 08:48:16       16 阅读

  11. SQL语言: 内外连接

    2024-03-26 08:48:16       14 阅读

  18. vue json字符串和Hex互转

    2024-03-26 08:48:16       14 阅读

  21. 蓝桥杯 付账问题

    2024-03-26 08:48:16       17 阅读

  28. 制作一个简单的HTML个人网页

    2024-03-26 08:48:16       17 阅读

  30. 贪心算法的习题答案

    2024-03-26 08:48:16       13 阅读