这里对快速排序做一下总结（之前在写时间复杂度和空间复杂度时候想到的。）
1. 思想
快排的思想就是说，选定数组中第一个数参考值 key ，然后用两个指针，分别从前往后，从后往前，把比 key 大的放在后边，比 key 小的放在前边。两个指针相遇之后，把 key 和 这个停止点的值交换。至此完成一趟排序，到这里，比key大的都在key后面，比key小的都在key前面。
对 key 左边的子组迭代，对key右边的子组迭代，直到子组只含有一个数字为止。
这里用图来给出直观的展示：
快排图示
2. 代码
public class QuickSort {
public void sort(int[] nums,int start,int end) {
// 递归停止条件
if(start>end) return;
int left=start,right=end,key=nums[start];
int temp=0;
while(left<right){
// 这里顺序很重要，要先从右边找。为了避免找过了的情况，还要限制 left<right
while(left<right && nums[right]>=key)
right--;
while (left<right && nums[left]<=key)
left++;
temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
nums[start] = nums[left];
nums[left] = key;
sort(nums,start,left-1); // 这里对子组求一个递归即可
sort(nums,left+1,end);
}
public static void main(String args[]){
int a[] = {6,1,2,7,9,3,4,5,10,8};
QuickSort q = new QuickSort();
q.sort(a,0,a.length-1);
for(int i=0;i<a.length;i++){
System.out.print(a[i]);
}
}
}
3. 关键点
- 是递归的，对子数组
- 递归停止条件是 start>end
- 一趟中，要从右向左找
- 同时为了避免找过了的情况，还要限制 left<right 指针
时间复杂度 nlogn
