你真的会写这十种排序方法吗？

男娘i 2023-07-24 13:19 34阅读 0赞

### 十大经典排序算法 ###

*  常见的四种排序算法
 *   *  冒泡排序
     *  插入排序
     *  选择排序
     *  快速排序
 *  六种特殊排序算法
 *   *  归并排序
     *  希尔排序
     *  堆排序
     *  计数排序
     *  桶排序
     *  基数排序

网上关于排序的算法已经很多了，我为什么会写这篇博客呢？  
最近我看得一道笔试题是要写出快速排序算法，那还不简单？但是，结果却是我只想到了快排的思想，但是代码并没有写出来。（我对不起考98分的数据结构Orz！）  
面对算法，如果有小伙伴应该跟我一样，一说就会，一写就废，快来跟我从头撸一遍排序算法吧~包教包会，不会再看！  
我将十种经典的排序算法分为两类，一种是常见的四种排序算法（冒泡，插入，选择和快排），一种是不常见却特别有韵味的六种排序算法。常见的四种排序算法一定要会，就算是背也要背下来，后面六种排序重在思想。

先放一张十大排序算法的总结图。关于稳定性，通俗地讲就是排序前后两个相等的数相对位置不变，则算法稳定。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzkwMTU2MQ_size_16_color_FFFFFF_t_70_pic_center]

# 常见的四种排序算法 #

## 冒泡排序 ##

对于冒泡排序，大家应该是在熟悉不过了，这里就带大家简单回顾一下。  
冒泡排序的思想是每次遍历都要让每两个元素依次比较，以此将最大值替换到末尾（或者将最小的值替换到最首）。以下是python代码

def swap(arr,a,b):
        # 交换数组arr中下标a和b的数据
        temp = arr[a]
        arr[a] = arr[b]
        arr[b] = temp
    def bubbleSort(arr):
        for i in range(len(arr)):
            # 依次遍历数组
            for j in range(0,len(arr) - i - 1):
                # 依次两两比较，将最大值放在末尾
                if arr[j] > arr[j+1]:
                    swap(arr,j,j+1)
            # print(arr)
        return arr

每次遍历的结果如图所示，可以看到每次遍历都会选择一个最大值，依次放在后面。  
![每次遍历的结果][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzkwMTU2MQ_size_16_color_FFFFFF_t_70]

## 插入排序 ##

插入排序的思想是：对于未排序的数据在已排序的序列arr\[:p\]中依次找到相应位置插入，每当插入元素时需要将待插入元素后面的元素后移。

def insertSort (arr):
        if len(arr) <= 1:
            return arr
        p = 1
        # 这里假设arr[:p]是已排序列，arr[p:]是未排序列
        while p != len(arr):
            # print(arr)
            move_index = p  # 要插入的位置的初始值设为p
            
            # 在未排序列中找一个值，我这里找的是最后一个值end_value，并用temp暂时记住end位置的值
            end_value = arr[len(arr) - 1]
            end = len(arr) - 1
            temp = end_value
    
            # 确定end_value要插入的位置
            for index in range(p): 
                if arr[index] > end_value:
                    move_index = index
                    break
            # 将move_index之后的元素都后移一位，并在move_index这个位置插入end_value
            while end != move_index:
                arr[end] = arr[end - 1]
                end -= 1
            arr[move_index] = temp
    
            p += 1
        return arr

每次插入的结果如图，可以看到，随着最末尾的元素依次插入，有序序列的队伍逐渐庞大起来了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzkwMTU2MQ_size_16_color_FFFFFF_t_70 1]

## 选择排序 ##

选择排序的思想是：主要在选择上，每一次从无序队列中选择出最小值，然后将其与有序队列后面的元素替换位置。

def selectionSort(arr):
        length = len(arr)
        for i in range(length):
            # arr[:i]都是有序数列，依次将arr[i:]的最小值与arr[i]替换位置
            # 先假设arr[i:]的最小值min为arr[i]
            min_index = i
            # print(arr)
            for j in range(i,length):
                if arr[min_index] > arr[j]:
                    min_index = j
    
            if min_index != i:
                swap(arr,min_index,i)
    
        return arr

每次插入的结果如图，可以看到，每次将无序序列的最小值与有序队列后面的元素替换位置，有序序列的队伍逐渐庞大起来了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzkwMTU2MQ_size_16_color_FFFFFF_t_70 2]  
选择排序和冒泡排序，插入排序一样，都是将无序序列逐步扩大到有序序列中，这三种方法的不同之处在于：  
1.选择排序只需要在无序序列**遍历**找到最小值，依次**替换**到有序序列后面。  
2.插入排序是在无序序列中**随便**抓一个元素，在有序序列中找到合适的位置再将元素**插入**。由于“插入”函数，所以需要将待插位置后面的元素依次向后移动。  
3.冒泡排序是在无序序列中通过依次**两两比较**找到最小值的，依次**替换**到有序序列后面。

## 快速排序 ##

快速排序的思想是：随机找一个下标p（我是默认为最后一个元素，当时老师教的时候叫这个位置为哨兵），**递归**将数组中的元素规划将比arr\[p\]大的数放在arr\[p\]右边 将比arr\[p\]小的数放在arr\[p\]左边。

def swap(arr,a,b):
        temp = arr[a]
        arr[a] = arr[b]
        arr[b] = temp
        
    def quickSort(arr, start, end):
        left = start
        right = end
        # 先判断是否有不满足排序的情况
        if len(arr) <= 1 or right <= left or left < 0 or right > len(arr)-1:
            return arr
        # 在arr[start:p-1]中划分
        # 在left找到一个比arr[p]大的数(顺序left += 1)，在right找到一个比arr[p]小的数(逆序right -= 1)，将arr[left]和arr[right]替换
        # 直至left==right，一次划分结束
        p = right
        right -= 1
        # print(arr)
        while right > left:
            # print(p, left, right)
            if arr[p] < arr[left] and arr[p] > arr[right]:
                swap(arr,left,right)
            elif arr[p] >= arr[left]:
                left += 1
            elif arr[p] <= arr[right]:
                right -= 1
    
        # 如果arr[p] < arr[left]，将此时的left下标处的值与p下标处的值替换
    
        if right == left and arr[p] < arr[left]:
            # print('###')
            swap(arr,p,left)
            p = left
    
        # 注：不存在right == left and left !=arr[p] and arr[p] > arr[left]的情况。只存在arr[p]>所有arr[start:p-1]
    
        # 对p两边的数组进行排序
        kuaisu(arr, start, p-1)
        kuaisu(arr, p+1, end)
        return arr

每次插入的结果如图，可以看到，快速排序是自上而下的，每次将数据划分为两拨，左边一波元素比哨兵元素大，右边一波的元素都比哨兵元素小。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzkwMTU2MQ_size_16_color_FFFFFF_t_70 3]  
到这里，四种常见的排序算法都讲完了，这四个算法很重要！！！这都是基础！！！后面讲的六种算法有的也使用到了这些基础算法。

# 六种特殊排序算法 #

## 归并排序 ##

归并排序的思想是采用分治法依次将两个有序表合并成一个有序表。

def twoMerge(arr1,arr2):
        # 对于两个数组，进行归并
        newarr = []
        first_index = 0     # arr1的动态下标
        second_index = 0    # arr2的动态下标
        first_len = len(arr1)   # arr1的长度，作为first_index的下标上限
        second_len = len(arr2)  # arr2的长度，作为second_index的下标上限
        while first_index < first_len and second_index < second_len:
            if arr1[first_index] < arr2[second_index]:
                newarr.append(arr1[first_index])
                first_index += 1
            else:
                newarr.append(arr2[second_index])
                second_index += 1
        # 对于arr2中的元素还未全部归并到新数组的情况
        if first_index == first_len:
            newarr += arr2[second_index:]
        # 对于arr1中的元素还未全部归并到新数组的情况
        else:
            newarr += arr1[first_index:]
        return newarr
    
    def mergeSort(arr):
        length = len(arr)
        # 先对字符串长度进行限制，以免陷入死循环
        if length <= 1:
            return arr
        mid = length // 2
        # print(arr, arr[:mid],arr[mid:])
        return twoMerge(mergeSort(arr[:mid]),mergeSort(arr[mid:]))

这里，归并算法最重要的一步就是通过使用**指针**的方式将两个数组有序归并，也就是twoMerge函数。（这里划重点）

## 希尔排序 ##

希尔排序采用的是分而治之的想法先将整个待排序的记录序列分割成为若干子序列组，分别对其进行插入排序。  
在这里，我先将讲一个这里使用的分组思想。一个班里面有12个同学，假设这次考试的成绩排名为\[98,97,94,86,83,79,74,69,65,63,60,59\]，老师想要为这12个同学分成三组，而且想要每个组里优良中差的学生分布的比较均匀。老师先为这组成绩划分四个等级，每个等级三个人：优：\[98,97,94\]，良：\[86,83,79\]，中：\[74,69,65\]，差:\[63,60,59\]。并且依次在四个等级中抽一个学生，让分布在优良中差的四个学生组成一个学习小组，这样就会分布得比较均匀了。  
在希尔排序算法中，数组中的元素没有优良中差之说，但是需要先划分，这时候的划分没有依据，随机划分即可。有点像等差数列的思想，在数组中以k为跨步，每k个元素为一个“等级”，在每个等级中选择第i个元素组成一个组，这个组内的元素下标为\{i,k+i,2k+i,…,nk+i\}。  
比如，在13个元素的数组中，要想划分为两组，首先分成7（13/7的上取整）个等级\{\[0,1\],\[2,3\],\[4,5\],\[6,7\],\[8,9\],\[10,11\],\[12\]\}，将每个等级中的第一个元素组成一个组\[0,2,4,6,8,10,12\]，每个等级中的第二个元素组成另一个组\[1,3,5,7,9,11\]。

讲完这个分组思想，我们继续讲希尔排序：  
1.按照等差数列的原理分组，分组成k组(k=len/2)，在每个数据段arr\[(a-1)k:ak\]中依次选择第i个元素组成一组\{arr\[ak+i\]\}  
2.在每个组内对数组进行插入排序  
3.然后，将组数等差减半，再在组内进行插入排序  
4.直到只能分为一组时，即对全部数组进行插入排序

希尔排序的内核排序还是使用内插法，虽然比较的次数多，但是交换的次数变少了

def shellSort(arr):
        gap = 1
        lenght = len(arr)
        # 分组
        while gap < lenght // 2:
            gap = gap * 2
    
        while gap > 0:
            # 组内使用内插法
            for i in range(gap,lenght):
                temp = arr[i]
                j = i - gap
                while j >= 0 and arr[j] > temp:
                    arr[j+gap] = arr[j]
                    j -= gap
                arr[j + gap] = temp
            gap = gap//2
            # print(arr)
        return arr

## 堆排序 ##

堆排序就是利用类似于二叉树的结构，依次将数组中最大值找到。这里由于涉及到要画图，我就偷个懒挂个链接叭~  
[\[Java排序算法\]–堆排序 (Heap Sort)][Java_ _Heap Sort].

def buildMaxHeap(arr):
        import math
        for i in range(math.floor(len(arr)/2),-1,-1):
            heapify(arr,i)
    
    def heapify(arr, i):
        left = 2*i+1
        right = 2*i+2
        largest = i
        if left < arrLen and arr[left] > arr[largest]:
            largest = left
        if right < arrLen and arr[right] > arr[largest]:
            largest = right
    
        if largest != i:
            swap(arr, i, largest)
            heapify(arr, largest)
    
    def swap(arr, i, j):
        arr[i], arr[j] = arr[j], arr[i]
    
    def heapSort(arr):
        global arrLen
        arrLen = len(arr)
        buildMaxHeap(arr)
        for i in range(len(arr)-1,0,-1):
            swap(arr,0,i)
            arrLen -=1
            heapify(arr, 0)
        return arr

## 计数排序 ##

计数排序的思想就比较厉害了，别的算法需要通过比较进行排序，而计数排序就不需要！！但是计数排序要求输入的数据必须是有确定范围的整数，比如对一个公司的员工年龄进行排序。

计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中，不需要比较！！！  
这里有点像字典的形式，计数排序先通过遍历，将数组中的元素以**元素**和**元素出现的次数**作为键值对存储起来，然后再利用这个键值对依次将元素依次写入原数组。比如，遍历数组\[3,0,0,1,3\]之后的**元素**和**元素出现的次数**对为\{0:2,1:1,2:0,3:2\}，那么只需要将2个0，1个1，0个2，2个3依次写入，得到数组\[0,0,1,3,3\]就是有序数组了。

def countSort(arr,maxValue):
    	# maxValue是arr中的最大元素
        length = len(arr)
        # 新建立个bucket数组，以字典的形式存储arr数组
        bucket_len = maxValue + 1
        bucket = [0]*bucket_len
        # 将数的个数放入对应的桶中
        for i in range(length):
            if not bucket[arr[i]]:
                bucket[arr[i]] = 0
            bucket[arr[i]] += 1
        #  将bucket中的数据为arr排序（重新往arr中放入数据）
        temp_index = 0
        for j in range(bucket_len):
            while bucket[j] > 0:
                arr[temp_index] = j
                bucket[j] -= 1
                temp_index += 1
    
        return arr

虽然计数排序不需要比较，但是需要大量内存空间，所以一般不会用这个排序方法。

## 桶排序 ##

如果你能看懂上面的计数排序，那么恭喜你，你已经一只脚踏入了桶排序的大门了。

桶排序的思想是将数组中的元素按照一定的规则放在不同的桶里，每个桶对桶内元素排序，排好序之后再合并桶，对，没错，这里就是归并排序的归并思想。

这里先不放代码，先看下一个排序算法。

## 基数排序 ##

基数排序也是用到了桶排序的思想。  
基数排序是按照低位先排序，然后收集(按照个位装桶)；再按照高位排序，然后再收集(按照十位装桶)；依次类推，直到最高位。

def radixSort(arr, maxDigit):
        # maxDigit是arr数组中最大元素的位数，不是重点，略
        length = len(arr)
        for i in range(maxDigit):
            counter = [[], [], [], [], [], [], [], [], [], []]
            # 这里没有用[[]]*10，参考https://blog.csdn.net/yockie/article/details/46127829
            division = pow(10,i)    # 除数，用来求各个位数上的值
            for j in range(length):
                bucket = arr[j] // division % 10   # 构造位数桶
                counter[bucket].append(arr[j])
            #  将counter中的每个bucket中的数据为arr排序（重新往arr中放入数据）
            temp_index = 0
            for buck in counter:
                for value in buck:
                    arr[temp_index] = value
                    temp_index += 1
        return arr

代码中的参考链接 [python-如何创建二维数组][python-].  
值得注意的是：  
基数排序：根据键值的每位数字来分配桶；(要求数组元素必须全是整数)  
计数排序：每个桶只存储单一键值；(要求数组元素有范围)  
桶排序：每个桶存储一定范围的数值；(要求数组元素有范围)

以上就是十种排序的全部内容了，如果有疏漏的地方，欢迎指出。  
散花~~  
![在这里插入图片描述][20200412023752734.jpeg_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzkwMTU2MQ_size_16_color_FFFFFF_t_70_pic_center]: /images/20230528/677d360bac0a4b70a7c887488c65d836.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzkwMTU2MQ_size_16_color_FFFFFF_t_70]: /images/20230528/a13d9d52e9eb4c48b3dd410416ebf5b0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzkwMTU2MQ_size_16_color_FFFFFF_t_70 1]: /images/20230528/d2f34cb2d3164609800958c55d10203f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzkwMTU2MQ_size_16_color_FFFFFF_t_70 2]: /images/20230528/487ad15641a8466490671e20d9a3b5a8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl8zNzkwMTU2MQ_size_16_color_FFFFFF_t_70 3]: /images/20230528/2f25423cdaf943459444c585a6444146.png
[Java_ _Heap Sort]: https://blog.csdn.net/high2011/article/details/78400379
[python-]: https://blog.csdn.net/yockie/article/details/46127829
[20200412023752734.jpeg_pic_center]: /images/20230528/d9d72d3754934b5b894486a7dc43ab41.png