数据结构学习 | 排序

选择排序

• 概述：给定一组需要排序的数，第一次遍历寻找数中的max/min并记录，第二遍遍历寻找剩下数中的max/min再记录……以此循环
• 时间复杂度O(n^2)[详见代码]
• 代码解释

def findsmallest(arr):
    smallest=arr[0]
    smallest_index=0  ###重要
    for i in range(len(arr)):
        if arr[i]<smallest:
            smallest=arr[i]
            smallest_index=i
            
    return smallest_index
        


def selectionsort(arr):
    new=[]
    for i in range(len(arr)):
        smallest=findsmallest(arr)
        new.append(arr.pop(smallest)) #pop内传递的是index
    return new

快速排序

• 概述：递归思想，每次选出一组数中的某一个数为pivot(中心点)，遍历这组数找出比pivot小的数放一组less，另一组greater是比pivot大的数；再将less和greater进行上述操作（递归）
• 时间复杂度

1. 平均：O(nlogn)
2. 最坏：O(n^2)
   待排序的序列为正序或者逆序，选出的pivot刚好是序列的max/min
3. 最好：O(nlogn)
   选出的pivot正好是待排序的序列的中间值

• 代码

def quicksort(arr):
    if len(arr)<2:
        return arr
    else:
        pivot=arr[0]
        less=[i for i in arr[1:] if i<=pivot]
        greater=[i for i in arr[1:] if i>pivot]
    return quicksort(less)+[pivot]+quicksort(greater)

冒泡排序

• 概述：给定一个需要排序的序列，比较相邻的两个元素，较小的放前，较大的放后。（第一趟比较完成后最大的数在序列的最后面）
• 时间复杂度：O(n^2)
• 代码

def bubble_sort(nums):
    for i in range(len(nums)-1):  # 这个循环负责设置冒泡排序进行的次数,最后一次不需要
        for j in range(len(nums) - i - 1):  # j为列表下标
            if nums[j] > nums[j + 1]:
                nums[j], nums[j + 1] = nums[j + 1], nums[j]
    return nums