搜索和排序(3) – 希尔排序、归并排序和快速排序

希尔排序

希尔排序也被称为“递减增量排序”，它是在插入排序的基础上做了改善，将列表分成多个子列表，并对每一个子列表进行插入排序。希尔排序并不是连续切分，而是运用增量i并选取一切距离为i的元素组成的子列表进行排序，这个i有时也被称作步长。

下面咱们来举一个例子，比方当前列表中有9个元素，假如增量为3，那么就存在3个子列表，别离是[54、17、44]， [26、77、55]， [93、31、20]。如下图所示：

假如咱们将每一个子列表进行插入排序就会得到以下结果：

榜首个子列表由54、17、44排序为17、44、54

第二个子列表由26、77、55排序为26、55、77

第三个子列表由93、31、20排序为20、31、93

终究以步长为3的排序结果为17、26、20、44、55、31、54、77、93

由此，咱们也就减少了终究排序的次数，终究一次运用插入排序得到终究结果：

所以，如何切分列表才是希尔排序的要害。

用Python完结希尔排序

咱们首要为$n/2$个子列表排序，然后为$n/4$个子列表排序，终究整个列表由根本的插入排序排好序。下图展现了选用这种增量后的榜首批子列表：

代码示例：

def shellSort(alist):
    subListCount = len(alist) / / 2
    while subListCount > 0:
        for startPosition in range(subListCount):
            gapInsertionSort(alist, startPosition, subListCount)
        print(*After increments of size*, subListCount, *The list is*, alist)
        subListCount = subListCount / / 2
def gapInsertionSort(alist, start, gap):
    for i in range(start + gap, len(alist), gap):
        currentValue = alist[i]
        position = i
        while position >= gap and alist[position - gap] > currentValue:
            alist[position] = alist[position - gap]
            position = position - gap
        alist[position] = currentValue
>>> alist = [54, 26, 93, 17, 77, 31, 44, 55, 20]
>>> shellSort(alist)
After increments of size 4 the list is [20, 26, 44, 17, 54, 31, 93, 55, 77]
After increments of size 2 the list is [20, 17, 44, 26, 54, 31, 77, 55, 93] 
After increments of size 1 the list is [17, 20, 26, 31, 44, 54, 55, 77, 93]

希尔排序和插入排序比起来最大的优势便是，希尔排序对列表现已做了预处理。所以在终究一步进行插入排序时就不需求进行多次比较和移动了。也便是说，在每一轮遍历时都使列表变得更加有序了，这使得终究一步就变得特别高效。

终究，希尔排序的时刻复杂度介于O(n)和O(n)之间。

归并排序

归并算法是经过分治战略来改善一种排序算法。它是一个递归算法，他会每次将一个列表一分为二。

假如一个列表是空或者只要一个元素的话，那么咱们认为它是有序的；假如列表不止一个元素，那么就将列表一分为二，并对这两部分都别离递归调用归并排序；当两部分都变为有序后，就进行归并这一根本操作。归并指的是将两个较小的有序列表并为一个有序列表的进程。

以列表54、26、93、17、77、31、44、55、20为例，下图展现了列表被拆分后的状况：

下图展现了归并后的有序列表：

归并排序的进程：

用Python完结归并排序

假如列表的长度小于或等于1，就阐明它现已是一个有序列表了，所以不需求做任何处理；假如长度大于1，那么就经过切片得到列表的左半部分和右半部分。

def mergeSort(alist):
    print("Splitting ", alist) //此处用于展现每次调用开端前，待排序列表中的内容
    if len(alist) > 1:
        mid = len(alist) / / 2
        leftHalf = alist[:mid]
        rightHalf = alist[mid:]
        mergeSort(leftHalf)
        mergeSort(rightHalf)
        // 以下代码担任将两个小的有序列表归并为一个大的有序列表
        i = 0
        j = 0
        k = 0
        while i < len(leftHalf) and j < len(rightHalf):
            if leftHalf[i] < rihtHalf[j]:
                alist[k] = leftHalf[i]
                i = i + 1
            else:
                alist[k] = rightHalf[j]
                j = j + 1
            k = k + 1
        while i < len(leftHalf):
            alist[k] = leftHalf[i]
            i = i + 1
            k = k + 1
        while j < len(rightHalf):
            alist[k] = rightHalf[j]
            j = j + 1
            k = k + 1
    print("Merging ", alist ) // 此处用于展现归并进程
>>> b = [54, 26, 93, 17, 77, 31, 44, 55, 20]
>>> mergeSort(b)
Splitting [54, 26, 93, 17, 77, 31, 44, 55, 20] 
Splitting [54, 26, 93, 17]  // 左半部分
Splitting [54, 26] // 左半部分的左半部分
Splitting [54]
Merging [54] 
Splitting [26] 
Merging [26] 
Merging [26, 54]  // 左半部分的左半部分排序完结
Splitting [93, 17] // 左半部分的右半部分
Splitting [93] 
Merging [93] 
Splitting [17] 
Merging [17] 
Merging [17, 93] // 左半部分的右半部分排序完结
Merging [17, 26, 54, 93] // 左半部分整体排序完结
Splitting [77, 31, 44, 55, 20] // 右半部分
Splitting [77, 31] // 右半部分的左半部分
Splitting [77] 
Merging [77] 
Splitting [31] 
Merging [31] 
Merging [31, 77] // 右半部分的左半部分排序完结
Splitting [44, 55, 20] // 右半部分的右半部分 
// 这儿需求留意的是：因为[44, 55, 20]不会均分，所以需求将[44, 55, 20]分为两部分，榜首部分是[44]，第二部分是[55, 20]
Splitting [44] 
Merging [44]  // 榜首部分默许有序
Splitting [55, 20] // 第二部分
Splitting [55] 
Merging [55] 
Splitting [20]
Merging [20] 
Merging [20, 55] // 第二部分排序完结
Merging [20, 44, 55] // 右半部分的右半部分排序完结
Merging [20, 31, 44, 55, 77] // 右半部分排序完结
Merging [17, 20, 26, 31, 44, 54, 55, 77, 93] // 整个数组排序完结
// 这儿需求留意的一点是：因为mergeSort函数需求额定的空间来存储经过切片操作得到的两个部分，那么当列表较大时，运用额定的空间或许会使排序出现问题。

咱们在二分搜索时现已知道，当列表的长度为n时，能切分log以2为底$n$次。

列表中的每一个元素终究都会得到处理并放到有序列表中，所以得到长度为$n$的列表就需求$n$次操作。

由此可知，咱们需求进行$logn$次拆分，且每一次都需求进行$n$次操作，所以一共是$nlogn$次操作。

终究得到，归并算法的时刻复杂度是O($nlogn$)。

快速排序

快速排序和归并排序相同，也选用分治战略，但是不运用额定的空间。但是列表不会被一分为二，算法的效率会有所下降。

快速排序会首要选出一个基准值。它的作用是帮助切分列表。在终究的有序列表中，基准值的正确所在方位通常被称作切割点，咱们会在切割点的左右两侧别离切分出列表，继续快速排序操作。

现在咱们有一个列表[54、26、93、17、77、31、44、55、20]，咱们将54作为榜首个基准值：

下一步咱们需求找到54的正确所在方位，这个方位也便是咱们说的切割点。咱们需求进行分区操作。经过分区操作，会找到切割点的方位，并将大于基准值的一切元素放在一边，小的放在另一边。

分区操作首要要找到两个坐标–leftmark和rightmark，他们别离位于列表剩下元素的最初和结尾。分区的目的是依据待排序的元素和基准值比较大小，并把他们放到正确的一边，一起逐步逼近切割点。

下图展现了为54寻找正确方位的进程：

首要咱们在剩下列表的最初向右找到一个比基准值大的元素作为leftmark，再从结尾向左找到一个比基准值小的值作为rightmark。也便是例子中的93和20，咱们互换他们的方位，继续重复上述进程。

当rightmark小于leftmark时，进程终止。这时，rightmark的方位便是切割点。将基准值与切割点的元素互换，就找到了基准值的正确方位。

如下图所示，此时，切割点左边一切的元素都小于基准值，右侧都大于基准值。因而咱们能够在切割点处将列表一分为二，并针对左右两部分递归的调用快速排序函数。

快速排序的进程：

用Python完结快速排序

在下面的代码中，快速排序函数quickSort调用了递归函数quickSortHelper，quickSortHelper首要处理和归并排序相同的根本状况，也便是假如列表的长度小于或等于1，阐明他现已是有序列表，假如大于1，则进行分区操作并递归地排序。这儿的分区函数partition完结了前面描述的进程。

def quickSort(alist):
    quickSortHelper(alist, 0, len(alist) - 1)
def quickSortHelper(alist, first, last):
    if first > last:
        splitPoint = partition(alist, first, last)
        quickSortHelper(alist, first, splitPoint - 1)
        quickSortHepler(alist, splitPoint + 1, last)
def partition(alist, first, last):
    pivotValue = alist[first]
    leftmark = first + 1
    rightmark = last
    done = False
    while not done:
        while leftmark <= rightmark and alist[leftmark] <= pivotValue:
            leftmark = leftmark + 1
        while alist[rightmark] >= pivotValue and rightmark >= leftmark:
            rightmark = rightmark - 1
        if rightmark < leftmark:
            done = True
        else:
            temp = alist[leftmark]
            alist[leftmark] = alist[rightmark]
            alist[rightmark] = temp
     temp = alist[first]
     alist[first] = alist[rightmark]
     alist[rightmark] = temp
     return rightmark

关于长度为n的列表，假如分区操作总是发生在列表的中部，那么就会切分$logn$次，为了找到切割点，$n$个元素都要与基准值比较，所以时刻复杂度是$O(nlogn)$。

假如切割点不在中部而是偏向列表的某一端，那么含有n个元素的列表或许被分成一个不含元素的列表和一个含有n-1个元素的列表，然后含有n-1的列表或许会被分成不含元素的列表和一个含有n-2元素的列表，以此类推。所以会导致时刻复杂度变为O(n2)O(n)O(n2)，因为还要加上递归的开销。

小结

1.不管列表是否有序，顺序搜索算法是时刻复杂度都是$O(n)$。

2.关于有序列表来说，二分搜索算法在最坏状况下的时刻复杂度是$O(logn)$。

3.根据散列表的搜索算法能够到达常数阶。

4.冒泡排序、挑选排序和插入排序都是O(n2)O(n)O(n2)算法。

5.希尔排序经过给子列表排序，改善了插入排序。它的时刻复杂度介于$O(n)$和O(n2)O(n)O(n2)之间。

6.归并排序的时刻复杂度是$O(nlogn)$,但是归并进程需求用到额定的储存空间。

7.快速排序的时刻复杂度是$O(nlogn)$，但当切割点不靠近列表中部时会降到O(n2)O(n)O(n2)，它不需求运用额定的存储空间。