2020.5.29日 算法排序

发布于 2020-05-29  30 次阅读


1.复习内容

2.灵感代办

3.学习内容

  • python排序的稳定性
  • python算法排序
    • 冒泡排序

4.扩展延伸知识

  • python的排序算法

    • python 推导循环的值

      • 顺序:先从循环内层推,然后依次向外推
      • 外层循环的变量,是根据内层循环的需要,而推出来的
      • 内层循环的变量,是根据实际要比较的次数推出来的
      • 排序中一般都是数值比较,只用一个循环中的值 ( j和j+1比较 )
    • 冒泡排序

      • 本质:一个个查找,有就交换
      • length的长度是需要减一才可以遍历,因为下标从0开始
      • 外层循环:如果有n个元素,需要比较n-1次
      • 内层循环:循环到最后的值,肯定是最大,所以需要比较n-i-1次
      • 优化冒泡排序:当没有交换,就可以退出循环
    • 选择排序

      • 本质:假设一个值是最小值,然后在数组查找是否有比元素小的,有则交换下标
      • 有一个min,用来记录最小值下标(认为是最小值)
      • 循环比较数组中元素是否有比min下标代表的值小,如果有,交换下标
      • 在将最小值下标min和循环中的元素交换,实现换位
      • 第一层循环是比较次数(0到length-1)
      • 第二层循环是比较环节(i+1到length)到length是因为要拿来做比较
    • 插入排序

      • 第一步,拿到第一个值,当做已排序值
    • 第二步,拿到第二个值(第一个值后面),在已排序中做比较,放入合适的位置
      • 第三步,循环上个操作,直到最后一个元素
    • 快速排序

      • 第一步,找到数组第一个元素作为基准值,
      • 第二步,递归操作需要终止值,
      • 第三步,函数递归传递的值
      • 第四步,从数组最后开始和基准值比较,如果小于基准,则和数组左边替换
      • 第五步,从数组最头开始和进准直比较,如果大于基准,则和数组右边替换
      • 第六步,将左边和右边的值都递运算
        • 代码
          •     def quick(self, left, right):
                            # 为了递归,left和right不满足立即退出
                    if left >= right:
                    return
                middle_num = self.__lists[left]
                low = left
                    high = right
            
                    while low < high:
                        while low < high and self.__lists[high] >= middle_num:
                            high -= 1
                        self.__lists[low], self.__lists[high] = self.__lists[high], self.__lists[low]
                        while low < high and self.__lists[low] <= middle_num:
                            low += 1
                        self.__lists[high], self.__lists[low] = self.__lists[low], self.__lists[high]
                    # middle_num = self.__lists[low]
                    self.quick(left, low - 1)
                    self.quick(low + 1, right)

5.知识内容个人梳理

6.今天都复习了之前的什么内容


Ares个人进阶之路