QuickSort

快速排序算法流程以网上的一图解千愁

具体实现

package Love;

/**
* Hello world!
*/

public class App {

public static void quickSort(int[] arr, int start, int end) {
int left = start;
int right = end;
int temp = 0;
if (left <= right) {
temp = arr[left];
while (left != right) {
while (left < right && arr[right] >= temp) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= temp) {
left++;
}
arr[right] = arr[left];
}
arr[right] = temp;
quickSort(arr, start, left - 1);
quickSort(arr, right + 1, end);
}
}

public static void main(String[] args) {
int arr[] = {4, 6, 3, 9, 6, 5, 1, 7, 6, 5, 2, 8};
quickSort(arr,0,arr.length - 1);
for(int a : arr){
System.out.print(a + " ");
}

}
}

基准数字可以随意选择,为了方便选择第一个元素 

两侧均有一个指针,一个从右往左,一个从左往右,右侧找到比基准数小的,就移到左边;左边找到比这个基准数大的,就移到右边,最终的目的就是比基准数小的都放在基准数左边,比基准数大的都放在基准数右边

基准数左右两边子数组递归调用上面的过程,任何一个子区间都是左边小于右边,就达到了排序的效果

发表评论