java的快速排序怎么写?
时间: 2023-09-19 10:05:56 浏览: 51
### 回答1:
Java的快速排序可以通过以下代码实现:
```java
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int pivot = partition(arr, left, right); // 获取基准点
quickSort(arr, left, pivot - 1); // 对左边的子数组进行快速排序
quickSort(arr, pivot + 1, right); // 对右边的子数组进行快速排序
}
}
private static int partition(int[] arr, int left, int right) {
int pivot = arr[left]; // 选择第一个元素作为基准点
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot; // 将基准点放回数组
return left;
}
```
其中,`quickSort`方法是快速排序的入口,它使用递归方式对数组进行分割和排序。`partition`方法是获取基准点的过程,它使用双指针的方式对数组进行遍历和交换。具体来说,`partition`方法将数组分成两部分,左边部分的所有元素小于等于基准点,右边部分的所有元素大于等于基准点。最后,`partition`方法将基准点放回数组,并返回基准点的下标。
### 回答2:
快速排序是一种高效的排序算法,常用于对数组进行排序。下面是用Java语言实现快速排序的示例代码:
```java
public class QuickSort {
public void quickSort(int[] array, int low, int high) {
if (low < high) {
int pivotIndex = partition(array, low, high);
quickSort(array, low, pivotIndex - 1);
quickSort(array, pivotIndex + 1, high);
}
}
private int partition(int[] array, int low, int high) {
int pivot = array[low];
int i = low + 1;
int j = high;
while (i <= j) {
while (i <= j && array[i] <= pivot) {
i++;
}
while (i <= j && array[j] > pivot) {
j--;
}
if (i < j) {
swap(array, i, j);
}
}
swap(array, low, j);
return j;
}
private void swap(int[] array, int i, int j) {
int temp = array[i];
array[i] = array[j];
array[j] = temp;
}
}
```
在快速排序算法中,首先选择一个基准元素(通常选择数组的第一个元素),然后将数组中比基准元素小的元素移到基准元素的左边,比基准元素大的元素移到基准元素的右边。然后,递归地对左右两边的子数组进行快速排序操作,直到整个数组有序。
以上代码中的`quickSort`方法是快速排序的入口方法,通过递归调用`partition`方法来实现排序。`partition`方法用于划分数组,将小于等于基准元素的元素放在基准元素的左边,大于基准元素的元素放在基准元素的右边,最后返回基准元素的索引。`swap`方法用于交换数组中的两个元素。
使用以上代码,我们只需创建一个QuickSort对象,然后调用`quickSort`方法,即可对一个整数数组进行快速排序。
### 回答3:
快速排序是一种常用的排序算法,它的基本思想是通过将一个数组划分为较小和较大两个子数组,分别对这两个子数组再进行递归排序,并最终合并得到一个有序的数组。下面是Java中快速排序的实现方法:
1. 定义一个方法quickSort,接收一个整数数组arr和两个整数参数low和high,表示要排序的数组范围。
2. 在quickSort方法中,设定两个指针i和j,分别指向数组的起始位置和结束位置。选择数组中的一个元素作为基准值pivot,一般选择数组中的中间元素。
3. 利用循环,反复将左指针i右移,直到找到比基准值大的元素为止;反复将右指针j左移,直到找到比基准值小的元素为止。
4. 如果左指针i仍然小于等于右指针j,交换两个指针所指向的元素。
5. 继续循环,直到左指针i大于右指针j为止。
6. 如果左指针i小于高位指针high,则递归调用quickSort方法,对左子数组进行排序,传入的参数为arr、low和i-1。
7. 如果右指针j大于低位指针low,则递归调用quickSort方法,对右子数组进行排序,传入的参数为arr、j+1和high。
8. 当递归调用完成后,整个数组就会有序。
以下是Java代码实现:
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int i = low;
int j = high;
int pivot = arr[(low + high) / 2]; // 选择中间元素作为基准值
while (i <= j) {
while (arr[i] < pivot) {
i++;
}
while (arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (low < j) {
quickSort(arr, low, j); // 对左子数组进行排序
}
if (high > i) {
quickSort(arr, i, high); // 对右子数组进行排序
}
}
}
public static void main(String[] args) {
int[] arr = {5, 9, 3, 1, 7, 2, 8, 6, 4};
quickSort(arr, 0, arr.length - 1);
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
以上代码会输出排序后的数组:1 2 3 4 5 6 7 8 9
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)