Python实现常见的排序算法

Python实现常见的排序算法

冒泡排序

• 算法步骤如下：
  1. 比较相邻的元素。若第一个比第二个大，则交换位置。
  2. 对每一对相邻的元素做同样的工作，从刚开始的第一对到最后一对，做完后，最后的元素会是最大的数。
  3. 针对所有元素重复以上步骤，每次都会有最后一个数的位置确定下来。
  4. 持续上面的步骤，直到没有任何一对数字需要比较为止。

  • 实现代码如下：

    def bubbleSort(arr):
        for i in range(1, len(arr)):
            for j in range(0, len(arr)-i):
                if arr[j] > arr[j+1]:
                    arr[j], arr[j+1] = arr[j+1], arr[j]
        return arr
    

  • 平均时间复杂度：O(n^{2)；最好情况：O(n)；最坏情况：O(n}2)。

  • 空间复杂度：O(1)。

  • 排序方式：内部排序；稳定性：稳定。

    选择排序

    • 算法步骤如下：
      1. 首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
      2. 再从剩余未排序元素中继续寻找最小（大）元素，存放到已排序序列的末尾。
      3. 重复以上步骤，直到所有元素都排好序为止。

      • 实现代码如下：

        def selectionSort(arr):
            for i in range(len(arr) - 1):
                # 记录最小元素的索引
                minIndex = i
                for j in range(i+1, len(arr)):
                    if arr[j] < arr[minIndex]:
                        minIndex = j
                # i不是最小数时，将i和最小数进行交换
                if i != minIndex:
                    arr[i], arr[minIndex] = arr[minIndex], arr[i]
            return arr
        

      • 平均时间复杂度：O(n^{2)；最好情况：O(n}2)；最坏情况：O(n^2)。

      • 空间复杂度：O(1)。

      • 排序方式：内部排序；稳定性：不稳定。

        插入排序

        • 算法步骤如下：
          1. 将待排序序列的第一个元素作为一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
          2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入元素与有序序列的元素相等，则将其插入到相等元素的后面）

          • 实现代码如下：

            def insertionSort(arr):
                for i in range(len(arr)):
                    preIndex = i-1
                    current = arr[i]
                    while preIndex >= 0 and arr[preIndex] > current:
                        arr[preIndex+1] = arr[preIndex]
                        preIndex -= 1
                    arr[preIndex+1] = current
                return arr
            

          • 平均时间复杂度：O(n^{2)；最好情况：O(n)；最坏情况：O(n}2)。

          • 空间复杂度：O(1)。

          • 排序方式：内部排序；稳定性：稳定。

            希尔排序

            • 算法步骤如下：
              1. 选择一个增量序列t1，t2，…，tk，其中ti>tj，tk=1。
              2. 按增量序列个数k，对序列进行k躺排序。
              3. 每趟排序，根据对应的增量ti，将待排序序列分割成若干个长度为m的子序列，分别对各个子序列进行直接插入排序。当增量为1时，将整个序列进行最终的插入排序。

              • 实现代码如下：

                def shellSort(arr):
                    import math
                    gap = 1
                    while (gap < len(arr)/3):
                        gap = gap*3 + 1
                    while gap > 0:
                        for i in range(gap, len(arr)):
                            temp = arr[i]
                            j = i - gap
                            while j >= 0 and arr[j] > temp:
                                arr[j+gap] = arr[j]
                                j -= gap
                            arr[j+gap] = temp
                        gap = math.floor(gap/3)
                    return arr
                

              • 平均时间复杂度：O(nlogn)；最好情况：O(nlog^{2n)；最坏情况：O(nlog}2n)。

              • 空间复杂度：O(1)。

              • 排序方式：内部排序；稳定性：不稳定。

                归并排序

                • 算法步骤如下：
                  1. 申请空间，空间大小为两个已经排序序列之和，该空间用来存放合并后的序列；
                  2. 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
                  3. 比较两个指针的元素，选择较小的元素放入到合并空间中，并移动指针到下一个位置；
                  4. 重复步骤3的操作直到某一个指针到达序列尾部；
                  5. 将另一个序列剩下的所有元素直接复制并合并到序列尾。

                  • 实现代码如下：

                    def mergeSort(arr):
                        import math
                        if len(arr) < 2:
                            return arr
                        middle = math.floor(len(arr) / 2)
                        left, right = arr[0:middle], arr[middle:]
                        return merge(mergeSort(left), mergeSort(right))
                    def merge(left, right):
                        result = []
                        while left and right:
                            if left[0] <= right[0]:
                                result.append(left.pop(0))
                            else:
                                result.append(right.pop(0))
                        while left:
                            result.append(left.pop(0))
                        while right:
                            result.append(right.pop(0))
                        return result
                    

                  • 平均时间复杂度：O(nlogn)；最好情况：O(nlogn)；最坏情况：O(nlogn)。

                  • 空间复杂度：O(n)。

                  • 排序方式：外部排序；稳定性：稳定。

                    快速排序

                    • 算法步骤如下：
                      1. 从数列中挑出一个元素，作为“基准”（pivot）；
                      2. 重新排序数列，所有元素比基准值小的摆放在基准前面，比基准值大的摆放在基准的后面（相同元素可以任一边）。分区退出后，该基准处于数列的中间位置；
                      3. 递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

                      • 实现代码如下：

                        def quickSort(arr, left=None, right=None):
                            left = 0 if not isinstance(left, (int, float)) else left
                            right = len(arr) - 1 if not isinstance(right, (int, float)) else right
                            if left < right:
                                partitionIndex = partition(arr, left, right)
                                quickSort(arr, left, partitionIndex-1)
                                quickSort(arr, partitionIndex+1, right)
                            return arr
                        def partition(arr, left, right):
                            pivot = left
                            index = pivot + 1
                            i = index
                            while i <= right:
                                if arr[i] < arr[pivot]:
                                    swap(arr, i, index)
                                    index += 1
                                i += 1
                            swap(arr, pivot, index-1)
                            return index - 1
                        def swap(arr, i, j):
                            arr[i], arr[j] = arr[j], arr[i]
                        

                      • 平均时间复杂度：O(nlogn)；最好情况：O(nlogn)；最坏情况：O(n^2)。

                      • 空间复杂度：O(logn)。

                      • 排序方式：内部排序；稳定性：不稳定。