内部排序算法总结(时间原因待完善)

冒泡

• 原理：当气泡从水底浮上来的时候，由于压强变小气泡就会越来越大。最终在水面是其最大的时候。

  冒泡排序算法每次从左到右比较，并判断是否需要交换位置(将大的放在右边)。在一次遍历后最大的数将会在最右边。之后对最大的数之外的数重复该操作。直到所有数都排列好。

• 模版要点：

  1. 工作一般用不上，面试可能会用到
  2. for 第j个气泡 in range(0,气泡长度-第i次排序-1): 这里的-1是因为下面的判断会判断j+1，所以这里需要-1

  def 冒泡排序(气泡列表):
    for 第i次排序 in range(0,气泡列表长度): #表示重复该操作第i次
        for 第j个气泡 in range(0,气泡长度-第i次排序-1): #表示一次具体的遍历换位
            if 气泡列表[第j个气泡] > 气泡列表[第j+1个气泡] :
                    气泡列表[第j个气泡] (交换) 气泡列表[第j+1个气泡]
  

---

选择

• 原理：想象一下，如果你把一堆不一样长度的筷子给一个小孩子让他排好，他会怎样做？ 大概会把最小的找出来放到一边，然后再找最小的放到后面，就这样一直找下去。

  选择排序就是按照这种依据：通过一次遍历找到最小的值，将最小的值和第一个数据交换位置。然后重复该步骤。

• 模版要点：

  1. 最小筷子的下标 = 第i次找：是因为每次找的时候第一眼看到的会觉得最小的，之后再刷新这个认识
  2. in range(第i次找 + 1, 一堆筷子的个数): 是因为每次找的时候，前i个已经是找出来了的
  3. if 第i次找 != 最小筷子的下标: 表示实际上最小的不是最开始看到的那第一个

  def 选择排序(一堆筷子):
      for 第i次找 in range(一堆筷子的个数 - 1):
          最小筷子的下标 = 第i次找
          for 比较的第j根筷子 in range(第i次找 + 1, 一堆筷子的个数):
              if 一堆筷子[比较的第j根筷子] < 一堆筷子[最小筷子的下标]:
                  最小筷子的下标 = 比较的第j根筷子
          if 第i次找 != 最小筷子的下标:
              一堆筷子[第i次找]（交换）一堆筷子[最小筷子的下标]
  

---

插入

• 原理：相当于一副扑克牌，将牌一张一张的放到左手。右手的牌插入到左手的时候，从左到右比较牌的大小，将牌插入到正确位置，使得左手的牌始终有序。
• 模版要点：
  1. 数组传入的是引用，直接赋值某个下标的改变，对所有时刻都生效
  2. if里面不能break：因为之后要不停的交换位置，才能做到后面的所有数字后移一位

  def 插入排序(桌上的牌):
      for 桌上第i张牌 in range(1,len(桌上的牌)):
          for 左手第j张牌 in range(0,桌上第i张牌):
              if 桌上的牌[左手第j张牌]>桌上的牌[桌上第i张牌]:
                  桌上的牌[左手第j张牌](交换位置)arr[桌上第i张牌]
  

---

快排

• 原理：每次取列表中的一个数，将其他数与其比较。小于的放到左边列表、大于的放到右边列表，最后将取出的树放到中间。不停的对左边列表和右边列表做同样的操作。最终得到有序。
  要点：

• 模版要点：

  1. pass

  递归法模版套路：数据量太大可能导致栈溢出

  while循环法模版套路：

---

希尔排序

---

指针排序

这是一个特殊场景的排序:将一个有序数组插入到另一个有序数组中。

• 原理：这里使用相当于上面插入排序的。把被插入的数组当作左手的牌，插入的数组当作桌上的牌。

• 模版要点：

  1. 具体算法做了一个优化：将被插入的牌的容量扩大,每次从最右边插入

  def 特殊插入排序之指针排序(左手的有序牌,左手牌的长度,桌上的倒序牌,桌上的倒序牌的长度):
    手上最后一张牌的位置 = 左手牌的长度 - 1
      手上最右边的位置 = 桌上的倒序牌的长度 + 左手牌的长度 - 1
    for 桌上的第i张倒序牌 in range(桌上的倒序牌的长度-1):
          if 桌上的倒序牌[桌上的第i张倒序牌]>=左手的有序牌[手上最后一张牌的位置]:
              左手的有序牌[手上最右边的位置]=桌上的倒序牌[桌上的第i张倒序牌]
          else:
            左手的有序牌[手上最右边的位置]=左手的有序牌[手上最后一张牌的位置]
            做插入排序：插入排序初始状态{{{
                左手牌=左手的有序牌[0-手上最后一张牌的位置-1]的范围
                插入牌=桌上的倒序牌[桌上的第i张倒序牌]
            }}}
       手上最右边的位置--
  };
  

---

归并

---

堆排序

---

线程阻塞