第十四讲：排序

# -*- coding:utf-8 -*-
# 排序
# 插入排序
def insertSort(originList):
    sortedList = []
    for i in range(0, len(originList)):
        if len(sortedList) == 0:
            sortedList.append(originList[i])
            continue
            # 倒查
            # for j in range(len(sortedList) - 1, -1, -1):
            #     if sortedList[j] <= originList[i]:
            #         sortedList.insert(j + 1, originList[i])
            #         break
            #     if j == 0:
            #         sortedList.insert(0, originList[i])
            # 正查
        for j in range(0, len(sortedList)):
            if sortedList[j] >= originList[i]:
                sortedList.insert(j, originList[i])
                break
            if j == len(sortedList) - 1:
                sortedList.insert(len(sortedList), originList[i])
    originList[:] = sortedList[:]
originList = [5, 3, 1, 7, 9, 8]
insertSort(originList)
# print "insert"
# print originList
# 冒泡排序
# 快速排序(弹幕这个好像有问题，但是可以实现，我感觉没问题 ojbk
def quickSort(originList, start, end):
    if start >= end:
        return
    left = start
    right = end
    flagIndex = left
    while left < right:
        while right > left:
            if originList[right] < originList[flagIndex]:
                originList[right], originList[flagIndex] = originList[flagIndex], originList[right] # 交换两个变量的位置
                flagIndex = right   # 继续将比较值索引更换以保证比较值不变
                break
            right -= 1
        while left < right:
            if originList[left] > originList[flagIndex]:
                originList[left], originList[flagIndex] = originList[flagIndex], originList[left]
                flagIndex = left
                break
            left += 1
    quickSort(originList, start, flagIndex)
    quickSort(originList, flagIndex + 1, end)
originList = [5, 3, 1, 7, 9, 8]
quickSort(originList, 0, len(originList) - 1)
# print "quick"
# print originList
# 归并排序