排序算法

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

  1. 冒泡排序
  • 顾名思义就是将相邻的两个数比较,不满足大小关系就交换顺序,将最大或最小的数像泡泡一样冒到最右或最左端
  1. 选择排序
  • 找到一个最大或最小值,然后将其和最右或最左端的数交换
  1. 直接插入排序
  • 首先取出序列的第一个数,假设它已经排好序,然后从第二个数开始将其插入到第一个数前面或后面
  • 然后将序列长度增加
  • 现在前面的序列已经排好序了,然后先取出没排好序的第一个值,将其与前面的序列相比较,如果比要插入的值大就把排好序的值依次往后挪一个,以空出一个空位让要插入的值占着。直到找到那个排好序的序列中比要插入的值小或相等的值,则要放置的位置就确定了,然后放入要插入的值,再将排好序的序列的长度增加,开始下一轮循环。
  • 简言之就是在已排序的序列中从后往前扫描,找到相应位置并插入
  1. 二分插入排序
  • 如果在寻找插入值的过程中使用二分查找就是二分查找排序/二分(折半)插入排序这样仅仅只是减小了比较操作的数量,并没有减小挪位操作的数量
  1. 快速排序
  • 核心思想:

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

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

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