常见的排序算法（python实现）

朱雀 2023-03-13 02:53 98阅读 0赞

排序算法有很多种，如冒泡排序、选择排序、快速排序等。

## 冒泡排序（升序） ##

冒泡排序是最基础的排序算法，他的基本思想就是：有两层循环，第一层循环n次，第二次循环n-i-1次，在第二次循环中比较第j个元素和第j+1个元素的大小，如果第j个元素大于第j+1那么这两个元素交换位置。这样的话每进行一次内循环就会将前n-i个元素的最大值放到n-i处。  
以下是冒泡排序的图解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MzI3MjY2_size_16_color_FFFFFF_t_70]

以下是python代码实现：

def  bubble(arr):
        n = len(arr)
        for i in range(n):
            for j in range(n-i-1):
                if arr[j] > arr[j+1]:
                    m = arr[j]
                    arr[j] = arr[j+1]
                    arr[j+1] = m
        return arr

总结:冒泡排序的时间复杂度是O(n^2)。冒泡排序有一个明显缺点就是有太多的交换次数，最多可能会交换 (n-1)! 次。

## 选择排序（升序） ##

选择排序是对冒泡排序的改进，他减少了交换次数，最多可能进行n-1次排序。基本思想是：跟冒泡排序类似，也是进行两次循环，每次内循环都会在第i个元素至n-1个元素之间找到最小值，然后将它与第i个元素交换位置。  
图解：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MzI3MjY2_size_16_color_FFFFFF_t_70 1]  
python代码实现：

def select(arr):
        n = len(arr)
        for i in range(n):
            min = i
            for j in range(i,n):
                if arr[j] < arr[min]:
                    min = j
            m = arr[i]
            arr[i] = arr[min]
            arr[min] = m
        return arr

总结：选择排序的时间复杂度是O(n^2)。虽然时间复杂度与冒泡排序相同，但时间上选择排序的速度更快一些。

## 插入排序（升序） ##

插入排序的速度与选择排序速度差不多。基本思想就是将选择排序中的寻找最小值变成了将第i个元素插入到前i-1个元素当中。  
python代码实现，这里借助了另外一个列表：

def insertSort(arr):
        temp = [arr[0]]
        n = len(arr)
        for i in range(1,n):
            for j,v in enumerate(temp):
                if arr[i] < v:
                    temp[j:j] = [arr[i]]
                    break
            else:
                temp.append(arr[i])
        return temp

时间复杂度是O(n^2)

## 快速排序（升序） ##

快速排序和前面的方法相比是最快的排序方法，它的基本思想是：递归的调用自己，每次都将传进来的数组进行遍历，数组中大于等于数组最后一个元素的放在右边，小于的放在左边。  
图解，递归调用顺序是left,midd,right;结束条件是传入的数组长度为1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MzI3MjY2_size_16_color_FFFFFF_t_70 2]  
代码实现：

def quick(arr,res):
        right = []
        left = []
        n = len(arr)
        las = arr[-1]
        if n == 1:
            res.append(las)
            return
        for i in range(n-1):
            if arr[i] >= las:
                right.append(arr[i])
            else:
                left.append(arr[i])
        # 顺序是左-自身-右(小-中间-大)
        #这是小
        if left:
            quick(left,res)
        # 这是中间值
        quick([las],res)
        # 这是大
        if right:
            quick(right,res)

时间复杂度是O(n\*logn)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MzI3MjY2_size_16_color_FFFFFF_t_70]: /images/20230312/f4bfdcd02f0f41b994b618f600a8c9b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MzI3MjY2_size_16_color_FFFFFF_t_70 1]: /images/20230312/276a9bd70ea949f9974cc08b6c9bcbfc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzM2MzI3MjY2_size_16_color_FFFFFF_t_70 2]: /images/20230312/05b59e1a26e9455696201bfe1779be69.png