快速排序是一种高效的排序算法,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键字小,然后分别对这两部分记录继续进行排序,以达到整个序列有序的目的。
下面是一个简单的Java实现:
public class QuickSort { public static void main(String[] args) { int[] arr = {3, 8, 2, 5, 1, 4, 7, 6}; quickSort(arr, 0, arr.length - 1); for (int i : arr) { System.out.print(i + " "); } } public static void quickSort(int[] arr, int low, int high) { if (low < high) { int pivotIndex = partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex + 1, high); } } private static int partition(int[] arr, int low, int high) { int pivot = arr[low]; while (low < high) { while (low < high && arr[high] >= pivot) { high--; } arr[low] = arr[high]; while (low < high && arr[low] <= pivot) { low++; } arr[high] = arr[low]; } arr[low] = pivot; return low; } }
这个程序首先定义了一个quickSort
方法,它接受一个整数数组、一个低索引和一个高索引作为参数。在quickSort
方法中,我们首先检查低索引是否小于高索引,如果是,则我们调用partition
方法对数组进行分区,并返回枢轴元素的索引。然后,我们递归地对枢轴元素左侧和右侧的子数组进行排序。
partition
方法接受一个整数数组、一个低索引和一个高索引作为参数。它首先将低索引处的元素作为枢轴,然后在高索引和低索引之间查找第一个小于枢轴的元素,并将其与枢轴交换。接下来,它在低索引和高索引之间查找第一个大于枢轴的元素,并将其与枢轴交换。这个过程会一直持续到高索引和低索引相遇。最后,将枢轴元素放在正确的位置,并返回其索引。
在main
方法中,我们创建了一个整数数组,并调用quickSort
方法对其进行排序。然后,我们遍历并打印排序后的数组。