基本排序算法学习笔记 Python版

0x00、冒泡排序（Bubble Sort）

0.1 算法描述

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

0.2 我的理解

• 仅考虑第一次比较相邻元素并交换的情况，实际上只是为了找出最大的元素，并把它放到最后一个位置上去。
• 既然最后一个位置上是最大的元素了，直接忽略最后一个元素，将剩下的元素当成一个全新的列表来看，从里面找出最大的一个元素放到最后,依次类推.

0.3 Python代码实现

def BubbleSort(li = []):
    """
        params: li 是待排序列表
    """
    length = len(li))
    for i in range(length - 1):
        for j in range(length - i - 1):
            if li[j] > li{j+1}:
                li[j], li[j+1] = li[j+1], li[j]
    return li

0x01、选择排序（Selection Sort）

1.1 算法描述

选择排序（Selection-sort）是一种简单直观的排序算法。

• 初始状态：无序区为R[1..n], 有序区为空;
• 第i趟排序（i = 1, 2, 3, .. n -1 ）开始时，当前有序区和无序区分别为R[1..i-1] 和 R[i..n] 。该趟排序从当前无序区中选出关键字最小的记录R[k]，将它与无序区的第一个记录R交换，使R[1..i]和R[i+1..n]。
• 简单来说，有序区多了一个记录，无序区少了一个记录。
• n – 1趟结束，数组有序化。

1.2 我的理解

• 该算法的核心是将待排序列看成两个区间， 一个是无序的区间，也就是还没排序的区间。第二个区间，是已经排序的区间。
• 然后规定一下，已经排序好区间放前面，没排序的区间放后面。
• 所以实际操作起来就是，遍历无序区间找到最大的一个数，然后交换第一个数。
• 交换后，向前移动一个单位，剩下的看成一个新的、无序的列表，以此类推即可排序

1.3 Python代码实现

def SelectionSort(li=[]):
    li = [:] # 浅拷贝
    length = len(li)
    for i in range(length):
        index = i # 把无序列表的第一个当成最小的那个
        for j in range(i+1, length):
            if li[j] < li[index]:
                index = j
        li[i], li[index] = li[index], li[i]

0x02、插入排序（Insertion Sort）

2.1 算法描述

插入排序也是一种构建有序和无序序列的排序算法

• 从第一个元素开始，该元素可以被认为是排序好的元素。 也就是有序区的第一个元素
• 取出下一个元素（无序区第一个元素），在有序区从后向前扫描并一一比较
• 如果从无序区取出的这个元素比有序区的元素大，则把有序区元素向后移动一个，其实就是跟无序元素交换位置， 因为比较是依次两两进行的，所以是可行的
• 如果从无序区取出的这个元素比有序区的元素小，则把它放在该有序区元素的后面，也就是什么都不做
• 对无序区剩下的元素依次重复上面的操作

2.2 Python代码实现

def InsertionSort(li = []):
	li = li[:]
	length = len(li)
	for i in range(length):
		index = i
		for j in range(i - 1, -1, -1):
			if li[index] < li[j]:
				li[index], li[j] = li[j], li[index]
				index = j
	return li

0x03、希尔排序（Shell Sort）

1959年Shell发明，第一个突破O(n2)的排序算法，是简单插入排序的改进版。它与插入排序的不同之处在于，它会优先比较距离较远的元素。希尔排序又叫缩小增量排序。

3.1 算法描述

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

3.2 我的理解

• 正如注释所说，希尔排序是直接插入排序的改进算法。
• 所以要理解这个算法，首先要深入理解插入排序
• 考虑一下，直接插入排序的算法复杂度与什么有关？
• 我认为，应该是跟待排序列各元素的顺序有关，当序列越有序的时候，插入排序只需要进行有限次数的移动即可完成排序。
• 因此，当整个序列通过增量排序之后，将偏大或偏小的元素集中在某一边的时候，即可降低整个算法的复杂度
• 实现起来也很简单，分段插入排序即可。 以下面的代码为例，除了while gap > 0 和 gap //= 2 这两个跟插入算法不一样之外，其余部分几乎一样。所以很简单

3.3 Python代码实现

希尔排序的核心在于间隔序列的设定。，既可以提前设定好间隔序列，也可以动态定义间隔序列。动态定义间隔序列的算法是《算法（第4版）》的合著者Robert Sedgewick提出的

动态增量希尔排序

def ShellSort(li = []):
    li = li[:]  # 列表浅拷贝
    length = len(li)
    gap = 1   # 初始化间隔 1
    # 动态定义间隔
    while(gap < length / 3): #  1, 4, 13, 40, 121, 364, 1093
        gap = 3*gap + 1  

    while gap > 0:
        for i in range(gap, length):
            index = i
            for j in range(i-gap, -1, -gap):
                if li[index] < li[j]:
                    li[index], li[j] = li[j], li[index]
                    index = j
        gap //= 3
    return li
    
def gapGenerator(length):
    gap = 1
    while (gap < length /3):
        gap = 3*gap + 1
    while(gap > 0):
        yield gap
        gap = gap // 3

希尔增量希尔排序

# 希尔增量排序
def ShellSort(li = []):
    li = li[:]
    length = len(li)
    gap = length // 2
    while gap>0:
        for i in range(gap, length):
            index = i
            for j in range(i-gap, -1, -gap):
                if li[index] < li[j]:
                    li[index], li[j] = li[j], li[index]
                    index = j
        gap //= 2
    return li

0x04、归并排序（Merge Sort）

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

4.1 算法描述

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

4.2 我的理解

• 我还不能理解. hhhh
• 我的理解是这样的，通过递归的算法把数据二分，分到最后只剩一个的时候就返回，两个的时候就可以比较了，每一次退回上一层就把左右两部分依次进行比较，最后就得出一个序列化的数据。

4.3 python代码实现

#归并排序
def MergeSort(li = []):
    li = li[:]
    length = len(li)
    if length < 2: return li
    middle = length // 2
    left   = li[0:middle]
    right  = li[middle:]
    return merge(MergeSort(left), MergeSort(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))

    while len(left):
        result.append(left.pop(0))

    while len(right):
        result.append(right.pop(0))

    return result

0x05 快速排序 （Quick Sort）

快速排序的基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另外一部分记录的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。

5.1 算法描述

快速排序使用分治来把一个串（list）分为两个子串（sub-lists）。

• 从数列中挑选出一个元素，称为“基准”（Pivot）
• 重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大德摆在基准的后面（相同的数可以放到任一边）。在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partion）操作;
• 递归的（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

5.2 我的理解

• 快速排序（Quick Sort）是对冒泡排序的一种改进。

5.3 Python代码实现

def QuickSort(li = []):
    li = li[:]
    length = len(li)
    if firstIndex < lastIndex:
        devIndex = Partion(li, firstIndex, lastIndex)
        
        QuickSort(li, firstIndex, divIndex)
        QuickSort(li, divIndex + 1, lastIndex)
        
def Partion