python–排序总结

1.快速排序

a.原理

快速排序的基本思想是在待排序的 n 个元素中任取一个元素(通常取第一个元素)作为基准,把该元素放人最终位置后,整个数据序列被基准分割成两个子序列,所有小于基准的元素放置在前子序列中,所有大于基准的元素放置在后子序列中,并把基准排在这两个子序列的中间,这个过程称为划分。然后对两个子序列分别重复上述过程,直到每个子序列内只有一个元素或空为止。

这是一种二分法思想,每次将整个无序序列一分为二。归位一个元素,对两个子序列采用同样的方式进行排序,直到子序列的长度为1或0为止。(摘自算法分析与设计第二版 有删改)

b.代码 

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]#轴
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)
s = list(map(float,input("输入用空格分隔的数字:").split()))#
print(quick_sort(s))

 python--排序总结

c.复杂度

时间复杂度最好情况O(nlog2n),

时间复杂度最坏情况O(n^2),

时间复杂度平均情况O(nlog2n),

空间复杂度最好情况O(log2n),

d.稳定性

不稳定

2.插入排序

a.原理 

插入排序,一般也被称为直接插入排序。对于少量元素的排序,它是一个有效的算法。插入排序是一种最简单的排序方法,它的基本思想是将一个记录插入到已经排好序的有序表中,从而一个新的、记录数增1的有序表。在其实现过程使用双层循环,外层循环对除了第一个元素之外的所有元素,内层循环对当前元素前面有序表进行待插入位置查找,并进行移动。

b.代码

def insert_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

arr = [3, 5, 2, 4, 1]
print(insert_sort(arr))

python--排序总结

c.复杂度

时间复杂度最好情况O(n),

时间复杂度最坏情况O(n^2),

时间复杂度平均情况O(n^2),

空间复杂度最好情况O(1),

d.稳定性

稳定

3.冒泡排序

a.原理 

重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序错误就把他们交换过来。走访元素的工作是重复地进行,直到没有相邻元素需要交换,也就是说该元素列已经排序完成

b.代码 

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

arr = [3, 5, 2, 4, 1]
print(bubble_sort(arr))

python--排序总结

c.复杂度

时间复杂度最好情况O(n),

时间复杂度最坏情况O(n^2),

时间复杂度平均情况O(n^2),

空间复杂度最好情况O(1),

d.稳定性

稳定

4.希尔排序

a.原理

希尔排序是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。

希尔排序是把记录按下标的一定增量分组,对每组使用直接插入排序算法排序;随着增量逐渐减少,每组包含的关键词越来越多,当增量减至 1 时,整个文件恰被分成一组,算法便终止。

b.代码 

def shell_sort(arr):
    n = len(arr)
    gap = n // 2
    while gap > 0:
        for i in range(gap, n):
            temp = arr[i]
            j = i
            while j >= gap and arr[j - gap] > temp:
                arr[j] = arr[j - gap]
                j -= gap
            arr[j] = temp
        gap //= 2
    return arr

arr = [3, 5, 2, 4, 1]
print(shell_sort(arr))

python--排序总结

c.复杂度

时间复杂度最好情况,

时间复杂度最坏情况,

时间复杂度平均情况O(n^1.3),

空间复杂度最好情况O(1),

d.稳定性

稳定

5.选择排序

a.原理 

选择排序是一种简单直观的排序算法。它的工作原理是:第一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,然后再从剩余的未排序元素中寻找到最小(大)元素,然后放到已排序的序列的末尾。以此类推,直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法

b.代码 

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

arr = [3, 5, 2, 4, 1]
print(selection_sort(arr))

python--排序总结

c.复杂度

时间复杂度最好情况O(n^2),

时间复杂度最坏情况O(n^2),

时间复杂度平均情况O(n^2),

空间复杂度最好情况O(1),

d.稳定性

稳定

6.堆排序

a.原理 

堆排序是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点。

发明人:罗伯特·弗洛伊德

b.代码 

def heap_sort(arr):
    n = len(arr)
    # 建立大顶堆
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # 将堆顶元素与末尾元素交换,并重新调整大顶堆
    for i in range(n - 1, 0, -1):
        arr[i], arr[0] = arr[0], arr[i]
        heapify(arr, i, 0)
    return arr

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2
    if l < n and arr[largest] < arr[l]:
        largest = l
    if r < n and arr[largest] < arr[r]:
        largest = r
    if largest != i:
        arr[i], arr[largest] = arr[largest], arr[i]
        heapify(arr, n, largest)

arr = [3, 5, 2, 4, 1]
print(heap_sort(arr))

python--排序总结

c.复杂度

时间复杂度最好情况O(nlog2n),

时间复杂度最坏情况O(nlog2n),

时间复杂度平均情况O(nlog2n),

空间复杂度最好情况O(1),

d.稳定性

不稳定

7.归并排序

a.原理 

归并排序的基本思想是首先将 a [0.. n 一1]看成 n 个长度为1的有序表,将相邻的 k ( k ≥2)个有序子表成对归并,得到 n / k 个长度为 k 的有序子表:然后再将这些有序子表继续归并,得到 n /k2个长度为 k 的有序子表,如此反复进行下去,最后得到一个长度为 n 的有序表。由于整个排序结果放在一个数组中,所以不需要特别地进行合并操作。若 k =2,即归并是在相邻的两个有序子表中进行的,称为二路归并排序。若 k >2,即归并操作在相邻的多个有序子表中进行,则叫多路归并排序。(摘自算法分析与设计第二版)

b.代码 

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left = arr[:mid]
        right = arr[mid:]
        merge_sort(left)
        merge_sort(right)

        i = j = k = 0

        while i < len(left) and j < len(right):
            if left[i] < right[j]:
                arr[k] = left[i]
                i += 1
            else:
                arr[k] = right[j]
                j += 1
            k += 1

        while i < len(left):
            arr[k] = left[i]
            i += 1
            k += 1

        while j < len(right):
            arr[k] = right[j]
            j+= 1
            k += 1

arr = [12, 11, 13, 5, 6, 7]
merge_sort(arr)
print(arr)

python--排序总结

c.复杂度

时间复杂度最好情况O(nlog2n),

时间复杂度最坏情况O(nlog2n),

时间复杂度平均情况O(nlog2n),

空间复杂度最好情况O(n),

d.稳定性

稳定

文章出处登录后可见!

已经登录?立即刷新

共计人评分,平均

到目前为止还没有投票!成为第一位评论此文章。

(0)
社会演员多的头像社会演员多普通用户
上一篇 2023年3月2日 下午10:08
下一篇 2023年3月2日 下午10:09

相关推荐