Python实现七种经典排序算法。

一、冒泡排序

介绍

• 冒泡排序是排序算法中较为简单的一种，英文称为 Bubble Sort。它遍历所有的数据，每次对相邻元素进行两两比较，如果顺序和预先规定的顺序不一致，则进行位置交换；这样一次遍历会将最大或最小的数据上浮到顶端，之后再重复同样的操作，直到所有的数据有序。
• 如果有n个数据，那么需要的比较次数，所以当数据量很大时，冒泡算法的效率并不高。
• 当输入的数据是反序时，花的时间最长，当输入的数据是正序时，时间最短。

步骤

1. 从前往后依次比较相邻的元素。如果前一个元素比后一个二元素大，交换二者位置。（数列遍历一遍后，最大数被移动到末尾)。
2. 重复步骤1（已确定位置的数据不需要再参与排序）。
3. 完成排序。

实现

动画演示

python代码实现

 

    def bubble_sort(alist):
        for i in range(len(alist)-1,0,-1):
            for j in range(i):
                if alist[j]>alist[j+1]:
                    alist[j],alist[j+1]=alist[j+1],alist[j]

优化：某一趟遍历如果没有数据交换，则说明已经排好序了，因此不用再进行迭代了。用一个标记记录这个状态即可。设置标志位flag，如果发生了交换flag设置为true；如果没有交换就设置为false。 这样当一轮比较结束后如果flag仍为false，即：这一轮没有发生交换，说明数据的顺序已经排好，没有必要继续进行下去,排序结束。

二、选择排序

介绍

• 选择排序简单直观，英文称为 Selection Sort，先在数据中找出最大或最小的元素，放到序列的起始；然后再从余下的数据中继续寻找最大或最小的元素，依次放到排序序列中，直到所有数据样本排序完成。很显然，选择排序也是一个费时的排序算法，无论什么数据，都需要 O(n²) 的时间复杂度，不适宜大量数据的排序。
• 选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上，则它不会被移动。选择排序每次交换一对元素，它们当中至少有一个将被移到其最终位置上，因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中，选择排序属于非常好的一种。

步骤

1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置 。
2. 再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3. 重复步骤2，直到所有元素均排序完毕。

实现

动画演示

python代码实现

def select_sort(alist)：
    for i in range(len(alist)-1):
        min_index=i
        for j in range(i+1,len(alist)):
            if alist[j]<alist[min_index]:
               min_index=j
        if min_index!=i:
             alist[i],alist[min_index] = alist[min_index],alsit[i]

三、插入排序

介绍

• 插入排序英文称为 Insertion Sort，它通过构建有序序列，对于未排序的数据序列，在已排序序列中从后向前扫描，找到相应的位置并插入，类似打扑克牌时的码牌。插入排序有一种优化的算法，可以进行拆半插入。
• 基本思路是先将待排序序列的第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列；然后从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置，直到所有数据都完成排序；如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。

步骤

1. 将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面）。

实现

动画演示

python代码实现

def insert_sort(alist):
    for i in range(1,len(alsit)):
        for j in range(i,0,-1):
            if alist[j]<alist[j-1]:
                alist[j-1],alist[j]=alist[j],alist[j-1]

四、快速排序

介绍

• 快速排序，英文称为 Quicksort，又称划分交换排序 partition-exchange sort，简称快排。
• 快速排序使用分治策略来把一个序列分为两个子序列。首先从数列中挑出一个元素，并将这个元素称为「基准」pivot。重新排序数列，所有比基准值小的元素摆放在基准前面，所有比基准值大的元素摆在基准后面，相同的数可以到任何一边。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区partition操作。之后，在子序列中继续重复这个方法，直到最后整个数据序列排序完成。
• 在平均状况下，排序n个项目要 O(nlogn) 次比较。在最坏状况下则需要 O(n²) 次比较，但这种状况并不常见。事实上，快速排序通常明显比其他算法更快，因为它的内部循环可以在大部分的架构上很有效率地达成。

步骤

1. 从数列中挑出一个元素，称为”基准”(pivot)。
2. 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区结束之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。
3. 递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

递归的最底部情形，是数列的大小是零或一，也就是永远都已经被排序好了。虽然一直递归下去，但是这个算法总会结束，因为在每次的迭代（iteration）中，它至少会把一个元素摆到它最后的位置去。

实现

动画演示

python代码实现

def quick_sort(alist,start,end):
    if start>=end:
        return
    pivot= alist[start]
    low = start
    high = end
    while low < high:
        while low < high and pivot < alist[high]:
            high-=1
       alist[low] = alist[high]
       while low < high and alist[low] < pivot:
           low+=1
       alist[high] = alist[low]
   alsit[low] = pivot
   quick_sort(alist,start,low-1)
   quick_sort(alist,low+1,end)

五、希尔排序

介绍

• 希尔排序也称递减增量排序，是插入排序的一种改进版本，英文称为 Shell Sort，效率虽高，但它是一种不稳定的排序算法。
• 插入排序在对几乎已经排好序的数据操作时，效果是非常好的；但是插入排序每次只能移动一位数据，因此插入排序效率比较低。
• 希尔排序在插入排序的基础上进行了改进，它的基本思路是先将整个数据序列分割成若干子序列分别进行直接插入排序，待整个序列中的记录基本有序时，再对全部数据进行依次直接插入排序。

步骤

1. 将元素分为n列，并对每列进行插入排序。
2. 将n列元素按行进行合并。
3. 重复步骤1-2，其中元素的列数为上次的一半。

实现

动画演示

python代码实现

def shell_sort(alist):
    gap=len(alist)//2
    while gap>0:
        for i in range(gap,len(alist)):
            j=i
            while (j-gap)>=0 and alist[j-gap]>alist[j]:
                alist[j-gap],alsit[j]=alist[j],alist[j-gap]
                j-=gap
         gap//=2 

六、归并排序

介绍

• 归并排序英文称为 Merge Sort，它是采用分治法的一个非常典型的应用。归并排序的思想就是先递归分解数组，再合并数组。
• 将数组分解最小之后，然后合并两个有序数组，基本思路是比较两个数组的最前面的数，谁小就先取谁，取了后相应的指针就往后移一位。然后再比较，直至一个数组为空，最后把另一个数组的剩余部分复制过来即可。
• 归并排序严格遵循从左到右或从右到左的顺序合并子数据序列, 它不会改变相同数据之间的相对顺序, 因此归并排序是一种稳定的排序算法。

步骤

1. 归分解，将数组分解成left和right。如果这两个数组内部数据是有序的（转向步骤2-4）；如果无序，则对数组进行二分，直至分解出的小组只有一个元素，此时认为该小组内部有序。
2. 合并两个有序数组，比较两个数组的最前面的数，谁小就先取谁，该数组的指针往后移一位。
3. 重复步骤2，直至一个数组为空。
4. 最后把另一个数组的剩余部分复制过来即可。

实现

动画演示

python代码实现

def merge_sort(alist):
    if len(alist)<=1:
        return alist
    mid = len(alist)//2
    left=merge_sort(alsit[:mid])
    right=merge_sort(alist[mid:])
    return sort(left,right)
def sort(left,right):
    l,r=0,0
    result=[]
    while l<len(left) and r<len(right):
        if left[l]<=right[r]:
            result.append(left[l])
            l+=1
        else:
            result.append(right[r])
            r+=1
    result+=left[l:]
    result+=right[r:]
return result

七、堆排序

介绍

• 堆排序，英文称 Heapsort，是指利用堆这种数据结构所设计的一种排序算法。堆排序在 top K问题中使用比较频繁。堆排序是采用二叉堆的数据结构来实现的，虽然实质上还是一维数组。二叉堆是一个近似完全二叉树。
• 二叉堆具有以下性质：
  • 父节点的键值总是大于或等于（小于或等于）任何一个子节点的键值。
  • 每个节点的左右子树都是一个二叉堆（都是最大堆或最小堆）。

步骤

1. 根据初始数组取构建一个完全二叉树，保证所有的父节点比子节点的数值大。
2. 每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为最大堆。

实现

动画演示

python代码实现

def heap_sort(alist):
    n = len(alist)
    first = int(n/2-1)
    for start in range(first,-1,-1):
        max_heapify(alist,start,n-1)
    for end in range(n-1,0,-1):
        alist[end],alist[0]=alist[0],alist[end]
        max_heapify(alist,0,end-1)
    return alsit

def max_heapify(alist,start,end):
    root = start
    while True:
        child = root*2+1
        if child>end :
            break
        if child+1<=end and alist[child]<alist[child+1]:
            child+=1
        if alist[root]<alist[child]:
            alist[root],alist[child]=alist[child],alist[root]
            root=child
        else:
            break

总结：常见排序算法效率比较

参考
https://github.com/hustcc/JS-Sorting-Algorithm