程序员必备排序算法（1）

一、写在前面

排序算法算是比较简单面试过程中遇到最多的算法，一般我们所说的排序算法往往指的是内部排序算法，即数据记录在内存中进行排序。

排序算法大体可分为两种：

　　　　一种是非线性时间比较类排序，通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此称为非线性时间比较类排序。主要有：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序等。

　　　　另一种是线性时间非比较类排序：不通过比较来决定元素间的相对次序，它可以突破基于比较排序的时间下界，以线性时间运行，因此称为线性时间非比较类排序。主要有：计数排序，基数排序，桶排序等。

今天主要给大家介绍比较类型排序。

二、算法详解

1、冒泡排序（Bubble Sort）

冒泡排序是一种非常简单的排序算法，也是我所学习编程以来的第一个排序算法。它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

1.1 算法描述

• 比较相邻的元素。如果第一个比第二个大，就交换它们两个；
• 对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对，这样在最后的元素应该会是最大的数；
• 针对所有的元素重复以上的步骤，除了最后一个；
• 重复步骤1~3，直到排序完成。

1.2 动图演示

1.3 代码实现

 1def bubbleSort(nums):
 2    for i in range(len(nums)-1):    # 这个循环负责设置冒泡排序进行的次数
 3        for j in range(len(nums)-i-1):  # ｊ为列表下标
 4            if nums[j] > nums[j+1]:
 5                nums[j], nums[j+1] = nums[j+1], nums[j]
 6    return nums
 7
 8nums = [5,2,45,6,8,2,1]
 9
10print (bubbleSort(nums))

2、选择排序（Selection Sort）

　选择排序也是一种简单直观的排序算法。它的工作原理很容易理解：初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。

　　注意选择排序与冒泡排序的区别：冒泡排序通过依次交换相邻两个顺序不合法的元素位置，从而将当前最小（大）元素放到合适的位置；而选择排序每遍历一次都记住了当前最小（大）元素的位置，最后仅需一次交换操作即可将其放到合适的位置。

2.1 算法描述

n个记录的直接选择排序可经过n-1趟直接选择排序得到有序结果。具体算法描述如下：

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

2.2 动图演示

2.3 代码实现

 1s = [3, 4, 1, 6, 2, 9, 7, 0, 8, 5]
 2
 3# select_sort
 4for i in range(0, len(s) - 1):
 5    index = i
 6    for j in range(i + 1, len(s)):
 7        if s[index] > s[j]:
 8            index = j
 9    s[i], s[index] = s[index], s[i]
10
11# print sort result.
12for m in range(0, len(s)):
13    print(s[m])

3、插入排序（Insertion Sort）

插入排序（Insertion Sort）的算法描述是一种简单直观的排序算法。它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。在从后向前扫描过程中，需要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

3.1 算法描述

一般来说，插入排序都采用in-place在数组上实现。具体算法描述如下：

• 从第一个元素开始，该元素可以认为已经被排序；
• 取出下一个元素，在已经排序的元素序列中从后向前扫描；
• 如果该元素（已排序）大于新元素，将该元素移到下一位置；
• 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
• 将新元素插入到该位置后；
• 重复步骤2~5。

3.2 动图演示

3.3 代码实现

第一种：先找到元素要插入的位置，然后将从该位置（包括）到待插入元素位置之间的元素都向后移动一位，最后将元素插入该位置。代码如下：

 1 def inertsort(l):  #参数的传入，当想传入的是一个list时，直接传入一个变量就行了
 2    N=len(l)
 3    for x in range(1,N):
 4        a,b=x,x
 5        n=l[x]
 6        while n<l[a-1] and a-1>=0:
 7            a=a-1
 8            if a-1<0:
 9                a=0 
10        while b>a:
11            l[b]=l[b-1]
12            b=b-1
13        l[a]=n
14
15l=[1,3,2,8,5,3,1]
16inertsort(l)
17print (l)

第二种思想是：将待插入元素与其前一个元素进行比较，若小于，则将前一个元素后移一位，在将带插入元素与前前一位进行比较，若小于，则将前前一位往后移，如此操作直到遇到小于待插入元素的位置，插入到该位后一位（此位已经在上一步后移了），代码如下：

 1def insertsort(list):
 2    N=len(l)
 3    for x in range(1,N):
 4        key=list[x]
 5        a=x
 6        while key<list[a-1]:
 7            l[a]=l[a-1]
 8            a=a-1
 9            if a-1<0:
10                break
11        list[a]=key
12
13l=[1,3,2,8,5,3,1]
14insertsort(l)
15print (l)

4、希尔排序（Shell Sort）

希尔排序，也叫递减增量排序，是插入排序的一种更高效的改进版本。希尔排序是不稳定的排序算法。

　　希尔排序是基于插入排序的以下两点性质而提出改进方法的：

• 插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率
• 但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位

4.1 算法描述

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

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

4.2 动图演示

4.3 代码实现

 1L = [1, 3, 2, 32, 5, 4]
 2def Shell_sort(L):
 3    step = len(L)//2
 4    while step > 0:
 5        for i in range(step,len(L)):            #在索引为step到len（L）上，比较L[i]和L[i-step]的大小
 6            while(i >= step and L[i] < L[i-step]):      #这里可以调整step从小到大或者从大到小排列
 7                L[i],L[i-step] = L[i-step],L[i]
 8                i -= step
 9        step //= 2
10    print (L)
11Shell_sort(L)

提示：

TypeError:

'float' object cannot be interpreted as an integer

Python3.0中" / "就一定表示 浮点数除法，返回浮点结果;" // "表示整数除法。

5、归并排序（Merge Sort）

归并排序是创建在归并操作上的一种有效的排序算法，1945年由冯·诺伊曼首次提出。

　　归并排序的实现分为递归实现与非递归(迭代)实现。递归实现的归并排序是算法设计中分治策略的典型应用，我们将一个大问题分割成小问题分别解决，然后用所有小问题的答案来解决整个大问题。非递归(迭代)实现的归并排序首先进行是两两归并，然后四四归并，然后是八八归并，一直下去直到归并了整个数组。

　　归并排序算法主要依赖归并(Merge)操作。归并操作指的是将两个已经排序的序列合并成一个序列的操作。

5.1 算法描述

• 把长度为n的输入序列分成两个长度为n/2的子序列；
• 对这两个子序列分别采用归并排序；
• 将两个排序好的子序列合并成一个最终的排序序列。

5.2 动图演示

5.3 代码实现

 1def merge(a, b):
 2    c = []
 3    h = j = 0
 4    while j < len(a) and h < len(b):
 5        if a[j] < b[h]:
 6            c.append(a[j])
 7            j += 1
 8        else:
 9            c.append(b[h])
10            h += 1
11
12    if j == len(a):
13        for i in b[h:]:
14            c.append(i)
15    else:
16        for i in a[j:]:
17            c.append(i)
18
19    return c
20
21
22def merge_sort(lists):
23    if len(lists) <= 1:
24        return lists
25    middle = len(lists)//2
26    left = merge_sort(lists[:middle])
27    right = merge_sort(lists[middle:])
28    return merge(left, right)
29
30
31if __name__ == '__main__':
32    a = [4, 7, 8, 3, 5, 9]
33    print (merge_sort(a))

以上就是今天的介绍，下篇推送会介绍非比较类型排序，文中引用的图片均来自网络。