工程上的排序大多使用复杂度为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;
}
网友评论