在计算科学中，一个排序算法是一种能将一串数据依照特定排序方式进行排列的一种算法。最常用到的排序方式是数值顺序以及字典顺序。有效的排序算法在一些算法中是重要的。排序算法也用在处理文字数据以及产生人类可读的输出结果。

基本上，排序算法的输出必须遵守下列两个原则：1. 输出结果为递增序列（递增是针对所需的排序顺序而言） 2.输出结果是原输入的一种排列、或是重组

经典的10大排序算法可以被分为两大类

非线性时间比较类排序：通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。

线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。

《Python实现经典排序算法(1)》

它们的时间空间复杂度为

《Python实现经典排序算法(1)》

下面详细介绍各排序算法及python实现

1.冒泡排序(Bubble Sort)

冒泡排序是一种简单的排序算法。它重复地走访过要排序的数组，一次比较两个元素，如果它们的顺序有误就把它们交换过来。重复地进行数组长度的次数直到没有再需要交换，退出循环排序完成。算法的名字由来是因为越小的元素会经由交换像水里的气泡一样慢慢地“浮”到数列的顶端。

1.1 算法描述

比较相邻的元素。如果第一个比第二个大，就交换它们两个；

对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；

针对所有的元素重复以上的步骤，除了最后一个；

重复上面步骤，直到没有交换发生，排序完成。

1.2 动图演示

《Python实现经典排序算法(1)》

1.3 Python3代码实现

    import numpy as np
    import random

    def bubble_sort(ownlist):
        n = len(ownlist)

        # Traverse through all array elements
        for i in range(n):

            # Last i elements are already in place
            for j in range(0, n-i-1):

                # traverse the array from 0 to n-i-1
                # Swap if the element found is greater
                # than the next element
                if ownlist[j] > ownlist[j+1] :
                    ownlist[j], ownlist[j+1] = ownlist[j+1], ownlist[j]
            print(ownlist)

    a = random.sample(list(np.arange(100)),20)
    bubble_sort(a)

2.选择排序(Selection Sort)

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。

初始状态：无序区为[1..n]，有序区为空；

第i趟排序(i=1,2,3…n-1)开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录交换，使R[1..i]和R[i+1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区；

n-1次循环结束，数组变得有序化。

2.2 动图演示

《Python实现经典排序算法(1)》

2.3 Python3代码实现

    import numpy as np
    import random

    def selection_sort(ownlist):
        n = len(ownlist)

        for i in range(n):

            minn = i
            for j in range(i, n):

                if ownlist[j] < ownlist[minn] :
                    minn = j
            if minn!=i:
                ownlist[i],ownlist[minn] = ownlist[minn],ownlist[i]
            print(ownlist)

    a = random.sample(list(np.arange(100)),20)
    selection_sort(a)

3.插入排序(Insertion Sort)

插入排序(Insertion-Sort)是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

3.1 算法描述

1.从第一个元素开始，该元素可以认为已经被排序；

2.取出下一个元素，在已经排序的元素序列中从后向前扫描；如果该元素（已排序）大于新元素，将该元素移到下一位置；重复直到找到已排序的元素小于或者等于新元素的位置；将新元素插入到该位置；

3重复步骤。

3.2 动图演示

《Python实现经典排序算法(1)》

3.3 Python3代码实现

    import numpy as np
    import random
    def insertion_sort(ownlist):
        for index in range(1,len(ownlist)):

            currentvalue = ownlist[index]
            position = index

            while position>0 and ownlist[position-1]>currentvalue:
                ownlist[position]=ownlist[position-1]
                position = position-1

            ownlist[position]=currentvalue
            print(ownlist)
    a = random.sample(list(np.arange(100)),20)
    insertion_sort(a)

4.希尔排序(Shell Sort)

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。希尔排序是基于插入排序的以下两点性质而提出改进方法的：插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位.

4.1 算法描述

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，具体算法描述：

  • 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1；
  • 按增量序列个数k，对序列进行k 趟排序；
  • 每趟排序，根据对应的增量ti，将待排序列分割成若干长度为m 的子序列，分别对各子表进行直接插入排序。仅增量因子为1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

4.2 动图演示

《Python实现经典排序算法(1)》

4.3 Python3代码实现

    import numpy as np
    import random
    def shell_sort(ownlist): 

        n = len(ownlist) 
        gap = n//2
        while gap > 0: 

            for i in range(gap,n): 

                temp = ownlist[i] 

                j = i 
                while  j >= gap and ownlist[j-gap] >temp: 
                    ownlist[j] = ownlist[j-gap] 
                    j -= gap 

                ownlist[j] = temp 
            gap //= 2
            print(ownlist)
    a = random.sample(list(np.arange(100)),20)
    print(a)
    shell_sort(a)

5.归并排序(Merge Sort)

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。

5.1 算法描述

把长度为n的输入序列分成两个长度为n/2的子序列；

对这两个子序列分别采用归并排序；

将两个排序好的子序列合并成一个最终的排序序列

5.2 动图演示

《Python实现经典排序算法(1)》

5.3 Python3代码实现

    import numpy as np
    import random
    def merge_sort(ownlist):
        print("分割 ",ownlist)
        if len(ownlist)>1:
            mid = len(ownlist)//2
            lefthalf = ownlist[:mid]
            righthalf = ownlist[mid:]

            merge_sort(lefthalf)
            merge_sort(righthalf)

            i=0 #left
            j=0  #right
            k=0  #
            while i < len(lefthalf) and j < len(righthalf):
                if lefthalf[i] < righthalf[j]:
                    ownlist[k]=lefthalf[i]
                    i=i+1
                else:
                    ownlist[k]=righthalf[j]
                    j=j+1
                k=k+1

            while i < len(lefthalf):
                ownlist[k]=lefthalf[i]
                i=i+1
                k=k+1

            while j < len(righthalf):
                ownlist[k]=righthalf[j]
                j=j+1
                k=k+1
        print("合并 ",ownlist)
    a = random.sample(list(np.arange(100)),20)
    print(a)
    merge_sort(a)

总结：

这篇文章介绍了5中排序算法的原理以及python3算法实现，下一篇将会就剩下的快速排序，堆排序，计数排序，桶排序，基数排序进行详细分析及pythn3实现代码.