Java快速排序在几种排序方法中是效率较高的
快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
基本思想
1.先从要排序的数列中找定义一个基准数
2.将比基准数大的放在基准数的右边，比基准数小的放在基准数的左边
3.再对左右区间重复第二步，直到各区间只有一个数
因此快速排序就是挖坑填数+分治法
下面以图来解释一下
初始时：left = 0；right = 9；temp = a[i] = 72。
由于将72储存到了temp中，所以相当于a[0]处空出来一个位置，可以将其他的数据填进来
从后向前找，当i=8时，符合条件48<72，所以将48填到a[0]处，left++。下一步从left开始向后找，找基准数大的，当left=3时符合条件，所以a[8] = a[3]，right--。
经变化后数组变为
此时left = 3; right = 7; temp=72。
再重复上面的步骤，先从后向前找，再从前向后找。
下面为实现的代码：
import java.util.Arrays;
import java.util.Scanner;
public class 快速排序 {
public static void main(String[] args) {
int[] arr = new int[6];
Scanner sc = new Scanner(System.in);
for (int i = 0; i < 6; i++) {
arr[i] = sc.nextInt();
}
quicksort(arr,0,5);
System.out.println(Arrays.toString(arr));
System.out.println(arr);
}
private static void quicksort(int[] arr, int left, int right) {
if (left < right) {
int temp = qsort(arr,left,right);
/*
分区，以基准数为中心分为左右两区
qsort方法的返回值是left，即每次排序完成后基准数的位置
*/
quicksort(arr,left,temp-1);
quicksort(arr,temp+1,right);
}
}
/**
* 排序过程
* arr 待排数组
* left 待排数组的最小下标
* right 待排数组的最大下标
*/
private static int qsort(int[] arr, int left, int right) {
int temp = arr[left];
while (right>left){
//让跳出循环时则表示该数小于基准数，所以转到if中
while (left<right&&arr[right]>temp){
right--;
}
if (left<right) {
//把在right处的值给到基准数处，然后left执行加一操作
arr[left++] = arr[right];
}
while(left<right && arr[left]<=temp) {
left++;
}
//跳出上一个循环说明当前的arr[left]的值大于基准数，需要将该值填充到右边空出的位置，然后当前位置空出。
if(left<right) {
arr[right--]=arr[left];
}
}
//将基准数填入最终的位置，这样在基准数左边都比基准数小，右边都比基准数大
arr[left] = temp;
return left;
}
}
网友评论