排序算法

标签（空格分隔）： 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趟。第i趟遍历时，设定(0,i-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+1
        while i < j:
            i += 1
            j -= 1
            while i <= right and nums[i] < nums[left]:
                i += 1
            while j >= left and nums[j] > nums[left]:
                j -= 1
            if i < j:
                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)
  需要借助辅助数组存储临时数据
• 稳定的排序方法

堆排序

为得到非递减序列，使用最大堆。将初始序列构造成最大堆，第一趟排序，将堆顶元素A[0]和堆底元素A[n-1]交换位置，A[0]向下调整，使得前n-1个元素还是堆；第i趟，将A[0]和A[n-i]交换，A[0]向下调整，使得前n-i个元素还是堆，直到第n趟结束。

def heap_sort(nums, n):
    # 构造最大堆
    for i in range((n-2)//2, -1, -1):
        adjust_down(nums, i, n-1)
    for i in range(n-1, 0, -1):
        nums[0], nums[i] = nums[i], nums[0]
        adjust_down(nums, 0, i-1)
        

def adjust_down(nums, r, j):
    child = 2 * r + 1
    tmp = nums[r]
    while child <= j:
        if child < j and nums[child] < nums[child+1]:
            child += 1
        if tmp >= nums[child]:
            break
        nums[(child-1)//2] = nums[child]
        child = child * 2 + 1
    nums[(child-1)//2] = tmp

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