基础算法记录

青旅半醒 2023-06-04 02:59 10阅读 0赞

## 二分查找 ##

lst = [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
    
    def binary_search(lst,item):
        low = 0
        high = len(lst)-1
        while low <= high:
            mid = (low + high)/2
            guess = lst[mid]
            if guess == item:
                return mid
            elif guess > item:
                high = mid - 1   # 注意索引的变更
            else:
                low = mid + 1    # 注意索引的变更
        return None
    
    
    ret = binary_search(lst,17)
    if ret:
        print('Index is {}'.format(ret))
    else:
        print('Not found.')

## 选择排序 ##

raw_lst = [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
    
    # 方法一：两层for循环实现
    def sort(lst):
        for i in range(len(lst) - 1):
            # 记录最小数的索引
            minIndex = i
            for j in range(i + 1, len(lst)):
                if lst[j] < lst[minIndex]:
                    minIndex = j
            # i 不是最小数时，将 i 和最小数进行交换
            if i != minIndex:
                lst[i], lst[minIndex] = lst[minIndex], lst[i]
        return lst
    
    # 方法二：for循环+递归实现（耗时更短）
    def sort_recursion(lst):
        if 1 == len(lst):
            return lst
        min_idx = 0
        min_num = lst[min_idx]
        for i in range(1,len(lst)):
            if lst[i]<min_num:
                min_idx = i
                min_num = lst[min_idx]
        lst[min_idx] = lst[0]
        lst[0] = min_num
        tmp = sort(lst[1:])
        tmp.insert(0,lst[0])
        return tmp
    
    lst = sort(raw_lst)
    print(lst)

## 冒泡排序 ##

import time
    
    raw_lst = [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
    
    # 方法一：两层for循环实现
    def bubbleSort(lst):
        for passnum in range(len(lst)-1,0,-1):
            for i in range(passnum):
                if lst[i]>lst[i+1]:
                    tmp = lst[i]
                    lst[i] = lst[i+1]
                    lst[i+1] = tmp
        return lst
    
    # 方法二：for循环+递归实现（耗时更短）
    def bubbleSort_recursion(lst):
        length = len(lst)
        if 1==length:
            return lst
        for idx in range(length):
            if idx<length-1:
                if lst[idx]>lst[idx+1]:
                    tmp = lst[idx]
                    lst[idx] = lst[idx+1]
                    lst[idx+1] = tmp
        pre_lst = bubbleSort(lst[:-1])
        pre_lst.append(lst[-1])
        return pre_lst
    
    s1 = time.time()
    lst1 = bubbleSort(raw_lst)
    print((time.time()-s1)*1000000)    # 49.591064453125
    s2 = time.time()
    lst2 = bubbleSort(raw_lst)
    print((time.time()-s2)*1000000)    # 28.848648071289
    print(lst1)
    print(lst2)

## 插入排序 ##

## 希尔排序 ##

## 快速排序 ##

# 基于 divide&conquer 的快速排序的Python实现
     
    lst = [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
     
    def quicksort(lst):
        if len(lst) < 2:
            return lst
        pivot = lst[0]
        left = [ ele for ele in lst[1:] if ele < pivot ]
        right = [ ele for ele in lst[1:] if ele >= pivot ]
        return quicksort(left) + [pivot,] + quicksort(right)
     
    sorted_lst = quicksort(lst)
    print(lst)
    print(sorted_lst)

## 归并排序 ##

典型的分治思想：

\- 分 即 将一个大的乱序序列分成很多个不能再分割的子序列，将各个子序列分别排序。

\- 治 即 将两个相邻的已经排好序的子序列合并成一个有序序列。

整个过程是递归实现的。

import math
    
    raw_lst = [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
    
    def merge(left,right):
        '''
        归并
        '''
        lst = []
        num1 = left.pop(0)
        num2 = right.pop(0)
        while True:
            if num1 < num2:
                lst.append(num1)
                if 0 == len(left):
                    lst.append(num2)
                    for num in right:
                        lst.append(num)
                    break
                else:
                    num1 = left.pop(0)
            else:
                lst.append(num2)
                if 0 == len(right):
                    lst.append(num1)
                    for num in left:
                        lst.append(num)
                    break
                else:
                    num2 = right.pop(0)
        return lst
    
    def sort(lst):
        '''
        先拆分 在归并
        '''
        if 1==len(lst):
            return lst
        mid = math.floor(len(lst)/2)
        left = lst[:mid]
        right = lst[mid:]
        return merge(sort(left),sort(right))  # 递归
    
    lst = sort(raw_lst)
    print(lst)

归并那块写的很不Pythonic，后来看到了 [https://www.runoob.com/w3cnote/merge-sort.html][https_www.runoob.com_w3cnote_merge-sort.html]

def merge(left,right):
        '''
        归并
        '''
        lst = []
        while left and right:
            if left[0]<right[0]:
                lst.append(left.pop(0))
            else:
                lst.append(right.pop(0))
        while left:
            lst.append(left.pop(0))
        while right:
            lst.append(right.pop(0))
        return lst

归并排序在处理大文件排序问题中有很好的应用：[大文件排序/外存排序问题][Link 1]

## 堆排序 ##

参考: [https://www.cnblogs.com/chengxiao/p/6129630.html][https_www.cnblogs.com_chengxiao_p_6129630.html]

**堆的定义和基本性质**

堆是具有以下性质的完全二叉树：
        每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；
        或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。
    
    任意节点（索引为K）的父节点的索引是 (K-1)/2 。
    任意节点（索引为K）的左叶子节点的索引是 2*K+1 ,右叶子节点的索引是 2*K+2 。
    假设节点数为 N，那么最后一个非叶子节点的索引是 N/2-1 。

**堆排序的基本思想**

将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。
    
    将其与末尾元素进行交换，此时末尾就为最大值。
    
    然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。
    
    如此反复执行，便能得到一个有序序列了。

**堆排序代码实现**

class HeapSort(object):
        def __init__(self, lst):
            self._list = lst
    
        def adjust(self, parent_idx, length):
            parent_val = self._list[parent_idx]
            child_idx = parent_idx*2+1
            while child_idx < length:
                # 比较左叶子节点和右叶子节点的大小, 取较大的一个
                if child_idx+1<length and self._list[child_idx]<self._list[child_idx+1]:
                    child_idx += 1
                # 比较叶子节点和父节点的大小, 把较大值赋给父节点
                if self._list[child_idx] > parent_val:
                    self._list[parent_idx] = self._list[child_idx] # 因为可能还需要进行下一层的替换, 所以这里替换操作只做一半
                    parent_idx = child_idx
                    child_idx = child_idx*2+1
                else:
                    break
            self._list[parent_idx] = parent_val # 把当前循环的父节点的值放到最终位置
    
        def heap_build(self):
            # Step1: 构建大顶堆
            # 从最后一个非叶子节点开始调整, 从下至上 从右直左
            length = len(self._list)
            parent_idx = length//2-1
            while parent_idx >= 0:
                self.adjust(parent_idx, length)
                parent_idx -= 1
        
        def head_sort(self):
            # Step2: 堆排序
            length = len(self._list)
            for sub_length in range(length-1,-1,-1):
                # Step2.1: 交换堆顶元素与末尾元素
                tmp = self._list[0]
                self._list[0] = self._list[sub_length]
                self._list[sub_length] = tmp
                # Step2.2: 把最大值沉到列表末端, 重新调整堆结构
                # 注意: 这次调整堆结构是从堆顶开始的, 并且需要重排的列表也是随着最大值的下沉而逐渐减少, 即保证前一次得到的最大值不会参与到本次的堆调整
                self.adjust(0, sub_length)
    
    
    lst = [19, 4, 0, 7, 14, 8, 2, 12, 11, 17, 13, 3, 18, 10, 6, 1, 15, 5, 16, 9]
    obj = HeapSort(lst)
    obj.heap_build()
    obj.head_sort()

## 桶排序 ##

转载于:https://www.cnblogs.com/standby/p/9570913.html

[https_www.runoob.com_w3cnote_merge-sort.html]: https://www.runoob.com/w3cnote/merge-sort.html
[Link 1]: https://www.cnblogs.com/standby/p/9780910.html
[https_www.cnblogs.com_chengxiao_p_6129630.html]: https://www.cnblogs.com/chengxiao/p/6129630.html