快速排序是一种常用的排序算法,它的时间复杂度为O(nlogn),效率比较高。下面是Java实现快速排序算法的步骤:
- 选择一个基准数(pivot),将待排序数组分为两个子数组,一边放比基准数小的数,另一边放比基准数大的数。
- 对这两个子数组分别进行递归排序,重复步骤1,直到所有子数组的大小都为1。
- 将所有子数组合并,得到排序后的数组。
代码一:
public void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[left];
int i = left;
int j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
arr[i] = arr[j];
while (i < j && arr[i] <= pivot) {
i++;
}
arr[j] = arr[i];
}
arr[i] = pivot;
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
代码二:
public void quickSort(int[] arr, int left, int right) {
if (left >= right) {
return;
}
int pivot = arr[left];
int i = left;
int j = right;
while (i < j) {
while (i < j && arr[j] >= pivot) {
j--;
}
while (i < j && arr[i] <= pivot) {
i++;
}
swap(arr,i,j);
}
swap(arr,left,i);
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
Q.E.D.
