三、查找与排序（下）

1、分治法（Divide and Conquer）

分解（divide）：将原问题分解成一系列子问题

解决（conquer）：递归地解决各子问题。若子问题足够小，则直接有解

合并（combine）：将子问题的结果合并成原问题的解

优点：容易确定运行时间，提升一定效率（类比想象二分法）

2、快速排序算法

图解一下：

QuickSort(A,p,r)
 if p<r
    q = Partition(A,p,r)
    QuickSort(A,p,q-1)
    QuickSort(A,q+1,r)
//A[q]为大小居中的数
//找一个中间的数，其左边元素小于它，右边元素大于它；划分左边区域进行排序，右边区域进行排序；得出最终结果

3、一遍单向扫描法

图解一下：

QuickSort
  quickSort(A,p,r)
    if(p<r)
      q = partition(A,p,r)
      quickSort(A,p,q-1)
      qucikSort(A,q+1,r)

  partition(A,p,r)
    pivot = A[p]
    sp = p+1 //扫描指针
    bigger = r //右侧指针
    while(sp<=bigger):
      if(A[sp]<=pivot) //扫描元素小于主元
        sp++
      else
        swap(A,sp,bigger) //扫描元素大于主元，二指针的元素交换，右指针左移
        bigger--

    swap(A,p,bigger)
    return bigger 

算法很美（三）

原文：https://www.cnblogs.com/wangzheming35/p/12442148.html