排序算法

重新复习一遍常用的排序算法

1. 冒泡排序

• 顾名思义就是将相邻的两个数比较，不满足大小关系就交换顺序，将最大或最小的数像泡泡一样冒到最右或最左端

2. 选择排序

• 找到一个最大或最小值，然后将其和最右或最左端的数交换

3. 直接插入排序

• 首先取出序列的第一个数，假设它已经排好序，然后从第二个数开始将其插入到第一个数前面或后面
• 然后将序列长度增加
• 现在前面的序列已经排好序了，然后先取出没排好序的第一个值，将其与前面的序列相比较，如果比要插入的值大就把排好序的值依次往后挪一个，以空出一个空位让要插入的值占着。直到找到那个排好序的序列中比要插入的值小或相等的值，则要放置的位置就确定了，然后放入要插入的值，再将排好序的序列的长度增加，开始下一轮循环。
• 简言之就是在已排序的序列中从后往前扫描，找到相应位置并插入

4. 二分插入排序

• 如果在寻找插入值的过程中使用二分查找就是二分查找排序/二分（折半）插入排序这样仅仅只是减小了比较操作的数量，并没有减小挪位操作的数量

5. 快速排序

• 核心思想：

  1. 确定一个 缘分值 的位置 ，使得该值的左边全部比它小，右边全部比它大，但是左右依然可能是无序的。
  2. 对左右两边递归调用快排算法，递归结束条件是需要排序的序列的长度是一，即left >= right

• 主干部分，缘分值的确定

  1. 首先将最左边的值确定为缘分值，然后通过循环从两边向中间靠拢求得缘分值的合适的位置。
  2. 循环的结束条件，左侧值和右侧值为同一值，则找到该 缘分值 的恰当位置，跳出循环。
  3. 循环体
     1. 找到右侧比当前 缘分值 小的值
     2. 将该值换到左侧（当前缘分值移到了右侧），然后将左边界右移一位
     3. 找到左侧比当前缘分值大的值
     4. 将该值换到右侧，则缘分值回到左侧起点的位置，开始下一轮循环

• 细节：

  3. 循环主要就是要找到 缘分值（在最左侧的那个值）的正确位置（下标），保证左侧的比它小，右侧的比它大。
  4. 循环结束之前，该缘分值一直保存在临时变量之中，而在排序的序列中一定是会有一个重复值（要么是i指向的那个值，要么是j指向的那个值）
  5. 在左右两边的变量互换之后应该判断 左右下标是否相等，如果相等则不用移动左右下标（否则会出错）。
  6. 在循环结束之前记得将原来放在临时变量中的值放回到序列之中，从而剔除序列中的重复值

6. 排序