python实现各种算法详解,以及时间复杂度

python实现各种排序

1. 快速排序

1:首先取序列第一个元素为基准元素pivot=R[low]。i=low,j=high。

2:从后向前扫描,找小于等于pivot的数,如果找到,R[i]与R[j]交换,i++。

3:从前往后扫描,找大于pivot的数,如果找到,R[i]与R[j]交换,j--。

4:重复2~3,直到i=j,返回该位置mid=i,该位置正好为pivot元素。 完成一趟排序后,以mid为界,将序列分为两部分,左序列都比pivot小,有序列都比pivot大,然后再分别对这两个子序列进行快速排序。

以序列(30,24,5,58,16,36,12,42,39)为例,进行演示:

1、初始化,i=low,j=high,pivot=R[low]=30:

i j
30 24 5 58 16 26 12 41 39

2、从后往前找小于等于pivot的数,找到R[j]=12

i j
30 24 5 58 16 26 12 41 39
  • R[i]与R[j]交换,i++
i j
12 24 5 58 16 26 30 41 39

3、从前往后找大于pivot的数,找到R[i]=58

i j
12 24 5 58 16 26 30 41 39
  • R[i]与R[j]交换,j--
i j
12 24 5 30 16 26 58 41 39

4、从后往前找小于等于pivot的数,找到R[j]=16

i j
12 24 5 30 16 26 58 41 39
  • R[i]与R[j]交换,i++
i,j
12 24 5 16 30 26 58 41 39

5、从前往后找大于pivot的数,这时i=j,第一轮排序结束,返回i的位置,mid=i

Low mid-1 mid mid+1 High
12 24 5 16 30 26 58 41 3

此时已mid为界,将原序列一分为二,左子序列为(12,24,5,18)元素都比pivot小,右子序列为(36,58,42,39)元素都比pivot大。然后在分别对两个子序列进行快速排序,最后即可得到排序后的结果。

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

    li[j] = pivot
    quicksort(low,i-1,li)
    quicksort(i+1,high,li)
    return li



lists=[30,24,5,58,18,36,12,42,39]
print("排序前的序列为:")
for i in lists:
    print(i,end =" ")
print("\n排序后的序列为:")
for i in quicksort(0,len(lists)-1,lists):
    print(i,end=" ")

2. 冒泡排序

冒泡排序(英语:Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端。

冒泡排序算法的运作如下:

  • 比较相邻的元素。如果第一个比第二个大(升序),就交换他们两个。
  • 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
  • 针对所有的元素重复以上的步骤,除了最后一个。
  • 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。

def bubblesort(li):
    for i in range(len(li)-1,0,-1):
        for j in range(1,i):
            if li[j-1]>li[j]:
                li[j-1],li[j] = li[j],li[j-1]

    return li

li = [54,26,93,17,77,31,44,55,20]
print(bubblesort(li))

3. 插入排序

插入排序(Insertion Sort)是一种简单直观的排序算法。它的工作原理是:通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

  1. 从第一个元素开始,该元素可以认为已经被排序;
  2. 取出下一个元素,在已经排序的元素序列中从后向前扫描;
  3. 如果该元素(已排序)大于新元素,将该元素移到下一位置;
  4. 重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
  5. 将新元素插入到该位置后;
  6. 重复步骤2~5。

这个算法和冒泡排序有点类似,都是两层for循环,一个是从正面挨个比,一个是倒着比

def insertsort(li):
    for i in range(1,len(li)):
        for j in range(i,0,-1):
            if li[j-1]>li[j]:
                li[j-1],li[j] = li[j],li[j-1]

    return li

li = [54,26,93,17,77,31,44,55,20]
print(insertsort(li))

4. 希尔排序

希尔排序是先取一个小于待排序列表长度的正整数d1,把所有距离为d1的数据看成一组,在组内进行插入排序。然后取一个小于d1的正整数d2,继续用d2分组和进行组内插入排序。每次取的分组距离越来越小,组内的数据越来越多,直到di=1,所有数据被分成一组,再进行插入排序,则列表排序完成。

希尔排序是基于插入排序进行优化的排序算法。在插入排序中,如果数据几乎已经排好序时,效率是很高的(想一下抓牌和插牌),时间复杂度为 O(n) 。但数据的初始状态并不一定是“几乎已经排好序”的,用插入排序每步只能将待插入数据往前移动一位,而希尔排序将数据分组后,每次可以往前移动di位,在di>1时进行的分组和组内排序可以将数据变成“几乎排好序”的状态,此时再进行最后一次插入排序,提高效率。

希尔排序的原理如下:

  1. 选择小于待排序列表长度 n 的正整数序列 d1,d2,...,di,其中 n>d1, d(i-1)>di, di=1 ,作为数据的间隔距离对列表进行分组。这里对 di 的取值和个数没有要求,只要是整数,d1<n,依次变小即可。

  2. 依次用 d1, ..., di 作为数据的距离对列表进行分组和组内插入排序,一共需要进行 i 轮排序。

  3. 在最后一轮排序前,列表中的数据达到了“几乎排好序”的状态,此时进行最后一轮插入排序。

以列表 [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21] 进行升序排列为例。

要进行升序排列,则分组后所有组内插入排序都进行升序排列。本例中以列表长度的length/3作为初始的分组距离 d1 ,d1=4。

  1. 从列表的开头开始,对所有数据按 d1 作为距离进行分组,分组只保证数据的间隔距离相等,不保证每组的数据个数一样,只是本例中刚好每组数据一样多。本例的数据可以分为4组,也就是第1,5,9作为排序对象,然后2,6,10;3,7,11;4,8,12.一共要排序4次。排完序为

  2. 第二次排序的话,这个距离为4//3 = 1,也就是最后一轮排序。这也和直接插入排序完全一样了,先将第一个数据作为已排序序列,后面的数据作为未排序序列,然后依次将未排序序列中的数据插入到已排序序列中。

def shellsort(li):
    n = len(li)
    gap = n//3
    while gap > 0:
        for i in range(gap,n):
            j = i
            while j>=gap and li[j-gap]>li[j]:
                li[j-gap],li[j] = li[j],li[j-gap]
                j -= gap
        gap = gap//3

alist = [54,26,93,17,77,31,44,55,20]
shellsort(alist)
print(alist)

5. 归并排序

将原问题划分成 n 个规模较小而结构与原问题相似的子问题;递归地解决这些问题,然后再合并其结果,就得到原问题的解。从上图看分解后的数列很像一个二叉树。

归并排序采用分而治之的原理:

  1. 将一个序列从中间位置分成两个序列;
  2. 在将这两个子序列按照第一步继续二分下去;
  3. 直到所有子序列的长度都为1,也就是不可以再二分截止。这时候再两两合并成一个有序序列即可。

def merge(left,right):
    r,l = 0,0
    res = []
    while r < len(right) and l < len(left):
        if left[l] < right[r]:  # 排序,小于等于的放左边
            res.append(left[l])
            l += 1
        else:
            res.append(right[r])  # 排序,大的放右边
            r += 1
    res +=(left[l:])
    res +=(right[r:])
  
    return res

def mergesort(li):
    if(len(li)) <2:
        return li

    mid = len(li)//2
    left = mergesort(li[:mid])
    right = mergesort(li[mid:])
    return merge(left,right)



li = [8,0,4,3,6,2]
print(mergesort(li))

6. 选择排序

选择排序(Selection sort)是一种简单直观的排序算法。它的工作原理如下。首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕。

选择排序的主要优点与数据移动有关。如果某个元素位于正确的最终位置上,则它不会被移动。选择排序每次交换一对元素,它们当中至少有一个将被移到其最终位置上,因此对n个元素的表进行排序总共进行至多n-1次交换。在所有的完全依靠交换去移动元素的排序方法中,选择排序属于非常好的一种。

def selection_sort(alist):
    n = len(alist)
    # 需要进行n-1次选择操作
    for i in range(n-1):
        # 记录最小位置
        min_index = i
        # 从i+1位置到末尾选择出最小数据
        for j in range(i+1, n):
            if alist[j] < alist[min_index]:
                min_index = j
        # 如果选择出的数据不在正确位置,进行交换
        if min_index != i:
            alist[i], alist[min_index] = alist[min_index], alist[i]

alist = [54,226,93,17,77,31,44,55,20]
selection_sort(alist)
print(alist)

7. 堆排序

堆排序(Heap Sort)是利用堆这种数据结构而设计的一种排序算法,是一种选择排序。

堆是具有以下性质的完全二叉树:每个结点的值都大于或等于其左右孩子结点的值,称为大顶堆;或者每个结点的值都小于或等于其左右孩子结点的值,称为小顶堆。

堆排序思路为: 将一个无序序列调整为一个堆,就能找出序列中的最大值(或最小值),然后将找出的这个元素与末尾元素交换,这样有序序列元素就增加一个,无序序列元素就减少一个,对新的无序序列重复操作,从而实现排序。

算法实现步骤

  1. 构造初始堆。将给定无序序列构造成一个大顶堆(一般升序采用大顶堆,降序采用小顶堆);
  2. 将堆顶元素与末尾元素进行交换,使末尾元素最大。然后继续调整堆,再将堆顶元素与末尾元素交换,得到第二大元素;
  3. 重新调整结构,使其满足堆定义,然后继续交换堆顶元素与当前末尾元素;
  4. 如此反复进行交换、重建、交换,直到整个序列有序。
def heap_sort(array):
    first = len(array) // 2 - 1
    for start in range(first, -1, -1):
        # 从下到上,从右到左对每个非叶节点进行调整,循环构建成大顶堆
        big_heap(array, start, len(array) - 1)
    for end in range(len(array) - 1, 0, -1):
        # 交换堆顶和堆尾的数据
        array[0], array[end] = array[end], array[0]
        # 重新调整完全二叉树,构造成大顶堆
        big_heap(array, 0, end - 1)
    return array


def big_heap(array, start, end):
    root = start
    # 左孩子的索引
    child = root * 2 + 1
    while child <= end:
        # 节点有右子节点,并且右子节点的值大于左子节点,则将child变为右子节点的索引
        if child + 1 <= end and array[child] < array[child + 1]:
            child += 1
        if array[root] < array[child]:
            # 交换节点与子节点中较大者的值
            array[root], array[child] = array[child], array[root]
            # 交换值后,如果存在孙节点,则将root设置为子节点,继续与孙节点进行比较
            root = child
            child = root * 2 + 1
        else:
            break


if __name__ == '__main__':
    array = [10, 17, 50, 7, 30, 24, 27, 45, 15, 5, 36, 21]
    print(heap_sort(array))

8. 计数排序

计数排序(Counting Sort)是一种不比较数据大小的排序算法,是一种牺牲空间换取时间的排序算法。

计数排序适合数据量大且数据范围小的数据排序,如对人的年龄进行排序,对考试成绩进行排序等。

计数排序先找到待排序列表中的最大值 k,开辟一个长度为 k+1 的计数列表,计数列表中的所有初始值都为 0。走访待排序列表,如果走访到的元素值为 i,则计数列表中索引 i 的值加1,走访完整个待排序列表,就可以统计出待排序列表中每个值的数量。然后创建一个新列表,根据计数列表中统计的数量,依次在新列表中添加对应数量的 i ,得到排好序的列表。

def counting_sort(array):
    if len(array) < 2:
        return array
    max_num = max(array)
    count = [0] * (max_num + 1)
    for num in array:
        count[num] += 1
    new_array = list()
    for i in range(len(count)):
        for j in range(count[i]):
            new_array.append(i)
    return new_array
 
 
if __name__ == '__main__':
    array = [5, 7, 3, 7, 2, 3, 2, 5, 9, 5, 7, 6]
    print(counting_sort(array))

9. 桶排序

桶排序(Bucket sort)是一种通过分桶和合并实现的排序算法,又被称为箱排序。

桶排序先将数据分到有限数量的桶里,然后对每一个桶内的数据进行排序(桶内排序可以使用任何一种排序算法,如快速排序),最后将所有排好序的桶合并成一个有序序列,列表排序完成。

桶排序需要占用很多额外的空间,对桶内数据进行排序,选择哪种排序算法对于性能的影响至关重要。桶排序适用的场景并不多,用得多一点的是基于桶排序思想的计数排序和基数排序。

桶排序的原理如下:

  1. 求出待排序列表中的最大值和最小值,得到数据的范围。

  2. 根据数据的范围,选择一个适合的值构建有限数量的桶,确定每个桶的数据范围。如数据范围是[0,100),将数据分成10个桶,第一个桶为[0,10),第二个桶为[10,20),以此类推。

  3. 将待排序列表中的数据分配到对应的桶中。

  4. 对每一个桶内的数据进行排序,这里可以采用任意一种排序算法,建议采用时间复杂度小的排序算法。

  5. 将所有桶中的数据依次取出,添加到一个新的有序序列中,列表排序完成。

# coding=utf-8
def bucket_sort(array):
    min_num, max_num = min(array), max(array)
    bucket_num = (max_num-min_num)//3 + 1
    buckets = [[] for _ in range(int(bucket_num))]
    for num in array:
        buckets[int((num-min_num)//3)].append(num)
    new_array = list()
    for i in buckets:
        for j in sorted(i):
            new_array.append(j)
    return new_array
 
 
if __name__ == '__main__':
    array = [5, 7, 3, 7, 2, 3, 2, 5, 9, 5, 7, 8]
    print(bucket_sort(array))

热门相关:斗神战帝   仗剑高歌   时间都知道   仗剑高歌   苏醒的秘密