快速排序是一种常用的排序算法,它利用分治思想将一个大的数组分成两个子数组来递归地进行排序。下面是一个使用Java实现的快速排序算法的示例代码:
java
Copy code
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
public static void main(String[] args) {
int[] arr = {5, 2, 9, 3, 7, 6, 8, 1, 4};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
在这个示例代码中,我们定义了一个快速排序的静态方法quickSort,它接受一个整数数组arr以及左右两个端点left和right。
我们还定义了一个辅助方法partition来对数组进行划分操作。在quickSort方法中,我们首先进行递归退出条件的判断,即如果左端点大于等于右端点,说明当前子数组已经有序,可以直接返回。
然后我们利用partition方法对数组进行划分操作,并递归地对左右两个子数组进行排序。在partition方法中,我们选择数组的第一个元素作为枢轴元素(pivot),并维护两个指针left和right,分别从左右两端向中间扫描数组。
我们通过不断交换左右两端的元素,将小于枢轴元素的元素放在左边,大于枢轴元素的元素放在右边,最终得到划分后枢轴元素的位置,并返回该位置作为下一次递归的分界点。
运行上述代码,可以得到排序后的数组结果:1 2 3 4 5 6 7 8 9。