快速排序

快速排序の简约版

• 容易理解

• 效率不够高,因为不是原地排序,两次遍历,产生了中间列表,

  def quick_sort(arr):
  
  # 递归出口
  if len(arr) <= 1:
      return arr
  
  # 列表的第1个元素作为pivot
  # 遍历列表的第2个元素到结束的元素
  # 大于pivot的放在left列表
  # 小于pivot的放在right列表
  else:
      pivot = arr[0]
      left = [i for i in arr[1:] if i < pivot]
      right = [i for i in arr[1:] if i >= pivot]
      return quick_sort(left) + [pivot] + quick_sort(right)
  

快速排序の双指针版

• 效率更高
• 较难理解双指针循环结束的位置

def partition(arr, low, high):
    pivot_index = low
    pivot = arr[pivot_index]
    left = pivot_index + 1
    right = high - 1
    while True:

        # 从arr的第2个元素遍历,left索引小于等于right,并且left元素小于pivot时,left+1继续循环,直到条件不满足
        # 退出循环时,证明left>right 或者 arr[left] >pivot
        while left <= right and arr[left] < pivot:
            left += 1
        while right >= left and arr[right] >= pivot:
            right -= 1

        # 循环出口
        if left > right:
            break
        else:
            arr[left], arr[right] = arr[right], arr[left]

    # 上面循环结束时,right就是arr分界线的索引
    arr[pivot_index], arr[right] = arr[right], arr[pivot_index]
    return right

def quick_sort(arr, low, high):
    if low < high:
        pivot = partition(arr, low, high)
        quick_sort(arr, low, pivot)
        quick_sort(arr, pivot + 1, high)

import random

arr = list(range(20))
random.shuffle(arr)
print(arr)
quick_sort(arr, 0, len(arr))
print(arr)

快速排序の算法导论版

# Python program for implementation of Quicksort Sort

# This function takes last element as pivot, places
# the pivot element at its correct position in sorted
# array, and places all smaller (smaller than pivot)
# to left of pivot and all greater elements to right
# of pivot
def partition(arr, low, high):
    i = (low - 1)  # index of smaller element
    pivot = arr[high]  # pivot

    for j in range(low, high):

        # If current element is smaller than or
        # equal to pivot
        if arr[j] <= pivot:
            # increment index of smaller element
            i = i + 1
            arr[i], arr[j] = arr[j], arr[i]

    arr[i + 1], arr[high] = arr[high], arr[i + 1]
    return i + 1


# The main function that implements QuickSort
# arr[] --> Array to be sorted,
# low --> Starting index,
# high --> Ending index

# Function to do Quick sort
def quickSort(arr, low, high):
    if low < high:
        # pi is partitioning index, arr[p] is now
        # at right place
        pi = partition(arr, low, high)

        # Separately sort elements before
        # partition and after partition
        quickSort(arr, low, pi - 1)
        quickSort(arr, pi + 1, high)


arr = [10, 5, 8, 7, 6]
n = len(arr)
quickSort(arr, 0, n - 1)
print("Sorted array is:")
print(arr)

冒泡排序

• 时间复杂度:算法计算过程中所需要的计算工作量

# 冒泡排序
# 两个相邻的数字比较,小的左移,大的右移
# 时间复杂度O(n^2)
list1 = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1]


def bubble_sort(iterable):
    n = len(iterable)

    # 遍历所有的元素
    for i in range(0, n):

        # 最后一个元素已经排好,第i次遍历时,已经排好了i个元素
        for j in range(0, n-1-i):
            if iterable[j] > iterable[j + 1]:
                iterable[j], iterable[j + 1] = iterable[j + 1], iterable[j]
    return iterable


list2 = bubble_sort(list1)
print(list2)

装饰器

• 实现一个装饰器,打印函数运行时的时间戳

import time


def run_time(func):
    def wrapper(*args, **kwargs):
        print(time.time())
        func(*args, **kwargs)

    return wrapper


@run_time
def run(*args, **kwargs):
    print(args)
    print(kwargs)


run(1, 2, key='value')

列表推导式

# 一行代码生成1-100之间的奇数
odd_numbers = [i for i in range(100) if 1 == i % 2]

copy 和 deepcopy 的区别

• 浅拷贝copy只是复制对象元素的引用
• 深拷贝deepcopy是复制对象所有元素的值全部复制一遍

不可变对象

import copy
t = ('a', 'b', 'c')
t_copy = copy.copy(t)
t_deepcopy = copy.deepcopy(t)
print(t_copy == t_deepcopy)  # True
print(id(t_copy) == id(t_deepcopy))  # True

不可变对象包含了可变对象

import copy
t = ('a', 'b', 'c', [1, 2, 3])
t_copy = copy.copy(t)
t_deepcopy = copy.deepcopy(t)
print(t_copy == t_deepcopy)  # True
print(id(t_copy) == id(t_deepcopy))  # False

可变对象

import copy
mylist = ['a', 'b', 'c']
mylist_copy = copy.copy(mylist)
mylist_deepcopy = copy.deepcopy(mylist)
print(mylist_copy == mylist_deepcopy)  # True
print(id(mylist_copy) == id(mylist_deepcopy))  # False