快速排序算法 java
时间: 2023-03-13 08:51:09 浏览: 118
快速排序算法 Java 的基本思路是:选择一个基准元素,通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小;然后,再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
相关问题
快速排序算法java
快速排序是一种采用分治法解决问题的典型应用,也是冒泡排序的一种改进。它的基本思想是通过一轮排序将待排记录分割成独立的两部分,其中一部分均比另一部分小,则可分别对这两部分继续进行排序,已达到整个序列有序。下面是一个使用Java实现的快速排序算法:
```java
public static int partition(int[] array, int left, int right) {
int pivot = array[left];
while (left < right) {
while (left < right && array[right] >= pivot) {
right--;
}
array[left] = array[right];
while (left < right && array[left] <= pivot) {
left++;
}
array[right] = array[left];
}
array[left] = pivot;
return left;
}
public static void quickSort(int[] array) {
quick(array, 0, array.length - 1);
}
public static void quick(int[] array, int start, int end) {
if (start >= end) {
return;
}
int pivot = partition(array, start, end);
quick(array, start, pivot - 1);
quick(array, pivot + 1, end);
}
```
这是一种基于Hoare划分方式的快速排序算法。它首先选择一个枢轴元素,然后将数组分割为两个部分,一部分包含所有小于枢轴元素的值,另一部分包含所有大于枢轴元素的值。然后,递归地对这两部分进行排序,最终得到正确的排序结果。
快速排序算法 java代码
以下是一个快速排序算法的Java代码实现:
```
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2, 7, 1, 10, 6, 9};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
public static void quickSort(int[] arr, int start, int end) {
if (start < end) {
int pivotIndex = partition(arr, start, end);
quickSort(arr, start, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, end);
}
}
public static int partition(int[] arr, int start, int end) {
int pivot = arr[end];
int i = start - 1;
for (int j = start; j < end; j++) {
if (arr[j] < pivot) {
i++;
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
int temp = arr[i + 1];
arr[i + 1] = arr[end];
arr[end] = temp;
return i + 1;
}
}
```
该代码使用递归实现快速排序算法,其中 `quickSort` 方法用于递归排序子数组,而 `partition` 方法则用于将数组分成两部分并返回枢轴元素的索引。在 `partition` 方法中,使用 `i` 记录小于枢轴元素的最后一个元素的索引,并将小于枢轴元素的元素与 `i` 交换位置。最后,将枢轴元素放到它的正确位置,并返回该位置的索引。