当前位置:  首页>> 技术小册>> Java面试指南

快速排序是一种常用的排序算法,它利用分治思想将一个大的数组分成两个子数组来递归地进行排序。下面是一个使用Java实现的快速排序算法的示例代码:

java
Copy code
public class QuickSort {

  1. public static void quickSort(int[] arr, int left, int right) {
  2. if (left >= right) {
  3. return;
  4. }
  5. int pivot = partition(arr, left, right);
  6. quickSort(arr, left, pivot - 1);
  7. quickSort(arr, pivot + 1, right);
  8. }
  9. public static int partition(int[] arr, int left, int right) {
  10. int pivot = arr[left];
  11. while (left < right) {
  12. while (left < right && arr[right] >= pivot) {
  13. right--;
  14. }
  15. arr[left] = arr[right];
  16. while (left < right && arr[left] <= pivot) {
  17. left++;
  18. }
  19. arr[right] = arr[left];
  20. }
  21. arr[left] = pivot;
  22. return left;
  23. }
  24. public static void main(String[] args) {
  25. int[] arr = {5, 2, 9, 3, 7, 6, 8, 1, 4};
  26. quickSort(arr, 0, arr.length - 1);
  27. for (int i : arr) {
  28. System.out.print(i + " ");
  29. }
  30. }

}
在这个示例代码中,我们定义了一个快速排序的静态方法quickSort,它接受一个整数数组arr以及左右两个端点left和right。

我们还定义了一个辅助方法partition来对数组进行划分操作。在quickSort方法中,我们首先进行递归退出条件的判断,即如果左端点大于等于右端点,说明当前子数组已经有序,可以直接返回。

然后我们利用partition方法对数组进行划分操作,并递归地对左右两个子数组进行排序。在partition方法中,我们选择数组的第一个元素作为枢轴元素(pivot),并维护两个指针left和right,分别从左右两端向中间扫描数组。

我们通过不断交换左右两端的元素,将小于枢轴元素的元素放在左边,大于枢轴元素的元素放在右边,最终得到划分后枢轴元素的位置,并返回该位置作为下一次递归的分界点。

运行上述代码,可以得到排序后的数组结果:1 2 3 4 5 6 7 8 9。


该分类下的相关小册推荐: