排序算法总结

算法
, ,

排序可以分为比较排序和非比较排序。比较排序有插入排序、希尔排序、选择排序、冒泡排序、快速排序、堆排序和归并排序；非比较排序有桶排序、基数排序和计数排序。

稳定排序：在排序前有 xi=xj，且 xi 排在 xj 前面，在排序后仍然是 xi 排在 xj 前面，则这种排序算法是稳定的。

o(nlogn) 时间复杂度的有：快速排序、堆排序、归并排序。

插入排序

顺序地把待排序序列中的各个记录按其关键字的大小，插入到已排序的序列的适当位置。
开始排序时，认为序列的第一个记录已排好序，然后将第二个记录与其进行比较交换，则第二个记录插入到已排好序的序列中。
之后的 arr[i] 与前 i-1 个记录进行比较，将其插入到比他小的记录的后面。
从后往前比较，把所有比当前待排序的记录更大的数都往后移动一位。

1
2
3
4
5
6
7
8
9
def insert_sort(arr):
    for i in range(1, len(arr)):
        tmp = arr[i]
        j = i
        while j and tmp < arr[j-1]:
            arr[j] = arr[j-1]
            j -= 1
        arr[j] = tmp
    return arr

冒泡排序

将第一个记录 arr[0] 与第二个记录 arr[1] 比较，若 arr[0]>arr[1]，则交换，以此类推到最后一个记录，一次冒泡的结果将数组中最大的数排到 arr 末尾。
外层 for 控制排序的执行次数，内层 for 控制一次排序中相邻记录的比较和交换，一共要执行 n 次冒泡，每次冒泡比较次数为 n-i ，因此时间复杂度 O(n2) 。相邻元素相等时没有发生交换，因此冒泡排序是稳定的。

1
2
3
4
5
6
7
def bubble_sort(arr):
    length = len(arr)
    for i in range(length):
        for j in range(length-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]  #1
    return arr

备注：

  1. python 交换两个元素不需要中间变量 a,b = b,a
  2. 算法改进：
    优化 1：若某一次遍历没有发生数据交换，则数组已经排好序，无需继续冒泡，设置一个 flag 来标明没有发生交换的时候
1
2
3
4
5
6
7
8
9
10
11
def bubble_sort1(arr):
    length = len(arr)
    for i in range(length):
        flag = 1 ###
        for j in range(length-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                flag = 0 ###
        if flag:
            break # 已排好序，直接跳出
    return arr

优化 2：记录每次遍历最后发生交换的位置，则该位置后面已经排好序，则下次冒泡只需遍历该位置之前的数组

1
2
3
4
5
6
7
8
9
10
11
12
13
def bubble_sort2(arr):
    length = len(arr)
    k = length-1 # j的循环范围
    for i in range(length):
        flag = 1
        for j in range(k):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
                k = j # 记录最后一次交换的位置
                flag = 0
        if flag:
            break # 已排好序，直接跳出
    return arr

快速排序

快速排序采用分治思想，以第一个数 arr[0] 作为基准，通过一趟排序将数据分成两部分，比 arr[0] 小的数排在左边，比 arr[0] 大的数排在右边，再对这两个部分进行快排，所有序列长度为1时则序列已排好序。

快速排序的时间复杂度为 O(nlogn)，空间复杂度 O(n)
首先就一次快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；

  • 最优的情况下空间复杂度为：O(logn) ；每一次都平分数组的情况
  • 最差的情况下空间复杂度为：O( n ) ；退化为冒泡排序的情况

大小相同的元素可能会交换顺序，因此快速排序是不稳定排序

快速排序的总体平均效率是最好的，但并不是任何时刻都最优。 最差的情况是如果数组已经排好序，时间复杂度会变为 O(n2)。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def quick_sort(arr, left, right):
    if left >=  right:
        return 
    low = left
    high = right
    key = arr[left]
    while left < right: 
        while left < right and arr[right] >= key:  #1
            right -= 1
        arr[left] = arr[right]
        while left < right and arr[left] <= key:
            left += 1
        arr[right] = arr[left]
    arr[left] = key
    quick_sort(arr, low, left-1)
    quick_sort(arr, left + 1, high)

备注：1. 必须要再加一层 while left < right，否则没有终止条件，会出现数组越界

堆排序

堆是以一维数组实现的，可以被看成一个完全二叉树，树上的每个结点对应数组的一个元素。除了最底层外，该树是完全充满的，而且是从左往右填充。

最大堆：除根结点以外的所有结点 i 都满足 a[parent(i)] >= a[i]，即非叶子结点的大于等于左右孩子的值; 即最大堆的最大元素存放在根节点中，用于升序排序。每次取出最大堆的根节点，之后需要调整堆，使得剩下的结点组成一个最大堆。

第 i 个结点 a[i] 的父元素为 a[(i-1)/2]
第 i 个结点 a[i] 的左孩子为 a[2i+1]
第 i 个结点 a[i] 的右孩子为 a[2i+2]

调整堆 max_heapify

  1. 调整堆是自顶向下，从最后一个非叶子结点开始，从左至右，从上到下依次进行调整，使得子节点不超过父节点的值。
  2. 比较 i 的根节点与其左右孩子的大小， 当 a[i] < a[2i+1]，则将根节点的值与左孩子的值互换； 当 a[i] < a[2i+2]，则将根节点的值与右孩子的值互换。
  3. 迭代调用上述过程。

建立最大堆 build_max_heap

  1. 建立最大堆是自底向上，利用 max_heapify() 来将数组转化为最大堆。
  2. 长度为 n 的数组构建的堆的最后一个非叶子结点下标为 n/2-1，从该结点开始，往前逐步调整堆，直到根节点。

堆排序 heap_sort

  1. 利用 build_max_heap() 和 max_heapify() 进行操作。首先建立最大堆。
  2. 将堆的根节点与最后一个结点交换， 将前面的 len-1 个结点做调整堆的过程，直到所有结点取出。对于 n 个结点需要做 n-1 次操作。

堆排序的时间复杂度为 o(nlogn)，调整堆需要 o(logn) 的时间，一共需要调整 n 次。
堆排序的空间复杂度为 o(1)。堆排序是不稳定排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
def max_heapify(heap, heap_size, root):
    left = 2 * root + 1
    right = 2 * root + 2
    largest = root
    if left < heap_size and heap[largest] < heap[left]:
        largest = left
    if right < heap_size and heap[largest] < heap[right]:
        largest = right
    if largest != root:
        heap[largest], heap[root] = heap[root], heap[largest]
        max_heapify(heap, heap_size, largest)

def build_max_heap(heap):
    heap_size = len(heap)
    for i in range((heap_size//2)-1, -1, -1):
        max_heapify(heap, heap_size, i)

def heap_sort(heap):
    build_max_heap(heap)
    for i in range(len(heap)-1, -1, -1):
        heap[0], heap[i] = heap[i], heap[0]
        max_heapify(heap, i, 0)
    return heap

归并排序

归并排序：将两个或者两个以上的有序序列合并成一个新的有序序列。

基本思想：采用分治思想，将原始序列看做 n 个有序的子序列，然后不断合并起来。

  1. 将原始序列分为 n 个长度为 1 的子序列，并把相邻的子序列两两合并为单位为 2 的子序列。
  2. 重复上述操作，按顺序成对进行归并，直到整个序列有序。

总共进行 logn 次归并，每次归并最多比较 n 次，因此时间复杂度为 O(nlogn), 空间复杂度为 O(n) [复杂度较差]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
def merge(left, right):
    i, j = 0, 0
    res = []
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            res.append(left[i])
            i += 1
        else:
            res.append(right[j])
            j += 1
    res.extend(left[i:])
    res.extend(right[j:])
    return res

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid]) # 通过递归将原始序列拆为 n 个长度为 1 的子序列
    right = merge_sort(arr[mid:])
    return merge(left, right)

桶排序

暂未总结

Leetcode 排序相关

Insertion Sort List

Leetcode : 147. Insertion Sort List (Medium)

用插入排序对链表进行排序。
链表不能像数组一样，从后往前遍历，必须要从起始节点往后遍历。

由于可能会改变链表表头，用 dummy 创建辅助节点，并用在每次遍历时，用 pre 记录下 dummy 节点，表示当前节点 cur 前面的节点。 实际上需要进行操作的节点是 cur.next。

当 cur.val > cur.next.val 时，说明 cur.next 需要插入到已经排好序的前面的链表中，因此循环一遍前面的链表，当 cur.next.val < pre.next.val 时，说明 cur.next 节点需要插入到 pre 的后面，cur.next.next 的前面。

要移动的节点需要先保存下来，即 tmp = cur.next, 之后再进行移动。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
def insertionSortList(self, head):
    if not head or not head.next:
        return head
    dummy = ListNode(0)
    dummy.next = head
    cur = head
    while cur.next:
        if cur.val > cur.next.val:
            pre = dummy
            while cur.next.val >= pre.next.val:
                pre = pre.next
            tmp = cur.next
            cur.next = cur.next.next
            tmp.next = pre.next
            pre.next = tmp
        else:
            cur = cur.next
    return dummy.next

Sort List

Leetcode : 148. Sort List (Medium)

要求时间复杂度为 O(nlogn), 空间复杂度为 O(1)

用到归并排序，链表排序不需要像数组排序一样开辟一个新的数组用于存储，因此空间复杂度变为 O(1)。
利用快慢指针法找到链表的中点，将链表分成两个部分，两个部分排好序后，再将其归并。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution:
    def sortList(self, head):
        if not head or not head.next:
            return head
        fast = slow = head
        while fast.next and fast.next.next:
            slow = slow.next
            fast = fast.next.next
        right = self.sortList(slow.next)
        slow.next = None
        left = self.sortList(head)
        return self.merge(left, right)
    
    def merge(self, left, right):
        dummy = ListNode(0)
        cur = dummy
        while left and right:
            if left.val <= right.val:
                cur.next = left
                left = left.next
            else:
                cur.next = right
                right = right.next
            cur = cur.next
        if left:
            cur.next = left
        if right:
            cur.next = right
        return dummy.next

Largest Number

Leetcode : 179. Largest Number (Medium)

1
2
3
4
5
6
7
8
9
10
11
from functools import cmp_to_key

class Solution:
    def largestNumber(self, nums):
        """
        :type nums: List[int]
        :rtype: str
        """
        nums = [str(x) for x in nums]
        nums.sort(key = cmp_to_key(lambda a, b: 1 if a+b<b+a else -1))       
        return ''.join(nums) if nums[0] != '0' else '0'

Kth Largest Element in an Array

Leetcode : 215. Kth Largest Element in an Array (Medium)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
class Solution(object):
    def findKthLargest(self, nums, k):
        if k > len(nums) or k <= 0:
            return None
        left, right = 0, len(nums)-1
        while left <= right:
            mid = self.quick_sort(nums, left, right)
            if mid == len(nums) - k:
                return nums[mid]
            elif mid < len(nums) - k:
                left = mid + 1
            else:
                right = mid - 1
        
    def quick_sort(self, nums, left, right):
        key = nums[left]
        while left < right:
            while left < right and nums[right] >= key:
                right -= 1
            nums[left] = nums[right]
            while left < right and nums[left] <= key:
                left += 1
            nums[right] = nums[left]
        nums[left] = key
        return left