排序算法的python实现（一）

排序算法是算法中最基本的算法，本文通过python实现选择排序、冒泡排序、插入排序以及各种改进方法,后台回复“代码”获取代码文件。部分动图出自 https://github.com/hustcc/JS-Sorting-Algorithm

本文所有的排序方法都在列表上进行操作，首先定义交换任意两项位置的函数swap。

def swap(x,i,j):
    """
    交换x的i,j位置元素
    """
    temp = x[i]
    x[i] = x[j]
    x[j] = temp

1、选择排序 排序算法的逻辑非常简单，首先搜索整个列表，找到最小项的位置，如果该位置不是列表的第1项，就交换这两个位置的元素。然后从列表的第2个元素开始，重复上述过程，直到算法达到整个过程的最后一个位置，图形解释如下

代码如下 def selectionSort(x): i = 0 while i < len(x) - 1: minindex = i j = i + 1 while j < len(x) : if x[minindex] > x[j]: minindex = j j+= 1 if minindex != i: swap(x,i,minindex) i+= 1 return x 函数包括一个嵌套的循环，对于大小为n的列表，外围的循环执行n-1次，内部循环的次数从n-1递减到1，因此，选择排序在各种情况下的复杂度为平方阶，运行结果如下

2、二元选择排序法（选择排序改进） 选择排序法每轮只找最小值，效率较低，可以考虑每次同时寻找最小值和最大值，并且在某一轮如果最小值与最大值相同，说明剩下的数字都相同，可以直接结束。 此外，与选择排序不同的是，需要考虑到如果第i轮里，恰好第i个数就是最大值时，先交换minindex和i之后，最大值的下标变成了minindex，这时候应该交换minindex和n-i-1，而不是maxindex和n-i-1。代码如下 def selectionSort_1(x): i = 0 while i <= len(x) // 2: minindex = i maxindex = i j = i + 1 while j < len(x) - i : if x[minindex] > x[j]: minindex = j if x[maxindex] < x[j]: maxindex = j j+= 1 if x[minindex] == x[maxindex]: return x if minindex != i: swap(x,i,minindex) if maxindex != len(x) - 1 - i : if maxindex != i: swap(x,len(x) - 1 - i,maxindex) else: swap(x,len(x) - 1 - i, minindex) i+= 1 return x 3、冒泡排序 冒泡排序从列表的开头处开始，逐个比较一对数据项，如果顺序不对就交换两项位置，直到移动到列表的末尾。这个过程的效果就是将最大的项以冒泡的方式排到算法的末尾。然后算法从列表开头到倒数第二项重复这一过程，依次类推，图形解释如下。

代码如下 def BubbleSort(x): j = len(x) - 1 while j > 0: i = 0 while i < j: if x[i] > x[i + 1]: swap(x,i,i+1) i += 1 j -= 1 return x 类似选择排序，冒泡排序也是一个嵌套的循环，如果列表是已经排好序的，冒泡排序不会执行任何的交换，在最坏的情况下，为平方阶复杂度。 4、冒泡排序法改进 在最好的情况下，冒泡排序法依然会执行每个循环但不进行任何操作，可以设定一个标记判断冒泡排序法在一次内层循环中是否进行了交换，如果没有，说明算法已经使排好序的，就可以直接返回，不过这种方法只是对最好的情况进行了改进，代码如下 def BubbleSort_1(x): j = len(x) - 1 while j > 0 : flag = False i = 0 while i < j: if x[i] > x[i + 1]: swap(x,i,i+1) flag = True i += 1 if not flag: return x j -= 1 return x 5、双向冒泡排序法 冒泡排序法存在所谓的“乌龟问题”，假设我们需要将序列按照升序排序。序列中的较小的数字又大量存在于序列的尾部，这样会让小数字在向前移动得很缓慢，因此针对这一问题，产生了双向冒泡排序法，也称鸡尾酒排序法。 双向冒泡排序法由两个方向同时进行冒泡，首先由左向右为大元素移动方向，从右向左为小元素移动方向，然后每个元素都依次执行。在第i次移动后，前i个和后i个元素都放到了正确的位置。图形解释如下

代码如下 def BidirectionalBubbleSort(x): j = 0 while j <= len(x)//2: flag = False for i in range(j ,len(x) - j - 1): if x[i]>x[i+1]: swap(x,i,i+1) flag=True for i in range(len(x)- 1 - j,j,-1): if x[i]<x[i-1]: swap(x,i,i-1) flag=True if not flag: return x j += 1 return x 实验结果如下

6、插入排序法

插入排序法类似打牌时候摸扑克牌整理顺序的过程，逻辑如下：

• 在第i轮通过列表的时候（i从1到n-1），第i项应该插入到列表的前i个项中的正确位置；
• 在第i轮之后，前i个项应该是排好序的；

图形解释如下

代码如下

def InsertionSort(x):
    i = 1
    while i < len(x):
        j = i - 1
        item = x[i]
        while j >= 0 and item < x[j]:
            x[j + 1] = x[j]
            j -= 1
        x[j + 1] = item
        i += 1   
    return x

7、希尔排序（插入排序改进）

插入排序对于几乎已经排好序的数据操作时，效率很高，但平均来说，插入排序很低效，因为插入排序每次只能将数据移动一位，希尔排序是在此基础上对于插入排序的一种改进。

希尔算法的逻辑是，先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序，具体步骤如下：

1. 设定一个较大间隔gap，对所有间隔为gap的数据通过插入排序法进行排序；
2. 执行完之后根据某种逻辑缩小gap（代码中采用除以3取整的办法），重复上述过程，直到gap = 0。

通过以上步骤，最终得到的列表是排好序的，并且可以证明，这种方法的平均的复杂度是O(nlogn)。代码如下

def HashSort(x):
    gap = round(len(x)*2/3)
    while gap > 0 :    
        print('gap =  ',gap )
        i = gap
        while i < len(x):
            j = i - gap
            item = x[i]
            while j >= 0 and item < x[j]:
                x[j + gap] = x[j]
                j -= gap
            x[j + gap] = item
            i += 1
        gap = round(gap/3)
    return x

这里print每次循环中gap的值，可以直观看到gap的变化过程，实验如下

关于各种方法效率的比较不再说明，其余排序方法下期再见，代码有问题的地方请指出，欢迎加群交流！