冒泡排序，选择排序，归并排序，快速排序，插入排序和希尔排序

ゞ浴缸里的玫瑰 2022-04-25 01:00 239阅读 0赞

**目录**

冒泡排序

选择排序

插入排序，

希尔排序

归并排序

快速排序

--------------------

###  ###

### 冒泡排序 ###

需要多次遍历列表。它比较相邻的项并交换那些无序的项。每次遍历列表将下一个最大的值放在其正确的位置。实质上，每个项“冒泡”到它所属的位置。

Figure 1 展示了冒泡排序的第一次遍历。阴影项正在比较它们是否乱序。如果在列表中有 n 个项目，则第一遍有 n-1 个项需要比较。重要的是要注意，一旦列表中的最大值是一个对的一部分，它将不断地被移动，直到遍历完成。

![5.7.åæ³¡æåº.figure1][5.7._.figure1]

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
    
    alist = [54,26,93,17,77,31,44,55,20]
    bubbleSort(alist)
    print(alist)

### 选择排序 ###

改进了冒泡排序，每次遍历列表只做一次交换。为了做到这一点，一个选择排序在他遍历时寻找最大的值，并在完成遍历后，将其放置在正确的位置。与冒泡排序一样，在第一次遍历后，最大的项在正确的地方。 第二遍后，下一个最大的就位。遍历 n-1 次排序 n 个项，因为最终项必须在第（n-1）次遍历之后。

Figure 3 展示了整个排序过程。在每次遍历时，选择最大的剩余项，然后放置在其适当位置。第一遍放置 93，第二遍放置 77，第三遍放置 55 等。 该函数展示在 ActiveCode 1 中。

![5.8.éæ©æåº.activecode1][5.8._.activecode1]

你可能会看到选择排序与冒泡排序有相同数量的比较，因此也是 O(n^2)。 然而，由于交换数量的减少，选择排序通常在基准研究中执行得更快。 事实上，对于我们的列表，冒泡排序有 20 次交换，而选择排序只有 8 次。

### 插入排序， ###

尽管仍然是 O(n^2)O(n2)，工作方式略有不同。它始终在列表的较低位置维护一个排序的子列表。然后将每个新项 “插入” 回先前的子列表，使得排序的子列表称为较大的一个项。Figure 4 展示了插入排序过程。 阴影项表示算法进行每次遍历时的有序子列表。

![5.9.æå¥æåº.figure4][5.9._.figure4]

我们开始假设有一个项（位置 0 ）的列表已经被排序。在每次遍历时，对于每个项 1至 n-1，将针对已经排序的子列表中的项检查当前项。当我们回顾已经排序的子列表时，我们将那些更大的项移动到右边。 当我们到达较小的项或子列表的末尾时，可以插入当前项。

插入排序的最大比较次数是 n-1 个整数的总和。同样，是 O(n^2)O(n2)。然而，在最好的情况下，每次通过只需要进行一次比较。这是已经排序的列表的情况。

关于移位和交换的一个注意事项也很重要。通常，移位操作只需要交换大约三分之一的处理工作，因为仅执行一次分配。在基准研究中，插入排序有非常好的性能。

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
    
    alist = [54,26,93,17,77,31,44,55,20]
    insertionSort(alist)
    print(alist)

### 希尔排序 ###

希尔排序（有时称为“递减递增排序”）通过将原始列表分解为多个较小的子列表来改进插入排序，每个子列表使用插入排序进行排序。 选择这些子列表的方式是希尔排序的关键。不是将列表拆分为连续项的子列表，希尔排序使用增量i（有时称为 `gap`），通过选择 i 个项的所有项来创建子列表。

这可以在 Figure 6 中看到。该列表有九个项。如果我们使用三的增量，有三个子列表，每个子列表可以通过插入排序进行排序。完成这些排序后，我们得到如 Figure 7 所示的列表。虽然这个列表没有完全排序，但发生了很有趣的事情。 通过排序子列表，我们已将项目移动到更接近他们实际所属的位置。

![5.10.å¸å°æåº.figure6][5.10._.figure6]

Figure 8 展示了使用增量为 1 的插入排序; 换句话说，标准插入排序。注意，通过执行之前的子列表排序，我们减少了将列表置于其最终顺序所需的移位操作的总数。对于这种情况，我们只需要四次移位完成该过程。

![5.10.å¸å°æåº.figure8][5.10._.figure8]

乍一看，你可能认为希尔排序不会比插入排序更好，因为它最后一步执行了完整的插入排序。 然而，结果是，该最终插入排序不需要进行非常多的比较（或移位），因为如上所述，该列表已经被较早的增量插入排序预排序。 换句话说，每个遍历产生比前一个“更有序”的列表。 这使得最终遍历非常有效。

虽然对希尔排序的一般分析远远超出了本文的范围，我们可以说，它倾向于落在 O(n)和 O(n^2)之间的某处，基于以上所描述的行为。对于 Listing 5中显示的增量，性能为 O(n^2)。 通过改变增量，例如使用`2^k -1（1,3,7,15,31等等）`，希尔排序可以在 O(n^3/2)处执行。

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)
    print(alist)

### 归并排序 ###

我们现在将注意力转向使用分而治之策略作为提高排序算法性能的一种方法。 我们将研究的第一个算法是归并排序。归并排序是一种递归算法，不断将列表拆分为一半。 如果列表为空或有一个项，则按定义（基本情况）进行排序。如果列表有多个项，我们分割列表，并递归调用两个半部分的合并排序。 一旦对这两半排序完成，就执行称为合并的基本操作。合并是获取两个较小的排序列表并将它们组合成单个排序的新列表的过程。 Figure 10 展示了我们熟悉的示例列表，它被mergeSort 分割。 Figure 11 展示了归并后的简单排序列表。

![5.11.å½å¹¶æåº.figure10][5.11._.figure10]

![5.11.å½å¹¶æåº.figure11][5.11._.figure11]

ActiveCode 1 中展示的 `mergeSort` 函数从询问基本情况开始。 如果列表的长度小于或等于1，则我们已经有有序的列表，并且不需要更多的处理。另一方面，长度大于 1，那么我们使用 Python 切片操作来提取左右两半。 重要的是要注意，列表可能没有偶数个项。这并不重要，因为长度最多相差一个。

为了分析 mergeSort 函数，我们需要考虑组成其实现的两个不同的过程。首先，列表被分成两半。我们已经计算过（在二分查找中）将列表划分为一半需要 log^n 次，其中 n 是列表的长度。第二个过程是合并。列表中的每个项将最终被处理并放置在排序的列表上。因此，大小为 n 的列表的合并操作需要 n 个操作。此分析的结果是 logn 的拆分，其中每个操作花费 n，总共 nlogn。归并排序是一种 O(nlogn)算法。

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] < righthalf[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)
    
    alist = [54,26,93,17,77,31,44,55,20]
    mergeSort(alist)
    print(alist)

### 快速排序 ###

快速排序使用分而治之来获得与归并排序相同的优点，而不使用额外的存储。然而，作为权衡，有可能列表不能被分成两半。当这种情况发生时，我们将看到性能降低。

快速排序首先选择一个值，该值称为 `枢轴值`。虽然有很多不同的方法来选择枢轴值，我们将使用列表中的第一项。枢轴值的作用是帮助拆分列表。枢轴值属于最终排序列表（通常称为拆分点）的实际位置，将用于将列表划分为快速排序的后续调用。

Figure 12 展示 54 将作为我们的第一个枢纽值。由于我们已经看过这个例子几次，我们知道 54 最终将会在当前持有 31 的位置。接下来将发生分区过程。它将找到拆分点，同时将其他项移动到列表的适当侧，小于或大于枢轴值。

![5.12.å¿«éæåº.figure12][5.12._.figure12]

![5.12.å¿«éæåº.figure13][5.12._.figure13]

我们首先增加左标记，直到我们找到一个大于枢轴值的值。 然后我们递减右标，直到我们找到小于枢轴值的值。我们发现了两个相对于最终分裂点位置不适当的项。 对于我们的例子，这发生在 93 和 20。现在我们可以交换这两个项目，然后重复该过程。

在右标变得小于左标记的点，我们停止。右标记的位置现在是分割点。枢轴值可以与拆分点的内容交换，枢轴值现在就位（Figure 14）。 此外，分割点左侧的所有项都小于枢轴值，分割点右侧的所有项都大于枢轴值。现在可以在分割点处划分列表，并且可以在两半上递归调用快速排序。

![5.12.å¿«éæåº.figure14][5.12._.figure14]

ActiveCode 1中显示 `quickSort` 函数调用递归函数`quickSortHelper`。 `quickSortHelper` 以与合并排序相同的基本情况开始。如果列表的长度小于或等于一，它已经排序。 如果它更大，那么它可以被分区和递归排序。 分区函数实现前面描述的过程。

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)
           quickSortHelper(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
    
    alist = [54,26,93,17,77,31,44,55,20]
    quickSort(alist)
    print(alist)

要分析 `quickSort` 函数，请注意，对于长度为 n 的列表，如果分区总是出现在列表中间，则会再次出现 log⁡n 分区。为了找到分割点，需要针对枢轴值检查 n 个项中的每一个。结果是 nlog⁡n。此外，在归并排序过程中不需要额外的存储器。

不幸的是，在最坏的情况下，分裂点可能不在中间，并且可能非常偏向左边或右边，留下非常不均匀的分割。在这种情况下，对 n 个项的列表进行排序划分为对0 个项的列表和 n-1 个项目的列表进行排序。然后将 n-1 个划分的列表排序为大小为0的列表和大小为 n-2 的列表，以此类推。结果是具有递归所需的所有开销的 O(n^2) 排序。

我们之前提到过，有不同的方法来选择枢纽值。特别地，我们可以尝试通过使用称为中值三的技术来减轻一些不均匀分割的可能性。要选择枢轴值，我们将考虑列表中的第一个，中间和最后一个元素。在我们的示例中，这些是54,77和20.现在选择中值，在我们的示例中为54，并将其用于枢轴值（当然，这是我们最初使用的枢轴值）。想法是，在列表中的第一项不属于列表的中间的情况下，中值三将选择更好的“中间”值。当原始列表部分有序时，这将特别有用。

[5.7._.figure1]: https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.7.%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F/assets/5.7.%E5%86%92%E6%B3%A1%E6%8E%92%E5%BA%8F.figure1.png
[5.8._.activecode1]: https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.8.%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F/assets/5.8.%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F.activecode1.png
[5.9._.figure4]: https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.9.%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F/assets/5.9.%E6%8F%92%E5%85%A5%E6%8E%92%E5%BA%8F.figure4.png
[5.10._.figure6]: https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.10.%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/assets/5.10.shell%E6%8E%92%E5%BA%8F.figure6.png
[5.10._.figure8]: https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.10.%E5%B8%8C%E5%B0%94%E6%8E%92%E5%BA%8F/assets/5.10.shell%E6%8E%92%E5%BA%8F.figure8.png
[5.11._.figure10]: https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.11.%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/assets/5.11.%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F.figure10.png
[5.11._.figure11]: https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.11.%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F/assets/5.11.%E5%BD%92%E5%B9%B6%E6%8E%92%E5%BA%8F.figure11.png
[5.12._.figure12]: https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.12.%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F/assets/5.12.%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.figure12.png
[5.12._.figure13]: https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.12.%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F/assets/5.12.%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.figure13.png
[5.12._.figure14]: https://facert.gitbooks.io/python-data-structure-cn/5.%E6%8E%92%E5%BA%8F%E5%92%8C%E6%90%9C%E7%B4%A2/5.12.%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F/assets/5.12.%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F.figure14.png