JAVA的快速排序怎么写
时间: 2023-09-12 12:05:07 浏览: 99
### 回答1:
Java的快速排序的代码如下:
public class QuickSort {
public static void quickSort(int[] array, int low, int high) {
if (array.length == 0)
return;
if (low >= high)
return;
int middle = low + (high - low) / 2;
int pivot = array[middle];
int i = low, j = high;
while (i <= j) {
while (array[i] < pivot) {
i++;
}
while (array[j] > pivot) {
j--;
}
if (i <= j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
i++;
j--;
}
}
if (low < j)
quickSort(array, low, j);
if (high > i)
quickSort(array, i, high);
}
}
### 回答2:
快速排序是一种常见的排序算法,通常用递归的方式实现。下面是一个用Java语言实现的快速排序算法代码示例:
```java
public class QuickSort {
public static void main(String[] args) {
int[] arr = new int[]{5, 2, 9, 1, 3, 7};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivot = partition(arr, low, high);
quickSort(arr, low, pivot - 1);
quickSort(arr, pivot + 1, high);
}
}
public static int partition(int[] arr, int low, int high) {
int pivot = arr[low];
while (low < high) {
while (low < high && arr[high] >= pivot) {
high--;
}
arr[low] = arr[high];
while (low < high && arr[low] <= pivot) {
low++;
}
arr[high] = arr[low];
}
arr[low] = pivot;
return low;
}
}
```
快速排序的核心思想是选取一个基准元素(一般选择数组的第一个元素),将数组分为两部分,比基准元素小的放在左边,比基准元素大的放在右边,然后递归地对左右两部分进行排序。在代码中,通过partition函数实现了选取基准元素并进行分区的过程,然后通过递归调用quickSort函数对左右两部分进行排序。最后,通过调用quickSort函数对整个数组进行排序。
以上代码实现了快速排序算法,可以对一个整型数组进行排序,并输出排序结果。
### 回答3:
快速排序是一种常用的排序算法,适用于各种数据类型的排序。
快速排序的基本思想是通过一趟排序将待排序序列分割成独立的两部分,其中一部分的所有元素比另一部分的所有元素小。然后对这两部分分别进行快速排序,以达到整个序列有序的目的。
具体的实现步骤如下:
1. 选择一个基准元素,通常选择待排序序列的第一个元素。
2. 设定两个指针,一个left指向待排序序列的起始位置,一个right指向序列的末尾位置。
3. 从right向left移动,找到第一个小于基准元素的位置,并将其与基准元素交换,然后left指针右移一位。
4. 从left向right移动,找到第一个大于基准元素的位置,并将其与基准元素交换,然后right指针左移一位。
5. 重复步骤3和步骤4,直到left和right指针相遇,此时基准元素的位置就确定了。
6. 根据基准元素的位置,将待排序序列分成两个子序列,分别对这两个子序列进行快速排序。
7. 继续递归上述步骤,直到每个子序列只有一个元素,排序结束。
以下是一个简单的Java代码实现快速排序:
```java
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int index = partition(arr, left, right);
quickSort(arr, left, index - 1);
quickSort(arr, index + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
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;
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方法中对一个数组进行快速排序,并输出排序结果。