常见排序算法总结(python实现)

一、插入排序

1、排序原理

i为已排序,j设为未排序

先将i1(第一个元素)标记为已排序,从j2(第二个元素)开始,将j2i中的元素比较(从i-1开始),如果j2<i-1,则将i-1后移一位,直到j2>in

以此类推,即可完成排序

2、代码实现

def insertSort(nums):
    length = len(nums)
    for i in range(1, length):
        temp = nums[i]
        for j in range(i, -1, -1):
            if temp < nums[j-1]:
                nums[j] = nums[j-1]
            else:
                break
        nums[j] = temp
    return nums

3、算法开销

插入排序是一种稳定的排序方法,其时间复杂度为O(n²)。排序过程只要一个元素的辅助空间,空间复杂度为O(1)。

二、冒泡排序

1、算法原理

i1i2比较,如果i1>i2,,交换i1i2,然后i2(可能经过交换)与i3比较,继续之前的步骤,一直到in,称为第一趟冒泡排序。第一趟冒泡排序后,最大的元素就会到最后一位,第二趟可以将第二大元素放在倒二位上……

经过i-1趟后,即可完成排序

2、代码实现

def bubbletSort(nums):
    length = len(nums)
    for i in range(length-1):
        for j in range(length-1-i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
    return nums

3、算法开销

冒泡排序也是一种稳定的排序方法,其时间复杂度为O(n²)。排序过程只要一个元素的辅助空间,空间复杂度为O(1)。

三、归并排序

1、算法原理

归并排序的核心是分治法,即分而治之。当一个大问题不好解决时,将其分解为多个子问题,且这些子问题互相独立且与原问题相同。最后将所有子问题的解合并,就得到原问题的解。

归并排序实现的步骤:

(1)分解。将n个元素分成各含n/2个元素的子序列

(2)求解。用归并排序对两个子序列递归地排序

(3)合并。合并两个已经排好序的子序列以及得到排序结果

2、代码实现

def MergeSort(nums):
    length = len(nums)
    if length == 1:
        return nums
    mid = length // 2
    left = nums[:mid]
    right = nums[mid:]
    l = MergeSort(left)
    r = MergeSort(right)
    return Merge(l, r)

def Merge(left, right):
    res = []

    while len(left) > 0 and len(right) > 0:
        if left[0] <= right[0]:
            res.append(left.pop(0))
        else:
            res.append(right.pop(0))

    res += left
    res += right
    return res

3、算法开销

归并排序也是一种稳定的排序方法,其时间复杂度为O(nlogn)。排序过程需要n个(与待排序记录数量相同)辅助空间,空间复杂度为O(n)。

四、快速排序

1、算法原理

快速排序是对冒泡排序的改进,通过一趟排序将待排记录划分为独立的两部分,成为前半区和后半区,其中,前半区中记录的关键字均不大于后半区记录的关键字,然后再分别对这两个部分进行快速排序,从而使整个序列有序。

快速排序实现的步骤:

(1)定义一个轴心点为pivot(用于比较,通常是第一个记录),两个指针ij,分别指向第一个和最后一个记录

(2)从j开始向前搜索,找到第一个小于pivot的记录并将其移动到i所在的位置

(3)从i开始向后搜索,找到第一个大于pivot的记录并将其移动到j所在的位置

(4)重复(3)、(4),直到ij相等为止

2、代码实现

def QuickSort(nums, low, high):
    if low < high:
        mid = Partition(nums, low, high)
        QuickSort(nums, low, mid)
        QuickSort(nums, mid+1, high)

def Partition(nums, low, high):
    pivot = nums[low]
    i, j = low, high
    while i < j:
        while i < j and nums[j] >= pivot:
            j -= 1
        nums[i] = nums[j]
        while i < j and nums[i] <= pivot:
            i += 1
        nums[j] = nums[i]
    nums[i] = pivot
    return i

另一种实现(递归+分治)

def QuickSort(nums):
    if len(nums) < 2:
        return nums
    else:
        pivot = nums[0]
        low = [m for m in nums[1:] if m < pivot]
        higt = [n for n in nums[1:] if n > pivot]
    return QuickSort(low) + [pivot] + QuickSort(higt)

转自百度百科(快速排序算法)

3、算法开销

快速排序是一种不稳定的算法,其时间复杂度为O(nlog₂n),空间复杂度为O(n²)


最后推荐一个排序可视化的网站,有助于理解各种排序算法

visualgo

  • 用支付宝打我
  • 用微信打我

Long may the sunshine

3条回应:“常见排序算法总结(python实现)”

  1. 树先生说道:

    有些问题想请教,能告诉我QQ吗?

Emin进行回复 取消回复

电子邮件地址不会被公开。 必填项已用*标注

召唤蕾姆