数据结构基础理论--冒泡排序，快速排序...代码实现

野性酷女 2021-09-18 01:44 313阅读 0赞

# 数据结构基础理论—查找与排序问题 #

#### 查找算法 ####

在一堆东西中，找到一个东西

##### 最基本写法： #####

*  从头到尾依次寻找，如果找到，就反馈，最后循环完成后，反馈失败

def find_value(data, val):
        for i,x in enumrate(data):
            if x == val:
                return i
            return -1

*  监视哨

def find_value(data, val):
        i = len(data)
        while i >= 0: 
            if data[i] == val:
                return i
            i -= 1
            return -1

时间复杂度 ： O(N)

##### 改进方案： #####

*  二分查找法  
     原数据必须有序，===》 构造一个二分查找树  
     O(logN)
 *  哈希查找法  
     x1 -----> 存储在一个物理地址，一个索引上  
     查找x1，能够构造一个函数，把x1传入后，就能得到这个索引
    
     f(x1) = index1 就把x1放到index1的位置上 存储  
     f(x2) = index2 就把x2放到index2的位置上 存储  
     查找x3  
     f(x3) = index3 通过index3去看下源空间，有没有x3
    
    > 所有的原数据，都经过一个哈希函数进行加工，加工的结果，尽量保证原数据没有重复索引,利用这个索引，把原数据放置在空间中
    
    > 当需要查找一个新的值val， 把val还是带入该哈希函数，得到一个新的索引值,利用这个索引值，看空间的值和val是否相等
    
        常用的哈希函数结构：
        1. 线性结构  y = kx+b
        2. 取整法
        3. 采样差值法
        4. 质数求模法
        10 88 44
        7 求模
        N % 7 = [0-6]
        10 % 7 = 3
        88 % 7 = 4
        44 % 7 = 2

#### 字典无序 ####

k-v  
 k 就会通过内部的哈希函数映射成一个固定的索引值  
 字典查找数据时，实际消耗的时间就跟这个哈希函数的执行时间，跟原空间大小的N没有关系

a = { }
    # 字典的key值是唯一的
    a['100'] = 'aaa'
    a['100'] = 'bbb'    # 覆盖原来的值

#### 列表有序 ####

分离的元素外置式

#### 排序算法 ####

##### 冒泡排序： #####

*  ⽐较相邻的元素。如果第⼀个⽐第⼆个⼤（升序），就交换他们两个。
 *  对每⼀对相邻元素作同样的⼯作，从第⼀对到结尾的最后⼀对。这步做完后，最后的元素会是最⼤的数。
 *  针对所有的元素重复以上的步骤，除了最后⼀个。
 *  持续每次对越来越少的元素重复上⾯的步骤，直到没有任何⼀对数字需要⽐较。

# 冒泡排序
    import random
    
    def bubble_sort(data:list):
        # 每轮减少一个
        for i in range(len(data)-1,0,-1):
            for j in range(i):
                if data[j] > data[j+1]:
                    data[j],data[j+1]= data[j+1],data[j]
                    
    def test():
        li = [random.randint(10,100) for v in range(10)]
        print('原列表',li)
        bubble_sort(li)
        print('冒泡后',li)
    
    if __name__ == "__main__":
        test()
        
    # 正常的时间复杂度： O(N^2)

##### 选择排序： #####

*  ⾸先在未排序序列中找到最⼩（⼤）元素，存放到排序序列的起始位置；
 *  然后，再从剩余未排序元素中继续寻找最⼩（⼤）元素；
 *  然后放到已排序序列的末尾。
 *  以此类推，直到所有元素均排序完毕

# 选择排序
    import random
    
    # 选择排序： 先比较记录索引，最后在交换位置
    def selection_sort(data):
        n = len(data)
        # 需要进⾏n-1次选择操作
        for i in range(n-1):
            minindex = i
            # 从i+1位置到末尾选择出最⼩数据
            for j in range(i+1,n):
                if data[j] < data[minindex]:
                    minindex = j
            # 如果选择出的数据不在正确位置，进⾏交换
            if minindex != i:
                data[i],data[minindex]=data[minindex],data[i]
    
    def test():
        li = [random.randint(10,100) for v in range(10)]
        print('原列表',li)
        selection_sort(li)
        print('选择排序后',li)
    
    if __name__ == "__main__":
        test()

##### 插入排序： #####

*  通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插  
    ⼊。
 *  插⼊排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最  
    新元素提供插⼊空间

##### 快速排序： #####

*  通过⼀趟排序将要排序的数据分割成独⽴的两部分，
 *  其中⼀部分的所有数据都⽐另外⼀部分的所有数据都要⼩，
 *  然后再按此⽅法对这两部分数据分别进⾏快速排序，
 *  整个排序过程可以递归进⾏，以此达到整个数据变成有序序列

步骤为：

*  从数列中挑出⼀个元素，称为"基准"（pivot），
 *  重新排序数列，所有元素⽐基准值⼩的摆放在基准前⾯，所有元素⽐基准值⼤的摆在基准  
    的后⾯（相同的数可以到任⼀边）。在这个分区结束之后，该基准就处于数列的中间位  
    置。这个称为分区（partition）操作。
 *  递归地（recursive）把⼩于基准值元素的⼦数列和⼤于基准值元素的⼦数列排序。

import random
    
    def quick_sort(data):
        less = []
        equal = []
        bigger = []
    
        if len(data)>1:
            # 默认选择第一个为基准
            pivot = data[0]
            for v in data:
                # 值小于基准，放入小的列表
                if pivot > v:
                    less.append(v)
                elif pivot == v:
                    equal.append(v)
                # 值小于基准，放入大的列表
                elif pivot < v:
                    bigger.append(v)
            # 递归再次快速排序
            return quick_sort(less) + equal + quick_sort(bigger)
        else:   
            return data
    
    def test():
        li = [random.randint(10,100) for v in range(10)]
        print('原列表',li)
        data = quick_sort(li)
        print('快速排序后',data)
    
    if __name__ == "__main__":
        test()

##### 归并排序 #####

*  归并排序是采⽤分治法的⼀个⾮常典型的应⽤。归并排序的思想就是先递归分解数组，再合并数  
    组。
 *  将数组分解最⼩之后，然后合并两个有序数组，基本思路是⽐较两个数组的最前⾯的数，谁⼩就先取  
    谁，取了后相应的指针就往后移⼀位。然后再⽐较，直⾄⼀个数组为空，最后把另⼀个数组的剩余部  
    分复制过来即可。

def merge_sort(alist):
        if len(alist)	<=	1:
            return alist
        # ⼆分分解
        num	=	len(alist)/2
        left	=	merge_sort(alist[:num])
        right	=	merge_sort(alist[num:])
        # 合并
        return merge(left,right)
    def merge(left,	right):
        '''合并操作，将两个有序数组left[]和right[]合并成⼀个⼤的有序数组'''
        #left与right的下标指针
        l,	r	=	0,	0
        result	=	[]
        while l<len(left)	and r<len(right):
            if left[l]	< right[r]:
                result.append(left[l])
                l	+=	1
                else:
                    result.append(right[r])
                    r	+=	1
                    result	+=	left[l:]
                    result	+=	right[r:]
                    return result
    alist	=	[54,26,93,17,77,31,44,55,20]
    sorted_alist	=	mergeSort(alist)
    print(sorted_alist)

#### 总结 ####

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1ODgwNA_size_16_color_FFFFFF_t_70]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mzk1ODgwNA_size_16_color_FFFFFF_t_70]: /images/20210726/86585ee3981441bfb1ea4a84bb98e5ea.png