经典排序算法及其python实现

Myth丶恋晨 2022-06-09 04:11 149阅读 0赞

![这里写图片描述][SouthEast]  
这是常见的几种排序算法，另外还有归并排序：  
![这里写图片描述][SouthEast 1]  
之后我将介绍每种排序算法并用python实现。  
由于排序问题的计算时间下界是O（nlogn），所以归并排序和快速排序都是渐进最优排序算法。

## 1 插入排序 ##

## 1.1 原理 ##

插入排序是将一个数插入到已经排好序的序列中 L。升序排列的具体步骤是：  
（1）外循环：依次遍历每一个元素；  
（2）当某个位置 k 上的数小于它**相邻**的前面位置 k - 1 的数，则开始依次比较；  
（3）内循环：将 L\[k\] 和前面的每个位置（逆序比较，依次为 k-1,k-2,…）的数进行比较，如果小于，就交换两个位置的数，继续比较；如果大于，就停止内循环；

## 1.2 时间复杂度和空间复杂度 ##

**空间复杂度：**交换两个位置的数值时，需要1个临时空间，所以空间复杂度为 1 。  
**时间复杂度：**排序经历内外循环，所以时间复杂度是n方。

## 1.3 python代码 ##

#coding:utf-8
    num = raw_input("输入需要排序的数字集合，以空格分隔：")
    num_list = num.split()
    num_list = [int(i) for i in num_list]
    for i in range(1,len(num_list)):
        if num_list[i-1] > num_list[i]:
            temp = num_list[i]
            index = i
            while temp < num_list[index-1] and index > 0:
                num_list[index] = num_list[index-1]
                index -= 1
            num_list[index] = temp
    print "res",num_list

## 2 冒泡排序 ##

## 2.1 原理 ##

冒泡排序是参照水中气泡依次往上冒得情景得来的。例如，从前往后依次将大数移动到后面，这样一轮下来，最大的数肯定在最后。  
我觉得插入排序和冒泡排序的关键步骤很像：都是相邻数之间的比较；都需要经历内外循环；一个是将大数往后移动，一个是将小数往前移动。  
具体步骤如下：  
（1）外循环：主要是用来控制内循环的次数 i ，一共经历 n 轮训还；  
（2）内循环：每次都从位置 i = 0 开始比较，如果 L\[ i \] > L \[i + 1\]，就将L\[ i \]元素和 L \[i + 1\]元素交换，相当于大的数向后移动了一位，然后继续移动 i + 1，依次比较，知道这轮循环结束，最大的数肯定在 L \[ n-1 \]处；  
（3）注意：在内循环时有一个缩短时间的方法，就是在控制循环次数时，不在考虑之前已经排好序的“大数”，也就是从后往前已经排好序的数。经过每轮外循环，都会有一个排好序的大数。

## 2.2 时间复杂度和空间复杂度 ##

**空间复杂度：**交换两个位置的数值时，需要1个临时空间，所以空间复杂度为 1 。  
**时间复杂度：**排序经历内外循环，所以时间复杂度是n方。

## 2.3 python代码 ##

#coding:utf-8
    num = raw_input("输入要排序的数字集合，以空格分隔:")
    number = [int(i) for i in num.split()]
    count = 0
    for i in range(0,len(number)):
        count += 1
        for j in range(len(number)-1-i): #如果没有-i，那么最坏复杂度是n方
            count += 1
            if number[j] > number[j+1]:
                temp = number[j]
                number[j] = number[j+1]
                number[j+1] = temp
    print number
    print count
    '''
    input:9 8 7 6 5 4 3 2 1
    count:45
    去掉第二个for循环的-i，结果count=81
    '''

## 3 选择排序 ##

## 3.1 原理 ##

从所有序列中先找到最小的，然后放到第一个位置。之后再看剩余元素中最小的，放到第二个位置……以此类推，就可以完成整个的排序工作了。可以很清楚的发现，选择排序是固定位置，找元素。相比于插入排序的固定元素找位置，是两种思维方式。  
具体步骤如下：  
（1）外循环：固定某个位置，从 i =0 开始，然后再在内循环中找对应位置的元素，到i = n-1 结束；  
（2）内循环：找到位置 i 之后的所有数中最小的数，和 位置 i 的数交换；

## 3.2 时间复杂度和空间复杂度 ##

**空间复杂度：**交换两个位置的数值时，需要1个临时空间，所以空间复杂度为 1 。  
**时间复杂度：**排序经历内外循环，所以时间复杂度是n方。

## 3.3 python 代码 ##

#coding:utf-8
    num = raw_input("请输入要排序的集合，用空格分隔：")
    data = [int(i) for i in num.split()]
    for i in range(len(data)):
        minest = data[i]
        index = i
        for j in range(i+1,len(data)):
            if data[j] < minest:
                minest = data[j]
                index = j
        temp = data[i]
        data[i] = minest
        data[index] = temp
    data = [str(k) for k in data]
    print " ".join(data)

## 4 快速排序 ##

## 4.1 原理 ##

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做**“分治”**的思想。  
我看到的讲解最清楚的一篇文章是[坐在马桶上看算法：快速排序][Link 1]  
具体步骤如下：  
（1）外循环：令列表第一个元素作为基准点base；  
（2）内循环：设置两个指针 i 和 j ， j 先从后往前找 比base小的数，找到后，i 从前往后找比base 大的元素，直到都找到了，然后交换两个位置的元素；如果还没有找到同时符合条件的元素，却有 i = j ，则有两种情况发生：j 移动到了一个符合条件的位置后， i 也移动过来了，此时可以交换 base 和 i 位置的元素；另一种是，j 一直移动都没有找到符合条件的元素，此时已经到了base，也就是 i 的初始位置，此时也可以交换 i 和base位置的元素，因为他们是同一个元素。综上，只要 i=j ，就可以交换 i 和base的元素。  
（3）一轮结束后，基准点已经移动到了合适的位置：左边的元素比它小，右边的元素比它大，但是左边的元素之间还没有排序，还需要递归的调用刚才的内循环的方法，参数分别为左右两侧的信息。

## 4.2 时间复杂度和空间复杂度 ##

**时间复杂度：**快速排序的交换跨度大于插入排序和冒泡排序的交换跨度，但是如果选取的基准是最大值或者最小值的话，存在一种情况，i 或 j 位置的元素会一直和 base基准元素交换位置，而不是i 和 j 位置交换元素，这样导致快排和之前的相邻元素比较的算法差别不大，所以最坏情况的复杂度是 n 方；最好情况下，每次找到的基准点都可以平均划分后面的元素，时间减少。  
**空间复杂度：**由于每次确定基准点后，都需要对后面的数进行交换，所以空间复杂度为 n 。

## 4.3 python代码 ##

#coding:utf-8
    num = raw_input("请输入要排序的集合，用空格分隔：")
    data = [int(i) for i in num.split()]
    def q_sort(L,left,right):
        if left >= right:
            return
        base = L[left]
        i = left
        j = right
        while i != j:
            while L[j] >= base and i < j:
                j -= 1
            while L[i] <= base and i < j:
                i += 1
            if (i < j):
                temp = L[j]  #交换 i ,j 位置的元素
                L[i] = L[j]
                L[j] = temp
        L[left] = L[i]
        L[i] = base
        if left < right:
            q_sort(L,left,i-1)
            q_sort(L,j+1,right)
    
    q_sort(data,0,len(data)-1)
    data = [str(i) for i in data]
    print " ".join(data)

## 5 归并排序 ##

## 5.1 原理 ##

归并排序也是采用分治的思想实现对n个元素进行排序。具体实现步骤是：  
（1）外循环：将元素集合递归的划分成大致相等的两个子集合，直到不能划分；  
（2）内循环：合并两个有序子集合得到一个大的有序集合，即比较每个元素。在这个过程中，产生一个新的数组b，用于存放排好序的元素集合。

## 5.2 时间复杂度和空间复杂度 ##

**时间复杂度：** 递归的划分元素集合瞎相当于两个一半元素的时间复杂度，而合并和复制操作可在O（n）时间完成，所以T（n） = 2 T(n/2) + O(n)，求解后是O（nlogn）。  
**空间复杂度：**归并的空间复杂度就是那个临时的数组和递归时压入栈的数据占用的空间：n + logn；所以空间复杂度为: O(n)。  
**以时间换空间：** 我看到网上很多blog分享空间复杂度只有O(1)的归并排序法；因为传统的归并排序所消耗的空间主要是在归并函数（把两个有序的函数合并成一个有序的函数），所以如果要让时间复杂度为 O(1) ，那么也只能在归并函数中做文章了。代码就不列出来了，其主要思想就是借助于快速排序（其实就是相当于归并函数被快速排序函数替换了）；这样的方法虽然可以减少内存的消耗，但是却会在时间上带来损失，因为这样时间复杂度却变成了 O(n^2) 了；所以这种方法并不是一个两全其美的idea；

## 5.3 python代码 ##

#coding:utf-8
    def merge(a,left,mid,right):
        #合并两个排好序的数组
        b = []   #空间：O(n)
        i = left
        j = mid + 1
        while i <= mid and j <= right:
            if a[i] <= a[j]:
                b.append(a[i])
                i += 1
            else:
                b.append(a[j])
                j += 1
        if i <= mid:
            for k in a[i:mid+1]:
                b.append(k)
        if j <= right:
            for k in a[mid+1:right+1]:
                b.append(k)
        print "b",b
        return b
    def mergeSort(a,left,right):
        if left < right:
            mid = (left + right)/2
            mergeSort(a,left,mid)  #T(n/2)
            mergeSort(a,mid+1,right)  #T(n/2)
            print "merge",a,left,mid,right
            b = merge(a,left,mid,right)
            for j in range(len(b)):
                a[left + j] = b[j]
        else:
            return
    num = raw_input()
    data = [int(i) for i in num.split()]
    mergeSort(data,0,len(data)-1)
    print data

## 5.4 改进：自然合并排序 ##

## 5.4.1 原理 ##

用1次对集合的扫描找出所有已经排好序的子集合，然后再将相邻的子集合进行两两合并。其中，和归并算法相较，merge步骤是不变的，只是mergeSort方法改变。在极端情况下，如果给定数组有序，那么自然合并算法不需要执行合并步，而mergeSort还需要执行logn次合并。通常情况下，自然合并算法的合并次数较少。

## 5.4.2 python 代码 ##

调式中

## 6 希尔排序（shell 排序） ##

## 6.1 原理 ##

希尔排序是以人名命名的，与shell没有任何关系。它是插入排序的改进版本，由于插入排序是相邻元素之间交换，使得时间较长，因此希尔排序加大交换元素之间的跨度，并且逐次减小跨度。  
具体实现步骤如下：  
（1）外循环：依次所见交换的跨度，跨度公式是：gap = len(a)/2；  
（2）内循环：将位置 i 的元素和位置 i+ gap 的元素比较大小，然后交换；  
（3）执行内外循环结束后，再执行一次插入排序，此时大部分数已经是有序的了，只是调整少部分数的位置。

## 6.2 时间复杂度和空间复杂度 ##

**时间复杂度：**  
**空间复杂度：**

## 6.3 python 代码 ##

#coding:utf-8
    def shellSort(a):
        gap = len(a)/2
        while gap > 0:
            for i in range(0,len(a)-gap):
                if a[i] > a[i+gap]:
                    temp = a[i]
                    a[i] = a[i+gap]
                    a[i+gap] = temp
                else:
                    continue
            gap = gap/2
        j = 1
        while j < len(a):
            if a[j] >= a[j-1]:
                j += 1
                continue
            else:
                k = j
                while k > 0:
                    if a[k] < a[k-1]:
                        temp = a[k]
                        a[k] = a[k-1]
                        a[k-1] = temp
                        k -= 1
                    else:
                        break
    data = raw_input()
    data = [int(i) for i in data.split()]
    shellSort(data)
    print data

## 8 其他排序算法 ##

还有基于树模型的排序算法，二叉树排序和堆排序，都是要结合数据结构知识来完成，正在学习中。

## 9 总结 ##

在这里讲解的六种算法，其中，插入排序，冒泡排序，选择排序都是比较稳定的排序，都是相邻元素比较大小并交换位置，时间复杂度也都是n方，空间复杂度是 1 ；再次基础上做出改进，结合”分治“思想产生了快速排序和归并排序，以空间换时间，增加了元素交换的跨度，时间复杂度是 nlogn，空间复杂度是 n ；在插入排序的基础上，又有希尔排序，也是增加了元素交换位置的跨度，时间复杂度是 nlogn ，空间复杂度 是 1。最后就是基于树模型的排序算法，在排序之前需要构建相应的数据结构，而之前的几种算法都是在数组上（列表）排序，不涉及更复杂的数据结构。  
另一篇讲解排序算法性能的文章是：[常用排序算法的python实现和性能分析][python]  
如果想要在比较模型上继续提高排序速度，在模型本身上没有可以改进的空间，只能使用其他办法——比如刚才提到的空间换时间的方法，使用其他空间存储一些重复的对比，或者使用混合的比较模型。  
事实上，大多数内置的排序算法都是混合型的，我们的目的是加快排序的速度，而不是模型本身。一种广泛采取的排序算法，是在数据量很大的时候，采取快速排序的方式，而在当分组很小的时候，使用其他稳定的排序方法。这样的混合型算法，综合效果是最好的，也就是一般内置排序使用的方法。

[SouthEast]: /images/20220609/afc9aa8f8170422ebb5c22e2194be818.png
[SouthEast 1]: /images/20220609/fe0d10b86c004a9fa952bf185f8cc602.png
[Link 1]: http://developer.51cto.com/art/201403/430986.htm%20%E5%9D%90%E5%9C%A8%E9%A9%AC%E6%A1%B6%E4%B8%8A%E7%9C%8B%E7%AE%97%E6%B3%95%EF%BC%9A%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
[python]: http://www.2cto.com/kf/201403/287405.html%20%E5%B8%B8%E7%94%A8%E6%8E%92%E5%BA%8F%E7%AE%97%E6%B3%95%E7%9A%84python%E5%AE%9E%E7%8E%B0%E5%92%8C%E6%80%A7%E8%83%BD%E5%88%86%E6%9E%90