用shell教你搞定各种排序算法-快速排序

排序算法中,没有一种算法在任意一种情况下都是最好的。我们总是能构造出一种最坏的情况。快速排序并不总是最快的。

快速排序是由东尼·霍尔提出的一种高效的排序算法，简称快排。它的算法思想并不复杂，可以用3个步骤6个字来概括：选基、分割、递归。

扩充成一句话就是：首先挑选基准值；然后分割数组，把小于基准值的元素放到基准值前面，大于基准值的元素放到基准值后面；最后递归地对小于基准值的子序列和大于基准值的子序列进行排序。主要使用了所谓的分治的思想

快速排序的写法有很多中,可以优化的点也有很多。但终归逃过不过一个分一个治，也就是递归。

光第一步选基就有很多方法和优化的空间
第一种方式,我们每次选待排数组的最左边一个元素为主
第二种方式,我们随机选待排数组的一个元素为主
第三种方式,我们组左,中,右三个数的中位数为主。或者5个数中的中位数
如果我们每次选的元素总是能将数组刚好左右分割，使得所选元素左边都比该元素小，右边的元素都比该元素大，那么我们的算法就是最优的。

下面我没来挑战一下这个看似简单实则超级难理解的算法。

main(){                                   #我们还是先来定义一个main方法
  array=(1 3 5 7 9 2 4 6 8 10 1 2 8 5 31) #我们再来定义一个待排数组,注意这里是个全局的变量
  quick_sort                              #我们调用我们即将书写的快速排序
  echo "${array[*]}"                      #打印数组,看看是不是按照从小到的的顺序排序了呢
}

function quick_sort(){
  #注意array是全局变量,我们可以在这里访问到它

  #快排一定有一个递归调用,这个递归调用一般需要左右两个数组下标

  function sort(){
    local left=$1;local right=$2
    local i=${left};local j=${right} #这里为什么要重新让j=right,i=left呢,我们直接用 left,right不行么?答案是不行,因为要记住数组进来的时候,处理的左右边界是什么。

    #1. 首先这个方法是一个递归，递归三要素之一就是要有退出条件
    if [[ ${left} -ge ${right} ]];then return; fi

    #2. 选主元
    local base=${array[left]} #每次都已最左边的为基

    while [[ ${i} -ne ${j} ]]; do
      #3. 分隔
      #3.1 从右边j想左找第一个比base小的元素的数组的下标,如果右边的元素一直比base大，就一直找，直到 j=i 了未知
      while [[ ${array[j]} -ge ${base} ]] && [[ ${j} -gt ${i}  ]];do #注意等号
        ((j--))
      done

      while [[ ${array[i]} -le ${base} ]] && [[ ${j} -gt ${i}  ]];do
        ((i++))
      done

      if [[ ${i} -lt ${j} ]];then
         local tmp=${array[j]}
         array[j]=${array[i]}
         array[i]=${tmp}
      fi
    done

    array[left]=${array[i]}
    array[i]=${base}

    sort "${left}" "$((i-1))"
    sort "$((i+1))" "${right}"
  }
  sort
}


main