python排序算法

Posted on | In

冒泡排序

冒泡排序的思想: 每次比较两个相邻的元素, 如果他们的顺序错误就把他们交换位置

比如有五个数: 12, 35, 99, 18, 76, 从大到小排序, 对相邻的两位进行比较

  • 第一趟:
  • 第一次比较: 35, 12, 99, 18, 76
  • 第二次比较: 35, 99, 12, 18, 76
  • 第三次比较: 35, 99, 18, 12, 76
  • 第四次比较: 35, 99, 18, 76, 12

经过第一趟比较后, 五个数中最小的数已经在最后面了, 接下来只比较前四个数, 依次类推

  • 第二趟
    99, 35, 76, 18, 12
  • 第三趟
    99, 76, 35, 18, 12
  • 第四趟
    99, 76, 35, 18, 12
    比较完成

冒泡排序原理: 每一趟只能将一个数归位, 如果有n个数进行排序,只需将n-1个数归位, 也就是说要进行n-1趟操作(已经归位的数不用再比较)

时间复杂度：O(n²) 

1
2
3
4
5
6
def my_sort(num):
    l = len(num)
    for i in range(l-1):
        for j in range(l-1-i):
            if num[j] < num[j+1]:
                num[j], num[j+1] = num[j+1], num[j]

快速排序

快速排序使用分治法（Divide and conquer）策略来把一个序列（list）分为两个子序列（sub-lists），从数列中挑出一个元素，称为 “基准”（pivot）；
重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。在这个分区退出之后，该基准就处于数列的中间位置

时间复杂度O(nlog₂n)

1
2
3
4
5
6
7
8
def quicksort(li):
    if len(li)<=1:
        return li
    op = li[0]
    left = [x for x in li if x < op]
    mid = [x for x in li if x == op]
    right = [x for x in li if x > op]
    return quicksort(left)+mid+quicksort(right)

插入排序

插入排序：选定元素，分别与列表中的元素比较，小的在左边，大的在右边

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

重复步骤2~5。

1
2
3
4
5
6
7
8
9
def insertsort(li):
    l = len(li)
    for i in range(1,l):
        value = li[i]
        j = i -1
        while j<=0 and value<li[j]:
            li[j+1] = li[j]
            j = j-1
        li[j+1]=value

选择排序

选择排序就是要首先选定一个元素认为为最小的，之后比较其他，如果小于之前的，换更换列表所在位置。

时间复杂度：O(n²)

1
2
3
4
5
6
7
8
def changesort(li):
    leng = len(li)
    for i in range(leng-1):
        index =i
        for j in range(i+1,leng):
            if li[j] < li[index]:
                index = j
        li[index], li[i] = li[i], li[index]

归并排序

归并排序：采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并
时间复杂度：O(nlog₂n)

归并排序也就是将列表中的元素分成两个长度为n/2的子序列，进行比较，之后合在一起

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def merge_sort(list1):#merge_sort是按照len(list1)//2分开，知道分成两两比较大小
    if len(list1)<=1:
        return list1
    mid=len(list1)//2
    left=merge_sort(list1[:mid])
    right=merge_sort(list1[mid:])
    return merge(left,right)
def merge(left,right):#mere函数主要是左右两边每次取一个数进行比较，小的加入到result中
    result=[]
    while len(left)and len(right):
        if left[0]<right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    if len(left)!=0:
        result+=left
    elif len(right)!=0:
        result+=right
    return result

堆排序

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

大顶堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2] 父节点i的左子节点在位置(2i+1); 父节点i的右子节点在位置(2i+2)

小顶堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

堆排序：

  1. 将无序列表构建最大堆，根节点为最大元素
  2. 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def heap_sort(hlist):
    def heap_adjust(parent):
        child = 2 * parent + 1  # left child
        while child < len(heap):
            if child + 1 < len(heap):
                if heap[child + 1] > heap[child]:
                    child += 1  # right child,比较左右结点的大小，选出最大的元素
            if heap[parent] >= heap[child]:
                break
            heap[parent], heap[child] = heap[child], heap[parent]#把最大的结点与父节点交换
            parent, child = child, 2 * child + 1#往二叉树下面走，继续去比较，选出最大放到根节点，知道所有元素比较完退出
 
    heap, hlist = copy.copy(hlist), []
    for i in range((len(heap)-2)// 2, -1, -1):#(len(heap)-2)// 2为二叉树层数，k=3,i=3,2,1,0
        heap_adjust(i)
    while len(heap) != 0:
        heap[0], heap[-1] = heap[-1], heap[0]
        hlist.insert(0, heap.pop())#第一个替换成heap最后一个
        heap_adjust(0)
    return hlist

时间复杂度O(nlog₂n)，不稳定

希尔排序

希尔排序将元素先平分，gap=len(list1)//2,按照gap去比较，一次//2,直到gap为1，
例如：gap=4,0-4,1-5,2-6，3-7,4-8,5-9去比较大小，若小于前面的,则交换位置。

时间复杂度：O(n) 

1
2
3
4
5
6
7
8
9
def Shell_sort(list1):
    gap=len(list1)
    while gap>1:
        gap=gap//2  #若len(list1)=9,gap=4,3,2,1
        for i in range(gap,len(list1)):
            for j in range(i%gap,i,gap):
                if list1[i]<list1[j]:
                    list1[j],list1[i]=list1[i],list1[j]
    print(list1)