java的快速排序怎么写
时间: 2023-08-31 11:24:06 浏览: 47
### 回答1:
快速排序的java实现如下:
public class QuickSort {
public static void sort(int[] array, int low, int high) {
if (array.length == 0)
return;
if (low >= high)
return;
// 找寻基准数据的正确索引
int index = partition(array, low, high);
// 进行迭代对index之前和之后的数组进行相同的操作使整个数组变成有序
sort(array, low, index - 1);
sort(array, index + 1, high);
}
private static int partition(int[] array, int low, int high) {
// 数组的第一个作为基准数据
int tmp = array[low];
while (low < high) {
// 当队尾的元素大于等于基准数据时,向前挪动high指针
while (low < high && array[high] >= tmp) {
high--;
}
// 如果队尾元素小于tmp了,需要将其赋值给low
array[low] = array[high];
// 当队首元素小于等于tmp时,向前挪动low指针
while (low < high && array[low] <= tmp) {
low++;
}
// 当队首元素大于tmp时,需要将其赋值给high
array[high] = array[low];
}
// 跳出循环时low和high相等,此时的low或high就是tmp的正确索引位置
// 由原理部分可以很清楚的知道low位置的值并不是tmp,所以需要将tmp赋值给arr[low]
array[low] = tmp;
return low; // 返回tmp的正确位置
}
}
### 回答2:
Java的快速排序是一种高效的排序算法,其实现主要涉及以下几个步骤:
1. 选择基准值:从待排序数组中选择一个基准值,通常是选取第一个元素作为基准值。
2. 划分数组:将待排序数组划分成两个子数组,小于基准值的元素放在基准值的左边,大于基准值的元素放在基准值的右边。这一步称为分区。
3. 递归调用:对划分后的两个子数组分别进行快速排序,即重复步骤1和步骤2。
4. 合并结果:将排序后的子数组按照顺序合并成一个有序的数组。这一步称为递归结束条件。
快速排序的基本思想是通过不断地将待排序数组划分为两个子数组,直到每个子数组只包含一个元素,然后再依次将子数组合并成一个有序数组。该算法的平均时间复杂度为O(nlogn),其中n为待排序数组的长度。
以下是使用Java代码实现快速排序的示例:
```java
public class QuickSort {
public static void quickSort(int[] array, int start, int end) {
if (start < end) {
int pivot = partition(array, start, end); // 获取基准值的索引
quickSort(array, start, pivot - 1); // 对基准值左边的子数组进行快速排序
quickSort(array, pivot + 1, end); // 对基准值右边的子数组进行快速排序
}
}
private static int partition(int[] array, int start, int end) {
int pivot = array[start]; // 选择第一个元素作为基准值
int left = start + 1; // 左指针
int right = end; // 右指针
while (left <= right) {
while (left <= right && array[left] < pivot) {
left++; // 左指针右移,直到找到一个大于等于基准值的元素
}
while (left <= right && array[right] > pivot) {
right--; // 右指针左移,直到找到一个小于等于基准值的元素
}
if (left <= right) {
swap(array, left, right); // 交换左右指针处的元素
left++;
right--;
}
}
swap(array, start, right); // 将基准值放在正确的位置上
return right;
}
private 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 = {9, 3, 5, 2, 8, 7};
quickSort(array, 0, array.length - 1); // 对数组进行快速排序
for (int num : array) {
System.out.print(num + " ");
}
}
}
```
通过上述示例代码,我们可以实现快速排序算法,并对给定的数组进行排序。最终输出的结果为:2 3 5 7 8 9,表示数组已经按照从小到大的顺序排序完成。
### 回答3:
快速排序是一种常用的排序算法,可以通过递归地将一个数组分成两部分来实现排序。具体步骤如下:
1. 选择一个基准元素(通常选取数组的第一个元素)。
2. 设置两个指针,一个指向数组的开始位置,另一个指向数组的结束位置。
3. 从数组的开始位置和结束位置开始分别向中间遍历,分别找到比基准元素大的元素和比基准元素小的元素。
4. 如果找到了这样的两个元素,则将它们交换位置。
5. 继续执行步骤3和4,直到指针相遇。
6. 将基准元素与指针相遇位置的元素进行交换,使基准元素左边的元素都小于基准元素,右边的元素都大于基准元素。
7. 对基准元素左边的子数组和右边的子数组递归地进行快速排序。
下面是一个使用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[low]; // 选取第一个元素作为基准元素
while (low < high) {
while (low < high && array[high] >= pivot) {
high--;
}
array[low] = array[high]; // 将比基准元素小的元素移动到左边
while (low < high && array[low] <= pivot) {
low++;
}
array[high] = array[low]; // 将比基准元素大的元素移动到右边
}
array[low] = pivot; // 将基准元素放置到最终位置
return low; // 返回基准元素的位置
}
public static void main(String[] args) {
int[] array = {9, 5, 7, 2, 3, 6, 8, 1, 4};
quickSort(array, 0, array.length - 1);
for (int num : array) {
System.out.print(num + " ");
}
}
}
```
以上代码实现了快速排序的逻辑。首先从数组的第一个元素开始,将数组划分为两部分,然后递归地对划分后的子数组进行快速排序,最终得到一个有序数组。运行以上代码的结果为:1 2 3 4 5 6 7 8 9,表示数组已按升序排列。