基本思想
- 先从数列中取出一个数作为基准数。
- 分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 再对左右区间重复第二步，直到各区间只有一个数。
实现原理
- 选择最左侧元素为基准数pivot，并记录
- 设置两个变量l和r分别指向头尾元素
- 从后向前搜索，直至找到比pivot小的数字，记录当时r值，并将该元素替换到pivot
- 从前向后搜索，直至找到比pivot大的数字，记录当前l值，并将该原子替换到下标为r的位置
- 当l==r时，将pivot赋值到此位置
代码实现
public class Quick_Sort {
public static void quick_sort(int[] array,int left,int right){
if (array==null||array.length<=0){
return;
}
if (left<right){
int l = left;
int r = right;
int pivot = array[left];
while (l<r){
while(l<r && array[r]>=pivot){
r--;
}
if (l<r){
array[l++]=array[r];
}
while (l<r && array[l]<pivot){
l++;
}
if (l<r) {
array[r--] = array[l];
}
}
array[l] = pivot;
quick_sort(array, left, l-1);
quick_sort(array, l+1, right);
}
}
public static void main(String[] args) {
int[] array = {3,44,38,5,47,15,36,26,27,2,46,4,19,50,48};
quick_sort(array,0,array.length-1);
System.out.println(Arrays.toString(array));
}
}
