javav写一个快速排序程序
时间: 2023-08-31 10:29:12 浏览: 49
### 回答1:
这里是一个快速排序程序的例子:
public class QuickSort {
public static void main(String[] args) {
int[] array = {9, 2, 4, 7, 3, 7, 10};
System.out.println("排序前:");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
quickSort(array, 0, array.length - 1);
System.out.println("\n排序后:");
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
public static void quickSort(int[] array, int low, int high) {
if (array.length == 0)
return;
if (low >= high)
return;
int left = low;
int right = high;
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;
quickSort(array, low, left - 1);
quickSort(array, left + 1, high);
}
}
### 回答2:
快速排序是常用的排序算法之一,它的主要思想是选取一个基准元素,通过将其他元素与基准元素进行比较,将小于基准元素的放在其左边,大于基准元素的放在其右边,从而实现对数组的快速排序。以下是一个使用Java语言编写的快速排序程序:
```java
import java.util.Arrays;
public class QuickSort {
public static void main(String[] args) {
int[] arr = {5, 3, 8, 6, 2, 7, 1, 4};
System.out.println("排序前的数组:" + Arrays.toString(arr));
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:" + Arrays.toString(arr));
}
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 pivot = arr[left];
int i = left + 1;
int j = right;
while (i <= j) {
if (arr[i] > pivot && arr[j] < pivot) {
swap(arr, i, j);
}
if (arr[i] <= pivot) {
i++;
}
if (arr[j] >= pivot) {
j--;
}
}
swap(arr, left, j);
return j;
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
```
以上是一个简单的快速排序程序,首先定义一个`quickSort`方法,用于排序整个数组。在`quickSort`方法中,通过`partition`方法选取基准元素,并将小于基准元素的放在其左边,大于基准元素的放在其右边。然后再对基准元素左边和右边的子数组进行递归调用`quickSort`方法。
`partition`方法中,选取数组第一个元素作为基准元素,并通过`i`和`j`两个指针进行扫描和交换,直到`i`和`j`相遇。最后将基准元素放到正确的位置上,并返回该位置索引。
最后,打印排序前和排序后的数组,结果如下:
排序前的数组:[5, 3, 8, 6, 2, 7, 1, 4]
排序后的数组:[1, 2, 3, 4, 5, 6, 7, 8]
### 回答3:
快速排序是一种常用的排序算法,它的基本思想是通过分治的方式将一个待排序的数组划分为较小的子数组,再对这些子数组进行排序,最终将整个数组排序完成。
以下是用Java编写的快速排序程序:
```java
public class QuickSort {
public static void main(String[] args) {
int[] array = {5, 2, 8, 3, 1, 6, 9, 4, 7};
quickSort(array, 0, array.length - 1);
for (int num : array) {
System.out.print(num + " ");
}
}
public static void quickSort(int[] array, int left, int right) {
if (left < right) {
int partitionIndex = partition(array, left, right);
quickSort(array, left, partitionIndex - 1);
quickSort(array, partitionIndex + 1, right);
}
}
public static int partition(int[] array, int left, int right) {
int pivot = array[right];
int i = left - 1;
for (int j = left; j < right; j++) {
if (array[j] < pivot) {
i++;
swap(array, i, j);
}
}
swap(array, i + 1, right);
return i + 1;
}
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
```
该程序首先定义了一个`QuickSort`类,并在其`main`方法中创建了一个待排序的数组`array`。然后调用`quickSort`方法对数组进行快速排序,并使用循环输出排序后的结果。
`quickSort`方法是递归实现快速排序的关键。在该方法中,我们首先判断待排序数组的左边界`left`是否小于右边界`right`,如果是,则调用`partition`方法对数组进行分区,并进行递归调用`quickSort`方法对分区后的子数组进行排序。
`partition`方法则是快速排序的核心所在。它选择一个基准元素`pivot`,并将小于基准元素的数放在数组的左边,大于基准元素的数放在数组的右边。最后返回基准元素所在的位置。
`swap`方法用于交换数组中两个元素的位置。
以上就是一个使用Java编写的快速排序程序,可以对任意数组进行快速排序。