排序算法

标签（空格分隔）： algorithm

冒泡排序

遍历n趟，每趟把最大的数交换到尾部

def bubble_sort(nums, n):
    i = n-1
    while i > 0:
        last = 0
        for j in range(0, i):
            if nums[j] > nums[j+1]:
                nums[j], nums[j+1] = nums[j+1], nums[j]
                last = j
        # 如果这一趟没有发生交换，说明已有序，终止遍历（last=0）
        i = last

• 时间复杂度 O(n^2)
• 稳定的排序方法

简单选择排序

遍历n趟，设定(0,n-1)段位有序段，后面为无序段，每趟遍历从无序段找到最小的数放入有序段尾部

def select_sort(nums, n):
    i = 0
    while i < n:
        min_index = i
        for j in range(i+1, n):
            if nums[min_index] > nums[j]:
                min_index = j
        
        if min_index != i:
            nums[min_index], nums[i] = nums[i], nums[min_index]
        i += 1

• 时间复杂度 O(n^2)
• 不稳定的排序方法
  对于序列: [48] 36 68 72 12 (48) 02
  最终结果: 02 12 36 (48) [48] 68 72

直接插入排序

设定第一个元素为有序序列，然后将剩余n-1个元素依次插入该序列，每次插入保证该序列有序

def insert_sort(nums, n):
    i = 1
    while i < n:
        j = i
        tmp = nums[i]
        while j > 0 and tmp < nums[j-1]:
            # 如果tmp < nums[j-1], tmp要插在nums[j-1]前面
            # 将nums[j-1]向后移动
            nums[j] = nums[j-1]
            j -= 1
        nums[j] = tmp
        i += 1

• 时间复杂度 O(n^2)
• 稳定的排序算法
  PS: 如果将tmp < nums[j-1]改成tmp <= nums[j-1]，就是不稳定的

快速排序

在序列中选取某个元素R，将小于R的元素放在R左侧，大于R的放在R右侧，然后再分别对R左侧和R右侧的序列进行快速排序，直到子序列为空或只有一个元素。

def quick_sort(nums, n):
    q_sort(nums, 0, n-1)

def q_sort(nums, left, right):
    # nums[left]为元素R
    if left < right:
        i, j = left, right
        while i < j:
            while nums[i] < nums[left]:
                i += 1
            while nums[j] > nums[left]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        # 元素R的最终位置为j
        nums[left], nums[j] = nums[j], nums[left]
        
        q_sort(nums, left, j-1)
        q_sort(nums, j+1, right)

• 时间复杂度: O(nlogn)
• 不稳定的排序算法

两路合并排序

将有n个元素的序列看n个长度为1的有序子序列，然后两两合并，得到?n/2?个长度为2或1的有序子序列；再两两合并，……，直到得到长度为n的有序序列时结束。

def merge_sort(nums, n):
    # i1, i2是子序列1的下、上界，j1, j2是子序列2的下、上界
    i1, i2, j1, j2 = 0, 0, 0, 0
    size = 1
    while size < n:
        i1 = 0
        while i1+size < n:
            j1 = i1 + size
            i2 = j1 - 1
            j2 = j1 + size -1
            # j2有又可能越界
            if j2 > n-1:
                j2 = n-1
            merge(nums, i1, i2, j1, j2)
            i1 = j2+1
        
        size *= 2

def merge(nums, i1, i2, j1, j2):
    # i1, i2是子序列1的下、上界，j1, j2是子序列2的下、上界
    tmp = []
    i, j = i1, j1
    while i <= i2 and j <= j2:
        if nums[i] < nums[j]:
            tmp.append(nums[i])
            i += 1
        else:
            tmp.append(nums[j])
            j += 1
    while i <= i2:
        tmp.append(nums[i])
        i += 1
    while j <= j2:
        tmp.append(nums[j])
        j += 1
    
    for i in range(i1, i1+len(tmp)):
        nums[i] = tmp[i-i1]

• 时间复杂度：O(nlogn)
• 空间复杂度：O(n)
  需要借助辅助数组存储临时数据
• 稳定的排序方法

常见排序算法

原文：https://www.cnblogs.com/Zioyi/p/14090840.html