详细讲解八大排序算法的思路和实现步骤

淡淡的烟草味﹌ 2021-12-13 02:13 203阅读 0赞

### 目录 ###

*  一、冒泡排序
 *   *  算法原理
     *  代码实现
 *  二、选择排序
 *   *  算法思路
     *  代码实现
 *  三、插入排序
 *   *  算法思路
     *  代码实现
 *  四、希尔排序
 *   *  算法思路
     *  代码实现
 *  五、快速排序
 *   *  算法思路
     *  代码实现
 *  六、归并排序
 *   *  算法思路
     *  代码实现
 *  七、基数排序
 *   *  算法思路
     *  代码实现
 *  八、堆排序
 *   *  算法思路
     *  代码实现
 *  九、性能对比

# 一、冒泡排序 #

## 算法原理 ##

1.  从集合的第1至n个元素，依次进行两两比较，出现前面一个元素比后面的大的情况就进行交换，即每次都把数值较大的元素放在后面，这样一轮下来，第n个元素就是集合中数值最大的元素了；
2.  接下来，就从第1至n-1，进行步骤1相同的操作，完成后第n-1个元素就第二大的元素了；
3.  继续重复这样的操作，直到元素都无需进行交换。（这其实是冒泡排序的一个小优化点，当出现所有元素都没有进行交换的时候，就无需再迭代，集合已经完成排序了）

## 代码实现 ##

def bubbleSort(arr):
        flag = False
        for n in range(len(arr) - 1):
            for i in range(len(arr) - n - 1):
                if arr[i] > arr[i+1]:
                    arr[i], arr[i+1] = arr[i+1], arr[i]
                    flag = True
            if not flag:  # 如果没有进行过数据交换，则无需再进行排序
                break
            else:
                flag = False
        
        return arr

# 二、选择排序 #

## 算法思路 ##

1.  让集合中的第一个元素，与后面的所有元素即第2至n个元素都进行比较，然后与数值最小的元素的位置进行交换；
2.  接着，让第二个元素，与后面的所有元素即第3至n个元素进行比较，然后与最小的元素的位置进行交换；
3.  继续重复这样的操作，就可以完成排序了。（总共需要n-1轮迭代）

## 代码实现 ##

def selectionSort(arr):
        
        for i in range(len(arr)-1):
            _min = arr[i]
            min_index = i
            for j in range(i+1, len(arr)):
                if _min > arr[j]:
                    _min = arr[j]
                    min_index = j
            arr[i], arr[min_index] = arr[min_index], arr[i]
        
        return arr

***因为选择排序进行数据交换的操作会少很多，所以选择排序的效率会比冒泡排序高；但是如果对于大部分是有序的集合来说，冒泡排序就可能会快些，因为可以提前停止迭代***

# 三、插入排序 #

## 算法思路 ##

每次让集合的第i（2 <= i <= n）个元素，与前面的i-1个元素，从后往前逐个比较，遇到比自己大的，则让该位置的元素后移，直到找到比自己大的，则停止迭代，插入该位置的后一个位置。

## 代码实现 ##

def insertSort(arr):
        for i in range(1, len(arr)):
            val = arr[i]
            index = i - 1
            while (index >= 0) & (val < arr[index]):
                arr[index + 1] = arr[index]
                index -= 1
            
            arr[index+1] = val
        
        return arr

***缺点：当集合靠后位置存在很小的数值时，需要进行很多次的元素移动位置即对集合的拷贝操作***

# 四、希尔排序 #

## 算法思路 ##

***希尔排序其实就是插入排序的进阶版，解决了上面说到的缺点。***

1.  每次先对数组先进行分组，然后对每一组都进行插入排序；
2.  第一次尽可能多的分组（n // 2），接着下轮减少分组（上轮组数的一半）；
3.  直到数组的所有元素都在同一组里面；
4.  这样做的目的就是尽量先将数值较小的元素放到前面。  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]

## 代码实现 ##

def shellSotr(arr):
        n = len(arr) // 2  # n：分组数，其实也是每组的步长
        while n > 0:
            for i in range(n):
                for j in range(i + n, len(arr), n):  # 对每组数据进行遍历
                    # 进行插入排序
                    val = arr[j]
                    index = j - n
                    while (index >= i) & (val < arr[index]):
                        arr[index + n] = arr[index]
                        index -= n
                    arr[index + n] = val
    
            n = n // 2

# 五、快速排序 #

## 算法思路 ##

1.  第一次，从集合中选取一个数值v（一般是中间位置），然后比v小的放在左边，比v大的放在右边；
2.  接下来，就是一个递归过程了：分别对左边和右边的区域进行第1步的操作，然后又继续对新的左边和右边的区域进行同样的操作。
3.  其实第1步还是有点难度，需要一点技巧的：同时从左边第1个数值和右边最后1个数值向中间位置进行遍历，当左边遇到比v大和右边遇到比v小的，就交换位置，然后继续遍历；
4.  需要注意的是：先达到中间位置的一边继续移动（或者遇到与中间位置的数值相等），另一边暂停移动。

## 代码实现 ##

def quickSortRecursion(arr, left, right):
        """ The recursion of quickSort :param arr: :param left: 此次排序数组范围的最左索引 :param right: 最右索引 :return: """
        mid = arr[(right + left) // 2]  # 取数组中间位置的数值作为划分左右区域的依据
        LEFT = left  # 将输入的left固定住，用于递归的输入
        RIGHT = right  # 同上
    
        while left < right:
            while arr[left] < mid:
                left += 1
            while arr[right] > mid:
                right -= 1
    
            if left >= right:
                break
    
            arr[left], arr[right] = arr[right], arr[left]
    
            # 先达到中间位置的一边继续移动（或者遇到与中间位置的数值相等），另一边暂停移动
            if arr[left] == mid:
                right -= 1
            if arr[right] == mid:
                left += 1
    
        # 此时有一边已经完成排序，需要移动一个位置，否则会无限递归
        if left == right:
            left += 1
            right -= 1
    
        if LEFT < right:
            quickSortRecursion(arr, LEFT, right)
        if RIGHT > left:
            quickSortRecursion(arr, left, RIGHT)
    
    
    def quickSort(arr):
        """ quickSort 快速排序 :param arr: 待排序数组 :return: """
        quickSortRecursion(arr, 0, len(arr)-1)

# 六、归并排序 #

## 算法思路 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 1]![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 2]

## 代码实现 ##

from typing import List
    
    
    def merge(arr1: List, arr2: List):
        """ 将两个有序数组合并为一个数组，仍保持有序 :param arr1: :param arr2: :return: """
        res = []
        i1 = 0
        i2 = 0
        while i2 < len(arr2):
            if i1 >= len(arr1):
                res.extend(arr2[i2:])
                break
    
            if arr2[i2] <= arr1[i1]:
                res.append(arr2[i2])
                i2 += 1
            else:
                while i1 < len(arr1):
                    if arr1[i1] < arr2[i2]:
                        res.append(arr1[i1])
                        i1 += 1
                    else:
                        break
    
        if i1 < len(arr1):
            res.extend(arr1[i1:])
    
        return res
    
    
    def merge_sort(arr: List):
        """ 归并排序 :param arr: :return: """
        # 归并排序中分治思想的"分"阶段：将原数组分为长度为1的子序列数组，可能会有一个长度为2的（数组的长度为奇数时）
        res = []
        i = 0
        while i < len(arr):
            if len(arr) - i == 3:
                res.append([arr[i]])
                res.append(sorted(arr[i+1:]))
                i += 3
            else:
                res.append([arr[i]])
                res.append([arr[i+1]])
                i += 2
        # 归并排序中分治思想的"治"阶段：将两两之间的有序子序列进行合并为一个新的有序子序列，直到只剩一个有序子序列，即为最终的排序结果
        while len(res) > 1:
            temp = []
            i = 0
            while i <= len(res)-1:
                if i == len(res)-1:
                    temp.append(res[i])
                    break
                else:
                    temp.append(merge(res[i], res[i+1]))
                    i += 2
            res = temp
    
        return res[0]
    
    
    if __name__ == '__main__':
        # print(merge([4, 8], [3, 5, 9, 10]))
        print(merge_sort([8, 4, 5, 7, 1, 3, 6]))

# 七、基数排序 #

## 算法思路 ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 3]  
从低位数->高位数，即个位数->十位数->百位数->…，依次按照上图的做法。最后从桶取出放入数组的即为有序数组了。  
![在这里插入图片描述][20190730081245292.png]

## 代码实现 ##

from typing import List
    
    
    def bucket_sort(arr: List[int], max_len: int):
        """ 基数排序（桶排序） :param arr: :param max_len: 最大值的位数 :return: """
        temp = arr.copy()  # 用于存放每次从桶取出的数据
    
        # 建立0-9 10个桶
        bucket = dict()
        for i in range(10):
            bucket[i] = []
    
        # 最大值只有三位数的情况下
        for i in range(1, max_len):
            # 将数值放入对应的桶中
            for a in temp:
                bucket[get_digit(a, i)].append(a)
            # 将数值从桶按顺序取出，并将桶清空
            temp = []
            for n in range(10):
                temp.extend(bucket[n])
                bucket[n] = []
    
        return temp
    
    
    def get_digit(num: int, n: int):
        """ 取出num对应位数的数值，1代表个位数，2代表十位数，以此类推 :param num: :param n: n位数 :return: """
        num_str = str(num)
        if n > len(num_str):
            return 0
        else:
            return int(num_str[-n])
    
    
    if __name__ == '__main__':
        print(bucket_sort([10, 5, 321, 33, 11, 100]))

# 八、堆排序 #

## 算法思路 ##

首先，我们需要了解什么是**大顶堆？**  
大顶堆是一种每个结点的值都要大于或等于其左右孩子结点的值，如下图：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 4]  
如用数组的形式来表示的话则如下，有个特点：arr\[i\] >= arr\[2*i+1\] && arr\[i\] >= arr\[2*i+2\]，整理成大顶堆之后最大值就会在数组的第一个位置。  
![在这里插入图片描述][20191016065917340.jpeg]  
相反，小顶堆则如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 5]  
那么我们的思路是这样：

1.  首先，将整个数组调整为大顶堆：从最后一个非叶子结点开始，以当前结点当作根节点，进行大顶堆调整；然后以同样的方式向前遍历，这样整个数组就调整为大顶堆了；
2.  然后，将数组的第一个元素（最大值）与最后一个元素进行位置的调换；
3.  再重复第1和2步的步骤，只是每次调整为大顶堆的数组位置是从第一个到倒数第n个（n表示第n轮）
4.  这样，整个数组就完成排序了。

一般升序采用大顶堆，降序采用小顶堆

## 代码实现 ##

import random
    import time
    
    
    # 以index=root作为根节点，向下进行递归：将父节点与子节点中进行比较，将父节点替换为较大值
    def heap(arr, root, length):
        # 左子树的index
        left = 2 * root + 1
        # 右子树的index
        right = 2 * root + 2
    
        head = root
    
        if left < length:
            if arr[head] < arr[left]:
                head = left
    
        if right < length:
            if arr[head] < arr[right]:
                head = right
    
        if head != root:
            arr[root], arr[head] = arr[head], arr[root]
            heap(arr, head, length)
    
    
    # 从最后一个非叶子节点向前调整，不然无法保证大顶堆的建立
    def max_heap(arr, length):
        for i in range(int(len(arr)/2)-1, -1, -1):
            heap(arr, i, length)
    
    
    # 建立大顶堆之后，数组的第一个元素就为最大值了
    # 然后将第一个元素替换到最后的位置
    # 忽略最后一个元素，继续建立大顶堆
    def heap_sort(arr):
        length = len(arr)
        for i in range(length):
            max_heap(arr, length-i)
            arr[0], arr[length-i-1] = arr[length-i-1], arr[0]

***完整的代码已上传至 [GitHub][]***

# 九、性能对比 #

import random
    import time
    from python.Sort.sorts import bubbleSort, selectionSort, insertSort, shellSort, quickSort
    from python.Sort.MergeSort import merge_sort
    from python.Sort.HeapSort import heap_sort
    
    
    """ 各种排序算法性能测试对比： bubbleSort : 7.712609052658081 selectionSort : 2.404778003692627 insertSort : 3.383096218109131 shellSort : 0.043745994567871094 quickSort : 0.020576000213623047 merge_sort : 0.04463386535644531 heap_sort : 15.450256109237671 sorted : 0.0013229846954345703 嘤嘤嘤，事实证明python尽量还是用自带的方法，毕竟很多底层都是c实现的，速度比你自己实现的快了不止一点点 """
    
    n = 10000
    methods = ["bubbleSort", "selectionSort", "insertSort", "shellSort", "quickSort", "merge_sort", "heap_sort", "sorted"]
    for method in methods:
        l = [random.randint(0, n) for i in range(n)]
        s1 = time.time()
        eval(method)(l)
        s2 = time.time()
        print(method, ":", s2-s1)

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 6]  
欢迎关注同名公众号：“我就算饿死也不做程序员”。  
交个朋友，一起交流，一起学习，一起进步。![在这里插入图片描述][20200430113642545.jpg]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70]: /images/20211210/61aa1d207b5942dea438b16c93a2844c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20190730074410117.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ==,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 2]: /images/20211210/736cafc022b844429e9f9b2e26c0d56e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 3]: /images/20211210/85ca077790e64955b66aff81d29d9611.png
[20190730081245292.png]: /images/20211210/83cd3ed678f34e468df71a0de594b6cb.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 4]: /images/20211210/587566dc85ba48be9a15d55a52247313.png
[20191016065917340.jpeg]: /images/20211210/7c1d9a3f9b204baeba69423248dc3cbf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 5]: /images/20211210/46687f7b4ca54df0a8676059b560fe28.png
[GitHub]: https://github.com/SGyuanshi/Algorithm/tree/master/python/Sort
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3NneXVhbnNoaQ_size_16_color_FFFFFF_t_70 6]: /images/20211210/ff4523a0f2334057a3e429c412bd59b0.png
[20200430113642545.jpg]: /images/20211210/b1b38124062f4e39b9fb89c7c4564dcc.png