（一）排序算法

排序算法性能比较

1.插入排序算法

把n个待排序的元素看成为一个有序表和一个无序表。开始时有序表中只包含1个元素，无序表中包含有n-1个元素，排序过程中每次从无序表中取出第一个元素，将它插入到有序表中的适当位置，使之成为新的有序表，重复n-1次可完成排序过程。

原理：

• 从第二个元素开始和前面的元素进行比较，如果前面的元素比当前元素大，则将前面元素 后移，当前元素依次往前，直到找到比它小或等于它的元素插入在其后面
• 然后选择第三个元素，重复上述操作，进行插入
• 依次选择到最后一个元素，插入后即完成所有排序

举例

数列[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]需要使用插入排序，我们来看看使用插入排序的详细步骤：

• 首先第二个元素99和前面的元素11比较，99>11，第一轮完了，列表是 1 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
• 然后，33作为比较元素，和前面的元素99比较，11<33<99交换位置，33插入到11和99之间，列表为 1 [11, 33, 99, 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
• 接着，33<69<99交换位置，列表变为 1 [11, 33, 69, 99, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
• 以此类推，69<77<99,77插入到69和99之间，列表变为 1 [11, 33, 69, 77, 99, 88, 55, 11, 33, 36,39, 66, 44, 22]
• 77<88<99, 88插入到77和99之间，列表变为 1 [11, 33, 69, 77, 88, 99, 55, 11, 33, 36,39, 66, 44, 22]
• 33<55<69<77<88<99,55插入到33和69之间，列表变为 1 [11, 33, 69, 77, 88, 99, 55, 11, 33, 36,39, 66, 44, 22]
• .......
• 最终得到列表 1 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

python实现

def insert_sort(arr):
    # 第一层for表示循环插入的遍数
    for i in range(1,len(arr)):
        # 设置当前需要插入的元素
        current = arr[i]
        # 与当前元素比较的比较元素
        pre_index = i - 1
        while pre_index >= 0 and arr[pre_index] > current:
            # 当比较元素大于当前元素则把比较元素后移
            arr[pre_index+1] = arr[pre_index]
            # 往前选择下一个比较元素
            pre_index -= 1
        # 当比较元素小于当前元素，则将当前元素插入在 其后面
        arr[pre_index+1] = current
    return arr

2.选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，所以称为：选择排序。

原理

• 设第一个元素为比较元素，依次和后面的元素比较，比较完所有元素找到最小的元素，将它和第一个元素互换
• 重复上述操作，我们找出第二小的元素和第二个位置的元素互换，以此类推找出剩余最小元素将它换到前面，即完成排序

举例

数列[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]需要使用插入排序，我们来看看使用选择排序的详细步骤：

1、首先11作为比较元素和列表后面的所有元素比较，找到最小的11，并放在第一位，第一轮完了，列表是 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]
2、然后，99作为比较元素，和后面的元素[33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]作比较，找到最小的11，和第二位元素99交换位置，即第二轮比较完后，列表为 [11, 11, 33 , 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 22]
3、第三轮比较完，22最小，和第三个元素33交换位置，列表变为 [11, 11, 22, 69, 77, 88, 55, 99, 33, 36,39, 66, 44, 33]
4、最终得到列表 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

python实现

def selection_sort(arr):
    # 第一层for表示循环选择的遍数
    for i in range(len(arr)-1):
        # 将起始元素设为最小元素
        min_index = i
        # 第二层for表示最小元素和后面的元素逐个比较
        for j in range(i+1,len(arr)):
            if arr[j] < arr[min_index]:
                # 如果当前元素比最小元素小，则把当前元素角标记为最小元素角标
                min_index = j
        # 查找一遍后将最小元素与起始元素互换
        temp = arr[min_index]
        arr[min_index]=arr[i]
        arr[i] = temp
    return arr

3.冒泡排序

重复地走访过要排序的元素列，依次比较两个相邻的元素，一层一层的将较大的元素往后移动，其现象和气泡在上升过程中慢慢变大类似，故成为冒泡排序。

原理

• 从第一个和第二个开始比较，如果第一个比第二个大，则交换位置，然后比较第二个和第三个，逐渐往后
• 经过第一轮后最大的元素已经排在最后，所以重复上述操作的话第二大的则会排在倒数第二的位置。
• 那重复上述操作n-1次即可完成排序，因为最后一次只有一个元素所以不需要比较

举例

举个例子，假设我现在有一个数列需要使用冒泡来排序 [11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]，我们来看看使用冒泡的详细步骤：

• 首先11和99比较大小，99大，99继续和后面的作比较，直到最后一个元素，第一轮完了，列表是 [11, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22, 99]
• 然后，重复第一轮操作，即第二轮比较列表是 [11, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22, 99]，
• 比较完后，列表为 [11, 33 , 69, 77, 55, 11, 33, 36,39, 66, 44, 22, , 88，99]
• 以此类推，最终得到列表 [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

python实现

def bubble_sort(arr):
    # 第一层for表示循环的遍数
    for i in range(len(arr)-1):
        # 第二层for表示具体比较哪两个元素
        for j in range(len(arr)-1-i):
            if a[j] > a[j+1]:
                # 如果前面的大于后面的，则交换这两个元素的位置
                temp = a[j]
                a[j] = a[j+1]
                a[j+1] = temp
    return arr

4.快速排序（重点）

通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。

原理

• 在数列之中，选择一个元素作为”基准”（pivot），或者叫比较值。
• 数列中所有元素都和这个基准值进行比较，如果比基准值小就移到基准值的左边，如果比基准值大就移到基准值的右边
• 以基准值左右两边的子列作为新数列，不断重复第一步和第二步，直到所有子集只剩下一个元素为止。

举例

举个例子，假设我现在有一个数列需要使用快排来排序：[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]，我们来看看使用快排的详细步骤：

• 选取中间的66作为基准值（基准值可以随便选）
• 数列从第一个元素11开始和基准值66进行比较，小于基准值，那么将它放入左边的分区中，第二个元素99比基准值66大，把它放入右边的分区中。
• 然后依次对左右两个分区进行再分区，直到最后只有一个元素
• 分解完成再一层一层返回，返回规则是：左边分区+基准值+右边分区

python实现

def quick_sort(arr):
    if len(arr) < 2:
        return arr
    mid = arr[len(arr)//2]
    left = []
    right = []
    arr.remove(mid)
    for item in arr:
        if item >= mid:
            right.append(item)
        else:
            left.append(item)
    return quick_sort(left) + [mid] + quick_sort(right)

5.希尔排序

先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

原理

希尔排序

• 计算一个增量（间隔）值
• 对元素进行增量元素进行比较，比如增量值为7，那么就对0,7,14,21…个元素进行插入排序
• 然后对1,8,15…进行排序，依次递增进行排序
• 所有元素排序完后，缩小增量比如为3，然后又重复上述第2，3步
• 最后缩小增量至1时，数列已经基本有序，最后一遍普通插入即可

举例

举个例子，假设我现在有一个数列需要使用快排来排序：[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]，我们来看看使用希尔排序的详细步骤：

• 首先，gap = length / 2=7，数组分为7组
  [11, 11],[ 99 , 33], [33, 36], [69, 39],[ 77, 66],[88, 44], [55, 22]
• 然后，对7组分别插入排序，像33,39,66,44,22这些元素被调到前面，
  [11, 11],[ 33 , 99], [33, 36], [39, 69],[ 66, 77],[44, 88], [22, 55]
• 接着，数组变为
  [11, 11,33 , 99, 33, 36, 39, 69, 66, 77,44, 88, 22, 55]
  gap = length / 2=3，数组分为3组，
  [11,99,39,77,22],[11,33,69,44,55],[33,36,66,88]
• 以此类推，gap = length / 2=1列表变为
  [11,22,39,77,99,11,33,44,55,69,33,36,66,88]
• 最终对数组微调，得到列表
  [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

python实现

def sheel_sort(arr):
    gap = len(arr) // 2
    while gap > 0:
        for i in range(gap,len(arr)):
            j = i
            current = a[i]
            while j - gap >=0 and current < arr[j - gap]:
                arr[j] = arr[j - gap]
                j -= gap
            a[j] = current
        gap = gap //2
    return arr

6.归并排序

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。归并排序适用于子序列有序的数据排序。

原理

• 将一个序列从中间位置分成两个序列；
• 在将这两个子序列按照第一步继续二分下去；

• 直到所有子序列的长度都为1，也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。

  
  归并排序

举例

举个例子，假设我现在有一个数列需要使用快排来排序：[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]，我们来看看使用归并排序的详细步骤：

1.对以下数组进行归并排序：　
[11, 99, 33 , 69, 77, 88, 55, 11, 33, 36,39, 66, 44, 22]

2. 首先，进行数组分组，即
   [11, 99, 33 , 69, 77, 88, 55], [ 11, 33, 36,39, 66, 44, 22]
   [11, 99, 33] , [69, 77, 88, 55], [ 11, 33, 36], [39, 66, 44, 22]
   [11], [99, 33] , [69, 77], [88, 55],[ 11], [33, 36],[39, 66], [44, 22]
   直到所有子序列的长度都为1，也就是不可以再二分截止。
   [11], [99], [33] , [69], [77], [88], [55],[ 11], [33], [36],[39], [66], [44], [22]
3. 这时候再两两合并成一个有序序列即可。
   [11],[33,99],[69,77],[55,88],[11],[33,36],[39,66],[22,44]
   [11,33,99],[55,69,77,88],[11,33,36],[22,39,44,66]
   [11,33,55,69,77,88,99],[11,22,33,36,39,44,66]
   4、最终排序
   [11, 11, 22, 33, 33, 36, 39, 44, 55, 66, 69, 77, 88, 99]

python实现

def merge_sor(arr):
    if len(arr) == 1:
        return arr
    mid = len(arr) // 2
    left = arr[:mid]
    right = arr[mid:]
    return merge(merge_sort(left),merge_sort(right))

def merge(left,right):
    result = []
    while len(left)>0 and len(right) > 0:
        if left[0] >= right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result += left
    result += right
    return result