用java写一个快速排序
时间: 2023-09-23 15:06:08 浏览: 66
### 回答1:
以下是使用Java编写的快速排序算法:
```java
public class QuickSort {
public static void main(String[] args) {
int[] array = { 3, 7, 1, 9, 2, 6, 8, 4, 5 };
quickSort(array, 0, array.length - 1);
for (int i = 0; i < array.length; i++) {
System.out.print(array[i] + " ");
}
}
public static void quickSort(int[] array, int left, int right) {
if (left >= right) {
return;
}
int pivot = array[left];
int i = left + 1, j = right;
while (i <= j) {
if (array[i] < pivot) {
i++;
} else if (array[j] > pivot) {
j--;
} else {
swap(array, i++, j--);
}
}
swap(array, left, j);
quickSort(array, left, j - 1);
quickSort(array, j + 1, right);
}
public static void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
```
运行结果:
```
1 2 3 4 5 6 7 8 9
```
这段代码使用了快速排序算法,将整数数组从小到大排序。快速排序具有以下优点:
1. 时间复杂度为 O(nlogn),是一种高效的排序算法。
2. 快速排序是原地排序,不需要额外的存储空间。
3. 可以使用递归实现,代码简单易懂。
快速排序的基本思想是通过一趟排序将数组分成两个部分,其中左边的元素小于一个基准值,右边的元素大于等于基准值。然后再递归地对左右两个子数组进行排序。在这个例子中,选择了最左边的元素作为基准值。
### 回答2:
快速排序是一种经典的排序算法,其中使用分治法思想将待排序的序列不断划分为较小和较大的两个子序列,然后递归地对这两个子序列进行排序,最终实现整个序列的有序排列。
下面是用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); // 对枢纽元素右侧的子序列进行快速排序
}
}
private 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) {
i++;
} else if (arr[j] > pivot) {
j--;
} else {
swap(arr, i, j); // 交换arr[i]和arr[j]
}
}
swap(arr, left, j); // 将枢纽元素放到正确的位置
return j;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = {5, 2, 8, 3, 6, 1, 9, 4, 7};
quickSort(arr, 0, arr.length - 1);
// 输出排序结果
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
以上是一个简单的快速排序算法的实现。在该实现中,通过选择第一个元素作为枢纽元素,不断地进行分区操作,将序列划分为较小和较大的两个子序列,然后再对子序列进行递归排序,最终得到有序的序列。在实际使用中,还可以通过优化枢纽元素的选择策略、使用随机化等方法来提高快速排序的性能。
### 回答3:
快速排序(Quick Sort)是一种常用的排序算法,它采用分治的思想,并通过在待排序序列中选择一个基准值,将序列划分为左右两部分,分别对两部分进行递归排序,最终实现整个序列的有序排列。
以下是用Java编写的快速排序算法:
```java
public class QuickSort {
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[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] < pivot) {
i++;
swap(arr, i, j);
}
}
swap(arr, i + 1, high);
return i + 1;
}
private static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
public static void main(String[] args) {
int[] arr = { 5, 2, 8, 9, 1, 3, 7 };
System.out.println("原始数组:");
printArray(arr);
quickSort(arr, 0, arr.length - 1);
System.out.println("排序后的数组:");
printArray(arr);
}
private static void printArray(int[] arr) {
for (int element : arr) {
System.out.print(element + " ");
}
System.out.println();
}
}
```
以上代码通过递归调用quickSort方法实现快速排序。在partition方法中,选择最后一个元素作为基准值(pivot),然后用i标记小于基准值的元素的位置,遍历数组,将小于基准值的元素与标记位置i进行交换,最后将基准值放入正确的位置。然后再对划分后的左右两个子序列递归地进行快速排序,直到序列有序为止。
运行以上代码,将输出原始数组和排序后的数组。原始数组为{5, 2, 8, 9, 1, 3, 7},排序后的数组为{1, 2, 3, 5, 7, 8, 9}。