快速排序是对冒泡排序的一种改进,由 C.A.R.Hoare(Charles Antony Richard Hoare,东尼·霍尔)在 1962 年提出。
快速排序的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据比另一部分的所有数据要小,再按这种方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,使整个数据变成有序序列。
这里我们选择最左边的数作为基准数,在扫描数据的过程中,我们还需要两个哨兵变量来辅助
比如r l
先从r位置开始扫描,直到找到比基准数小的数就停下,然后从l的位置开始找比基准数大的数,找到之后就进行交换,然后继续这个过程,直到r 和 l相遇就算一轮结束
这里我说一下我对于要从r位置开始的原因的理解:因为我们最终的目的是保证基准数的左边都比它小,基准数右边都比他大,最后r和l相遇的位置与基准数的位置进行交换,而我们的基准数就在最左边,因此必须保证相遇的地方小于基准数,但是l出发找的是比基准数大的位置,综上理由就是我个人的看法,如果理解不到位希望大家指出,我及时改正
当我们写完一次的处理方法后,就可以进行递归了:
package zzh0323;
import java.util.*;
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[100];
for(int i = 0;i < arr.length;i++){
arr[i] = (int)(Math.random() * 100000);
}
long beginTime = System.currentTimeMillis();
quickSort(arr,0,arr.length - 1);
long endTime = System.currentTimeMillis();
System.out.println("共花费了" + (endTime - beginTime) / 1000 + "s");
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int left,int right){
if(left > right){
return;
}
int l = left;
int r = right;
int temp = 0;
int pivot = arr[left];
while(l != r){//
while(arr[r] >= pivot && l < r){//在右边找比pivot小的数
r--;
}
while(arr[l] <= pivot && l < r){//在左边找比pivot大的数
l++;
}
temp = arr[l];
arr[l] = arr[r];
arr[r] = temp;
}
//将pivot归位
arr[left] = arr[l];
arr[l] = pivot;
//递归处理下一组
quickSort(arr,left,l - 1);
quickSort(arr,l + 1,right);
return;
}
}
文章评论