快速排序
快速排序原理
快速排序(Quick Sort)是一种基于分治思想的排序算法,通过选择一个基准值,将数组分为两个子数组,一个子数组中的元素都比基准值小,另一个子数组中的元素都比基准值大,然后递归地对子数组进行排序,最终得到一个有序数组。
public class QuickSortDemo {
int[] numArrays = {4,3,6,2,9,1,7,3,2,9,6,10};
/**
*
* 快速排序的入门方法
* @param arr 需要排序的数组
* @param left 左边界
* @param right 右边界
*/
public static void quickSort(int[] arr, int left, int right) {
//如果左边界小于右边界
if (left < right) {
// 获取枢轴元素的下标
int pivotIndex = partition(arr, left, right);
// 对枢轴元素左边的子数组进行快速排序
quickSort(arr, left, pivotIndex - 1);
// 对枢轴元素右边的子数组进行快速排序
quickSort(arr, pivotIndex + 1, right);
}
}
/**
* 选取基准元素,并将数组划分为两个部分
* @param arr 需要排序的数组
* @param left 左边界
* @param right 右边界
* @return 返回基准元素的下标
*/
private static int partition(int[] arr, int left, int right) {
//选择最左侧的元素作为枢轴元素
int pivot = arr[right];
//指向左边界的前一个元素
int i = left - 1;
//遍历left,right区间的内的元素
for (int j = left; j < right; j++) {
//如果当前元素小于枢轴元素
if (arr[j] < pivot) {
//i向右移动一位
i++;
//元素调换arr[i]与arr[j]的位置
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//交换arr[i + 1]与arr[right]的位置
int temp = arr[i + 1];
arr[i + 1] = arr[right];
arr[right] = temp;
return i + 1;
}
@Test
public void test(){
this.quickSort(numArrays,0,numArrays.length-1);
System.out.println(Arrays.toString(numArrays));
}
}