搜索和排序(2) – 冒泡排序、选择排序和插入排序

冒泡排序

冒泡排序要经过多次遍历列表，她比较相邻的元素，将不合顺序的进行方位交流，在每一轮遍历中都将下一个最大值放在正确的方位上。

下图展现了冒泡排序第一次遍历的过程，其间深色的是正在比较的元素。假如列表中有n个元素，那么第一轮遍历要比较n-1对：

当第二轮开端遍历时，最大值现已在正确的方位上了，所以还剩n-1个元素需求遍历，那么第二遍便是要遍历n-2次。以此类推，那么咱们需求遍历的轮数便是n-1轮。当n-1轮完成后，最小的元素就必然在正确的方位上了。

用Python完成冒泡排序

def bubbleSort(alist):
    for passnum in range(len(alist) - 1, 0, -1):
        for i in range(passnum):
            if alist[i] > alist[i + 1]
                temp = alist[i]
                alist[i] = alist[i + 1]
                alist[i + 1] = temp

冒泡排序一般认为是效率最低的排序算法，由于在确认终究的方位前有必要交流元素。所以咱们可以经过在一轮遍历中有没有发生元素交流，假如没有，证明列表现已有序，下一次遍历就不需求将这两个元素再进行一次排序了，这种对冒泡排序的修改成为短冒泡。

def shortBubbleSort(alist):
    exchanges = True
    passnum = len(alist - 1)
    while passnum > 0 and exchanges:
        exchanges = False
        for i in range(passnum):
            if alist[i] > alist[i + 1]:
                exchanges = True
                temp = alist[i]
                alist[i] = alist[i + 1]
                alist[i + 1] = temp
        passnum = passnum + 1

挑选排序

挑选排序是在冒泡排序的基础上做了改善，每次遍历列表时只做一次交流。它是在每一次遍历时找到元素最大值并放在正确方位上，假定咱们给n个元素排序，那么需求遍历n-1轮。

用Python完成挑选排序

def selectionSort(alist):
    for fillslot in range(len(alist) - 1, 0, -1):
        positionOfMax = 0
        for location in range(1, fillslot + 1):
            if alist[location] > alist[positionOfMax]:
                positionOfMax = location
        temp = alist[fillslot]
        alist[fillslot] = alist[posotionOfMax]
        alist[positionOfMax] = temp

挑选排序的时刻复杂度也是O(n)，但是由于减少了交流次数，所以挑选排序一般更快。

刺进排序

刺进排序的时刻复杂度也是O(n)，它是在列表较低的一段维护一个有序的子列表，将每个新元素逐一刺进子列表中。

下图具体的展现了第5轮遍历的情况。此时，有序子列表中包括5个元素：17、26、54、77、93，现在想刺进31。第一次与93比较，93右移，同理77和54也会右移。当遇到26时不会移动了，所以31的方位就找到了，现在子列表中就有6个元素了：

所以，当n个元素排序时，刺进排序需求遍历n-1轮，循环从方位1开端，直到n-1完毕，这些元素都被刺进到有序子列表中。

用Python完成刺进排序

def insertionSort(alist):
    for index in range(1, len(alist)):
        currentValue = alist[index]
        position = index
        while position > 0 and alist[position - 1] > currentValue:
            alist[position] = alist[position - 1] // 完成了移动操作，将列表中的一个值挪一个方位，为待刺进元素腾出空间
            position = position - 1
        alist[position] = currentValue

最坏情况下，刺进排序算法的比较次数是前n-1个整数之和，对应的时刻复杂度的是O(n)；最好的情况下，列表现已是有序的，那么每一轮只需比较一次。