Python数据结构与算法-常见的九种排序算法以及二分查找法

墨蓝 2022-05-14 10:18 155阅读 0赞

**目录**

1、冒泡排序法

2、选择排序法

3、插入排序法

4、快速排序法

5、希尔排序法

6、归并排序法

7、堆排序法

8、桶排序

9、基数排序

常见的算法效率比较：

八、二分查找法：

--------------------

### 1、冒泡排序法 ###

冒泡排序算法的运作如下：

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

![70][]

#1.冒泡排序
    li = [1, 45, 23, 56, 11, 24, 11, 89, 47, 12]
    #方法1
    def buble_sort1(alist):
        n = len(alist)
        for i in range(n-1):
            for j in range(n-1-i):
                if alist[j] > alist[j+1]:
                    alist[j], alist[j+1] = alist[j+1], alist[j]
        return alist
    print(buble_sort1(li))  # [1, 11, 11, 12, 23, 24, 45, 47, 56, 89]
    
    #方法2
    def buble_sort2(alist):
        n = len(alist)
        for i in range(n-1, 0, -1):
            for j in range(i):
                if alist[j] > alist[j+1]:
                    alist[j], alist[j+1] = alist[j+1], alist[j]
        return alist 
    print(buble_sort2(li))
    
    #方法3:从后面的数往前进行冒泡
    def buble_sort3(alist):
        n = len(alist)
        for i in range(n-1):
            for j in range(n-1, i, -1):
                if alist[j] < alist[j-1]:
                    alist[j-1], alist[j] = alist[j], alist[j]
        return alist 
    print(buble_sort3(li))

### 2、选择排序法 ###

![70 1][]

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

![70 2][]![70 3][]

#2选择排序法
    def selection_sort1(alist): #将最小的数方在前面
        n = len(alist)
        for i in range(n-1):    #需要进行 n-1次的操作
            min_index = i 
            for j in range(i+1, n): #从 i+1 开始遍历， 前面几项是已经排序好的
                if alist[j] < alist[min_index]: #找出最小的数据
                    min_index = j 
            if min_index != i:  #将数据进行交换
                alist[i], alist[min_index] = alist[min_index], alist[i]
        return alist
    print(selection_sort1(li))   # [1, 11, 11, 12, 23, 24, 45, 47, 56, 89]
    
    def selection_sort2(alist): #将最大的数放在后面
        n = len(alist)
        for i in range(n-1, 0, -1):
            max_index = i
            for j in range(i-1, 0, -1):
                if alist[j] > alist[max_index]:
                    max_index = j 
            if max_index != i:
                alist[i], alist[max_index] = alist[max_index], alist[i]
        return alist
    print(selection_sort2(li))

### 3、插入排序法 ###

插入排序（英语：Insertion Sort）是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

![70 4][]

#3.插入排序
    def insert_sort(alist):
        n = len(alist)
        for i in range(1, n):   #将列表的第一个元素，即下标为0的元素设为有序的，从第二个元素开始比较
            for j in range(i, 0, -1):   #将下标为 i 的元素与前面几项相比
                if alist[j] < alist[j-1]:
                    alist[j], alist[j-1] = alist[j-1], alist[j]
        return alist
    print(insert_sort(li))

### 4、快速排序法 ###

![70 5][]

#4.快速排序
    #将一个数组分为2 个数组， 在通过递归调用自身函数为每一个子数组进行排序
    def quick_sort(alist, start, end):
        if start >= end:
            return  #递归的退出条件，直接退出函数
        low = start # 由左向右移动
        high = end 
        mid = alist[low]    #设置第一个元素为基准元素， 小于它的再左边，大于它的在右边
        
        while high > low:
            while high > low and alist[high] >= mid:    #需要有个等号最后判断条件停止，使得其光标往左移动 
                high -= 1
            alist[low] = alist[high]
            
            while high > low and alist[low] < mid:  #往右移动
                low += 1
            alist[high] = alist[low]
            
        alist[low] = mid #最后将基准赋值
        
        quick_sort(alist, start, low -1)    #进行递归， 以low为标注分界
        quick_sort(alist, low+1, end)
        return alist
    n =len(li)
    print('test quick sort')
    print(quick_sort(li, 0, n-1))

### 5、希尔排序法 ###

希尔排序(Shell Sort)是插入排序的一种。也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因DL．Shell于1959年提出而得名。 希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

![70 6][]

#5.希尔排序
    def shell_sort(alist):
        n = len(alist)
        gap = n//2
        while gap > 0:
            for i in range(gap, n):
                j = i 
                while j >= gap and alist[j-gap] > alist[j]: #插入排序
                    alist[j-gap], alist[j] = alist[j], alist[j-gap]
                    j -= gap  # 确保循环只能记性一次
            gap //= 2
        return alist 
    print(shell_sort(li))
    print(11/2) # 5.5
    print(11//2)    # 5 双斜杠输出整数

**另外一种与插入排序类似的方法**

>     # 插入排序方法为：
>     def insertSort(alist):
>         n = len(alist)
>         for i in range(1, n):
>             for j in range(i, 0, -1):
>                 if alist[j] < alist[j-1]:
>                     alist[j], alist[j-1] = alist[j-1], alist[j]
>         return alist
>     # print(insertSort(alist))
>     
>     def shell_sort(alist):
>         n = len(alist)
>         gap = n // 2
>         while (gap > 0):
>             for i in range(gap, n):
>                 for j in range(i, 0, -1):
>                     if alist[j] < alist[j-gap]:
>                         alist[j], alist[j-gap] = alist[j-gap], alist[j]
>             gap //= 2
>         return alist

### 6、归并排序法 ###

归并排序是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。

将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。

![70 7][]

#6.归并排序
    def merge(left, right):
        le = 0
        ri = 0
        result = []
        while (le < len(left)) and (ri < len(right)):
            if left[le] < right[ri]:
                result.append(left[le])
                le += 1
            else:
                result.append(right[ri])
                ri += 1
        result += left[le:]
        result += right[ri:]    #此处出现错误
        return result 
    
    def merge_sort(alist):
        n = len(alist)
        if n <= 1:
            return alist 
        num = n // 2
        left = merge_sort(alist[:num])
        right = merge_sort(alist[num:])
        return merge(left, right)
    print('test merge sort---')
    print(merge_sort(li))

### 7、堆排序法 ###

堆是具有下列性质的完全二叉树：  
每个分支节点的值都大于或等于其左右孩子的值，称为大顶堆；  
每个分支节点的值都小于或等于其做右孩子的值，称为小顶堆；  
因此，其根节点一定是所有节点中最大（最小）的值。

![aHR0cDovL3N0YXRpYy56eWJ1bHVvLmNvbS9mZWl4dWVsb3ZlMTAwOS94a2gweGFzMXR2Yjl1dGlpYXlrYXJ4bWQvaW1hZ2VfMWIzYmJmNnBxMWY4NDdjcTZ1ZjcwanB0ZTEzLnBuZw][]

def maxHeapfy(alist, length, parent):
        left = 2 * parent + 1
        right = 2 * parent + 2
        largest = parent
        if left < length and alist[left] > alist[largest]:
            largest = left
        if right < length and alist[right] > alist[largest]:
            largest = right
        if largest != parent:
            alist[largest], alist[parent] = alist[parent], alist[largest]
            maxHeapfy(alist, length, largest)  # 递归构建
    
    def buildMaxHeap(alist):  # 构建最大堆
        n = len(alist)
        lastParent = (n-1) // 2
        for i in range(lastParent, -1, -1):
            maxHeapfy(alist, n, i)
    
    def heapSort(alist):
        buildMaxHeap(alist)
        n = len(alist)
        for i in range(n-1, -1, -1):
            alist[0], alist[i] = alist[i], alist[0]  # 将最大值放在最后面
            maxHeapfy(alist, i, 0)
        return alist
    
    a = [30,50,57,77,62,78,94,80,84]
    print(a)
    print(heapSort(a))
    alist = [2, 4, 1, 2, 5, 58, 45, 24, 67]
    print(heapSort(alist))
    b = [random.randint(1,1000) for i in range(1000)]
    print(b)
    print(heapSort(b))

堆排序参考：[https://www.jianshu.com/p/d174f1862601][https_www.jianshu.com_p_d174f1862601] （很详细）

[https://blog.csdn.net/minxihou/article/details/51850001][https_blog.csdn.net_minxihou_article_details_51850001]

### 8、桶排序 ###

>     # 桶排序也叫计数排序，简单来说，就是将数据集里面所有元素按顺序列举出来，然后统计元素出现的次数。最后按顺序输出数据集里面的元素。
>     # 1.申请一个包含所有元素的数组，并初始化0。（需要找到最大值）
>     # 2.遍历原始数据，并计数。
>     # 3.遍历计数完成后的各个数组元素，输出索引值。

def buck_sort(alist):
        n = len(alist)
        maxList = alist[0]
        for a in alist:
            if a > maxList:
                maxList = a
        li = [0] * (maxList+1)  # 1. 创建数组
        for a in alist:  # 2. 进行计数
            li[a] += 1
        # print(li)
        # 3. 取出index
        new_alist = []
        for i in range(len(li)):
            if li[i] > 0:
                a = li[i]
                while a > 0:
                    new_alist.append(i)
                    a -= 1
        print(new_alist)

### 9、基数排序 ###

基数排序一般用于长度相同的元素组成的数组。首先按照最低有效数字进行排序，然后由低位向高位进行。

import random
    def radixSort():
        # A=[random.randint(1,9999) for i in range(10000)]
        A = [104, 101, 999, 200, 234]
        i, a = 0, A[random.randint(0, len(A))]
        while a > 0: # 计算数字的位数
            print(a)
            i += 1
            a //= 10
        for k in range(i):  # 进行i 轮的排序
            s=[[] for i in range(10)]
            for i in A:
                s[i//(10**k)%10].append(i)
            print(s)
            A=[a for b in s for a in b] # 变换了 A
            print("this is A")
            print(A)
        return A
    print(radixSort())

### 常见的算法效率比较： ###

![70 8][]![aHR0cDovL3N0YXRpYy56eWJ1bHVvLmNvbS9mZWl4dWVsb3ZlMTAwOS91MzduZGQ3a2RlNGUzNmdmdmMwbHgyODcvaW1hZ2VfMWIzY3BobTloZHEyNXNsMmExY2NuMW1uMDF0LnBuZw][]

![aHR0cDovL3N0YXRpYy56eWJ1bHVvLmNvbS9mZWl4dWVsb3ZlMTAwOS82ZXZ4ZHZob296a2s4N25ndHZoMnRqcmcvaW1hZ2VfMWIzY3BtZmI3ZG5oY2lnbG5maXJiaTFzOS5wbmc][]

*  如果待排序列基本有序，请直接使用简单的算法，不要使用复杂的改进算法。
 *  归并排序和快速排序虽然性能高，但是需要更多的辅助空间。其实就是用空间换时间。
 *  待排序列的元素个数越少，就越适合用简单的排序方法；元素个数越多就越适合用改进的排序算法。
 *  简单选择排序虽然在时间性能上不好，但它在空间利用上性能很高。特别适合，那些数据量不大，每条数据的信息量又比较多的一类元素的排序。

参考：[http://www.cnblogs.com/feixuelove1009/p/6143539.html][http_www.cnblogs.com_feixuelove1009_p_6143539.html]

### 八、二分查找法： ###

二分查找法的前提是：该数组是有序的

#二分查找法：前提是该数组是有序数组
    print(7/2)
    print(7//2)
    print(1//2)
    #查找给定的数字，如果存在，返回索引，否则，返回-1
    def BinarySearch(array, number):
        low = 0 
        high = len(array) -1 
        while low <= high:
            mid = (low+high)//2 
            if array[mid] < number:
                low = mid + 1
            elif array[mid] > number:
                high = mid -1
            else:
                return mid 
        return -1
    
    array1=[1,2,3,34,56,57,78,87]
    array2 = [1]
    print(BinarySearch(array2, 1))

[70]: /images/20220514/2bf930cb41b046beb72f92d74b184649.png
[70 1]: /images/20220514/98d62318d7a34a56b82b189df29ff11e.png
[70 2]: https://img-blog.csdn.net/20180906151537529?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[70 3]: /images/20220514/b13a606b1c824ff6b4ab125e497e3e98.png
[70 4]: /images/20220514/b1438c29cadb4c2692a5f4b882cd273e.png
[70 5]: /images/20220514/e6a69b29b2ec495aad18a2d35e4209fc.png
[70 6]: /images/20220514/f074df1733aa4b158f8877a65ca60d01.png
[70 7]: /images/20220514/3f8d9252c8d24d5aba7e23ef0778c57c.png
[aHR0cDovL3N0YXRpYy56eWJ1bHVvLmNvbS9mZWl4dWVsb3ZlMTAwOS94a2gweGFzMXR2Yjl1dGlpYXlrYXJ4bWQvaW1hZ2VfMWIzYmJmNnBxMWY4NDdjcTZ1ZjcwanB0ZTEzLnBuZw]: /images/20220514/8834c1afaed748c797403a6792916fbc.png
[https_www.jianshu.com_p_d174f1862601]: https://www.jianshu.com/p/d174f1862601
[https_blog.csdn.net_minxihou_article_details_51850001]: https://blog.csdn.net/minxihou/article/details/51850001
[70 8]: https://img-blog.csdn.net/20180906212306553?watermark/2/text/aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQwNTg3NTc1/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70
[aHR0cDovL3N0YXRpYy56eWJ1bHVvLmNvbS9mZWl4dWVsb3ZlMTAwOS91MzduZGQ3a2RlNGUzNmdmdmMwbHgyODcvaW1hZ2VfMWIzY3BobTloZHEyNXNsMmExY2NuMW1uMDF0LnBuZw]: /images/20220514/bfa90b0197544910a30feb9188259b40.png
[aHR0cDovL3N0YXRpYy56eWJ1bHVvLmNvbS9mZWl4dWVsb3ZlMTAwOS82ZXZ4ZHZob296a2s4N25ndHZoMnRqcmcvaW1hZ2VfMWIzY3BtZmI3ZG5oY2lnbG5maXJiaTFzOS5wbmc]: /images/20220514/a2d34eefc1e64decb14a4a4d9235d6d1.png
[http_www.cnblogs.com_feixuelove1009_p_6143539.html]: http://www.cnblogs.com/feixuelove1009/p/6143539.html