几种常见的排序算法,冒泡,插入,选择,快排等

冒泡排序

比较相邻的元素,如果第一个比第二个大,就进行交换,重复上述步骤,直到排序完成。

时间复杂度

  • ​​​​最优:O(n) (遍历一次发现没有任何可以交换的元素,排序结束。)
  • 最坏:O(n²)
  • 稳定性:稳定

    
    def bubble_sort(arr):
    length = len(arr) - 1
    for j in range(length):  # 第一次遍历确定最大的
        count = 0
        for i in range(length - j):  # 外层每循环一次,都会确定一个最大的,要判断的元素都会减少1个。
            if arr[i] > arr[i + 1]:
                arr[i], arr[i + 1] = arr[i + 1], arr[i]  # 交换位置
                count += 1
    
        if count == 0:  # 如果没有位置交换,则表示已经有序
            return arr
    
    return arr
    
    lst = [3,6,1,4,2,8,7,10,9,5]
    print(bubble_sort(lst))  
    

选择排序

选择数组的第一个元素假定为最小元素,然后让这个元素和其他元素做比较,如果遇到比自己小的,则更新最小值的下标,直到把元素遍历完,找到了最小值,并和最开始始设定时的元素交换位置。

时间复杂度

  • 最优: O(n²)
  • 最坏: O(n²)
  • 平均: O(n²)
  • 稳定性: 不稳定( 考虑升序每次选择最大的情况 )

    def select_sort(lst):
    n = len(lst)  # 获取长度
    for j in range(n - 1):  # 循环n-1 
        min = j #第一个元素为最小值
        for i in range(j + 1, n):  # 内层循环从第二个元素开始
            if lst[min] > lst[i]:  # 判断元素是否比自己小,小的话交换下标
                min = i
        lst[j], lst[min] = lst[min], lst[j] # 直到找到最小的那个,交换位置
    return lst
     
    lst = [6,3,1,4,2,8,7,10,9,5]
    print(select_sort(lst))       
    

快速排序

选择一个基准值,把所有比基准值小的放到一个列表,比基准值大的放一个列表,最后将它们合并

时间复杂度

  • 最优: O(nlogn)
  • 最坏: O(n²)
  • 稳定性: 不稳定

    • 最坏情况 每次选择的基准值是当前序列的最小或者最大值
    • 最优情况 最优情况 每次选择的基准值可以将当前序列等分

      def quick_sort(lst):
      if len(lst) < 2:
      return lst
      else:
      pivot = lst[0]
              
      less = [i for i in lst[1:] if i <= pivot]
      
      greater = [i for i in lst[1:] if i > pivot]
      
      return quick_sort(less) + [pivot] + quick_sort(greater)
      
      lst = [3,6,1,4,2,8,7,10,9,5]
      print(quick_sort(lst))
      
      # 指定列表的第一个元素为基准值(pivot = lst[0])
      # 循环列表找出比基准值小的放入less
      # 找出比基准值大的放入greater
      # 递归调用,最后合并
      
      

插入排序

插入排序过程描述
1、从数组的第二个元素开始抽取元素 2、把它与左边第一个元素比较,如果大,则继续与左边第二个比较。直到遇到不比它大的元素,插入到那个元素的右边。 3、继续选取下一个元素,再重复第二个步。 时间复杂度

  • 最优: O(n)
  • 最坏: O(n²)
  • 平均: O(n²)
  • 稳定性: 稳定

    def insert_sort(a_list):
    n = len(a_list)
    for i in range(1, n):               # 未排序序列从第二个元素开始遍历
        for j in range(i, 0, -1):       # 已排序序列从后往前遍历
            if a_list[j] < a_list[j-1]: # 如果当前元素小于前一个元素, 则交换元素位置
                a_list[j], a_list[j-1] = a_list[j-1], a_list[j]
            else:                       # 如果大于前一个元素, 则保持位置不变
                break
    return a_list