第二章：排序基础

---

选择排序算法（selectionSort）

算法思想：

（直白描述）
1. 找出所有元素中的最小值，与第一个位置的元素互换。
2. 找出剩下的元素中的最小值，与第二个位置的元素互换。
3. 以此类推。

（形式化描述）
重复（元素个数-1）次
    # 从0开始
    把第一个没有排序过的元素设置为最小值
    遍历每个没有排序过的元素
        如果元素 < 现在的最小值
        将此元素设置成为新的最小值
    将最小值和第一个没有排序过的位置交换

算法图示：

选择排序.gif
Python使用函数实现：

def selectionSort(arrList):
    '''
    选择排序
    :param arrList:可迭代对象
    :return:
    '''
    for i in range(0, len(arrList)):
        # 寻找[i, len(arrlist))区间的最小值
        minIndex = i
        for j in range(i+1, len(arrList)):

            if arrList[j] < arrList[i]:
                minIndex = j

        # 交换i位置和最小值
        # 注意双向交换
        arrList[i], arrList[minIndex] = arrList[minIndex], arrList[i]

# 测试
a = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]
selectionSort(a)

print(a)    
# 输出
[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

使用模板（泛型）编写算法：
随机生成算法测试用例：
测试算法性能

---

插入排序算法（insertionSort）

算法思想：

（直白描述）
1.当只考虑第一个元素的时候，它已经排好序了，第一个元素不动。
2.寻找第二个元素合适的位置，把它和第一个元素比较，如果小于第一个元素，交换，否则，它的位置是合适的，继续下一次循环。
3.寻找第三个元素合适的位置，先和第二个元素比较，如果小于第二个元素，和第二个元素交换位置，然后和第一个元素比较，如果小于第一个元素，和第一个元素交换位置，继续下一次循环。

Python使用函数实现：

def insertionSort(arrList):
    # 从1开始，第0个元素已经有序
    for i in range(1, len(arrList)):
        # 寻找arrList[i]合适的插入位置
        for j in range(i, 0, -1):
            # 如果当前位置元素比前一个位置元素小，交换
            if arrList[j] < arrList[j-1]:
                arrList[j-1], arrList[j] = arrList[j], arrList[j-1]
            # 否则，当前元素位置合适，寻找下一个元素的合适位置
            else:
                break

a = [10, 9, 8, 7, 6]
insertionSort(a)

print(a)
# [6, 7, 8, 9, 10]

插入排序算法的改进

算法思想：

（形式化描述）
将第一个元素标记为已排序
遍历每个没有排序过的元素
    “提取” 元素 X
    i = 最后排序过元素的指数 到 0 的遍历
        如果现在排序过的元素 > 提取的元素
            将排序过的元素向右移一格
        否则：插入提取的元素

算法图示：

插入排序.gif
Python使用函数实现：

def insertionSort(arrList):
    # 从1开始，第0个元素已经有序
    for i in range(1, len(arrList)):
        # 寻找arrList[i]合适的插入位置

        # 将当前元素提取出来
        x = arrList[i]
        # j保存元素应该插入的位置，初始为i
        j = i
        # -1取不到，可以取到0
        for j in range(i, -1, -1):
            if arrList[j-1] > x:
                # 赋值而不做交换
                arrList[j] = arrList[j-1]
            else:
                # 位置合适
                break

        arrList[j] = x

a = [10, 9, 8, 7, 6]
insertionSort(a)

print(a)
# [6, 7, 8, 9, 10]

冒泡排序（bubbleSort）

希尔排序（shellSort）