写一段java对数组进行快速排序的代码
时间: 2023-09-18 19:05:53 浏览: 73
### 回答1:
public static void quickSort(int[] arr, int left, int right) {
if (arr == null || left >= right) {
return;
}
int pivot = arr[left];
int i = left, 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);
}
### 回答2:
以下是一段Java代码示例,用于对数组进行快速排序:
```java
public class QuickSort {
public static void quickSort(int[] array, int low, int high) {
if (low < high) {
int pivot = partition(array, low, high);
quickSort(array, low, pivot - 1);
quickSort(array, pivot + 1, high);
}
}
public static int partition(int[] array, int low, int high) {
int pivot = array[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (array[j] < pivot) {
i++;
swap(array, i, j);
}
}
swap(array, i + 1, high);
return i + 1;
}
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
public static void main(String[] args) {
int[] array = {7, 2, 6, 4, 1, 8, 5, 3};
int n = array.length;
System.out.println("原始数组:");
for (int i : array) {
System.out.print(i + " ");
}
quickSort(array, 0, n - 1);
System.out.println("\n排序后的数组:");
for (int i : array) {
System.out.print(i + " ");
}
}
}
```
这段代码实现了快速排序算法。在`quickSort`方法中,我们通过递归调用将数组切分成子数组,并对每个子数组进行排序。`partition`方法用于选择一个基准元素,并将小于该元素的元素放在基准元素的左侧,大于该元素的元素放在基准元素的右侧。最后,我们通过交换元素的位置来完成排序。
在`main`方法中,我们创建了一个测试数组,并依次打印原始数组和排序后的数组。
### 回答3:
快速排序是一种常用的排序算法,其基本思想是通过一趟排序将待排序的序列分割成独立的两部分,其中一部分小于基准元素,另一部分大于基准元素,然后再分别对这两部分继续进行排序,最终得到有序序列。
以下是使用Java实现快速排序的代码:
```java
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivotIndex = partition(arr, left, right);
quickSort(arr, left, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivotValue = arr[left]; // 选取第一个元素作为基准元素
int i = left, j = right;
while (i < j) {
// 从右往左找第一个小于基准元素的值
while (i < j && arr[j] >= pivotValue) {
j--;
}
if (i < j) {
arr[i++] = arr[j];
}
// 从左往右找第一个大于基准元素的值
while (i < j && arr[i] <= pivotValue) {
i++;
}
if (i < j) {
arr[j--] = arr[i];
}
}
arr[i] = pivotValue;
return i;
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 9, 1, 3};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
以上代码中,`quickSort`方法用于递归调用,将数组按照基准元素分成两部分分别进行排序,`partition`方法用于确定基准元素的位置并调整数组顺序。在`main`方法中,我们可以看到对数组进行快速排序的调用,并打印排序后的结果。