快速排序の单向扫描法

工程上的排序大多使用复杂度为O（nlgn）即快排的方式。

简介快排即为三部：

1.定主元位置划分（划分为两部分左边都比主元小，右边都大）

2.递归的解决两边的问题。同1

3.合并（快排因为划分的原因不在需要合并）

单向扫描法思路：

1.定主元pivot

2.扫描指针sp，尾指针bigger

3.<=pivot sp右移

  > pivot与bigger当前元素交换,bigger左移

  边界：sp > big 交错 跳出 将主原 与 bigger元素交换 最后返回bigger（主元位置）

（Java代码示例）

static void quickSort(int[] arr, int p, int r) {

if(p < r) {//递归出口

int q = partition(arr, p, r);//定主元位置

quickSort(arr, p, q-1);//左侧递归排序

quickSort(arr, q+1, r);//右侧递归排序

}

}

static int partition(int[] arr, int p, int r) {//单向扫描定主元位置

int pivot = arr[p];//数组的第一个元素为主元大小

int sp = p + 1;//扫描指针

int bigger = r;//右侧指针

while(sp <= bigger) {//两指针交错跳出循环

if(arr[sp] <= pivot) {//<=主元素，扫描指针右移

sp++;

}else{//>主元素，当前元素与右侧指针交换，右侧指针左移

swap(arr, sp, bigger);

bigger--;

}

}

swap(arr, p, bigger);//主元素放到合适的位置（bigger指针）

return bigger;//主元素位置 且数组左边都小于主元素 右边都大于主元素

}

static void swap(int[] arr, int i, int j) {//交换下标为 i j 的元素

int temp = arr[i];

arr[i] = arr[j];

arr[j] = temp;

}