Bdc6f800707c17a82eb0941c1eb3704b
Python-高级-常用排序算法实现

版权声明:本文为博主原创文章,遵循CC BY-NC-ND 4.0 版权协议,转载请附上原文出处链接和本声明。

排序是每个软件工程师和开发人员都需要基础知识技能。不仅要通过编码面试,还要对编程本身有一般性的了解。不同的排序算法是算法设计如何对程序复杂性,速度和效率产生如此强烈影响的完美展示。

让我们将5种最流行排序算法,看看如何在Python中实现它们!

Bubble Sort(冒泡排序)

冒泡排序是常用的一种,因为它清楚地演示了排序的工作方式,同时简单易懂。

冒泡排序逐步完成列表并比较相邻的元素对。如果元素的顺序错误,则会交换元素。重复遍历列表的未排序部分,直到列表被排序。

由于冒泡排序反复通过列表中未排序的部分,因此它的最坏情况复杂度为O(n²)。

Bubble Sort

Bubble Sort

def bubble_sort(arr):
    def swap(i, j):
        arr[i], arr[j] = arr[j], arr[i]

    n = len(arr)
    swapped = True

    x = -1
    while swapped:
        swapped = False
        x = x + 1
        for i in range(1, n-x):
            if arr[i - 1] > arr[i]:
                swap(i - 1, i)
                swapped = True

    return arr

Selection Sort(选择排序)

选择排序也很简单,但通常优于冒泡排序。如果您在两者之间进行选择,最好默认选择排序。

使用Selection排序,

  • 将输入列表/数组分为两部分:已排序的项目子列表和剩余要排序的项目子列表组成列表的其余部分。
  • 首先找到未排序子列表中的最小元素,并将其放在已排序子列表的末尾。
  • 不断抓取最小的未排序元素,并将其按排序的子列表中的排序顺序放置。该过程迭代地继续,直到列表完全排序。

Selection Sort

Selection Sort

def selection_sort(arr):        
    for i in range(len(arr)):
        minimum = i

        for j in range(i + 1, len(arr)):
            # Select the smallest value
            if arr[j] < arr[minimum]:
                minimum = j

        # Place it at the front of the 
        # sorted end of the array
        arr[minimum], arr[i] = arr[i], arr[minimum]

    return arr

Insertion Sort(插入排序)

与冒泡排序和选择排序相比,插入排序更快且可以说更简单。

在每次循环迭代中,插入排序从数组中删除一个元素。然后,它会在另一个已排序的数组中找到该元素所属的位置,并将其插入其中。它重复此过程,直到没有输入元素。

Insertion Sort

Insertion Sort

```python
def insertion_sort(arr):

for i in range(len(arr)):
    cursor = arr[i]
    pos = i

    while pos > 0 and arr[pos - 1] > cursor:
        # Swap the number down the list
        arr[pos] = arr[pos - 1]
        pos = pos - 1
    # Break and do the final swap
top Created with Sketch.