JAVA 实现快速排序算法
时间: 2023-03-15 16:15:11 浏览: 84
Java 中实现快速排序的基本思想是:通过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据都要小,然后再按此方法对这两部分数据分别进行快速排序,整个排序过程可以递归进行,以此达到整个数据变成有序序列。
相关问题
Java实现快速排序算法
快速排序是一种常用的排序算法,其基本思想是将一个待排序的序列分成两个子序列,然后对这两个子序列分别进行排序,以达到整个序列有序的目的。
以下是Java实现快速排序算法的代码:
```
public class QuickSort {
public static void quickSort(int[] arr, int left, int right) {
if (left < right) {
int partitionIndex = partition(arr, left, right);
quickSort(arr, left, partitionIndex - 1);
quickSort(arr, partitionIndex + 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) {
while (i <= j && arr[i] < pivot) {
i++;
}
while (i <= j && arr[j] > pivot) {
j--;
}
if (i <= j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
int temp = arr[left];
arr[left] = arr[j];
arr[j] = temp;
return j;
}
public static void main(String[] args) {
int[] arr = {5, 3, 8, 4, 2};
quickSort(arr, 0, arr.length - 1);
for (int i : arr) {
System.out.print(i + " ");
}
}
}
```
在该代码中,`quickSort`方法用于进行快速排序,其中`left`表示待排序序列的左边界,`right`表示待排序序列的右边界。首先判断左边界是否小于右边界,如果是,则进行分区操作,分别对左分区和右分区进行递归调用。
`partition`方法用于进行分区操作,其中`pivot`表示基准值,即待排序序列的第一个元素。`i`和`j`分别表示左侧指针和右侧指针,初始时`i=left+1`,`j=right`。在while循环中,左侧指针向右移动,直到找到一个大于等于`pivot`的元素,右侧指针向左移动,直到找到一个小于等于`pivot`的元素,然后交换这两个元素的位置。最后将基准值和右侧指针所指的元素交换位置,并返回右侧指针的位置。
在`main`方法中,定义一个待排序的整型数组,然后调用`quickSort`方法进行排序,并输出排序后的结果。
该代码的时间复杂度为O(nlogn),空间复杂度为O(logn)。
用java实现快速排序算法
快速排序是一种常用的排序算法,它的基本思想是通过一趟排序将待排序列分割成独立的两部分,其中一部分的所有元素都比另一部分的所有元素小,然后再按此方法对这两部分分别进行快速排序,整个过程可以递归进行,以此达到整个序列有序的目的。下面是用Java实现快速排序算法的代码:
```
public void quickSort(int[] arr,int left,int right){
if (left < right) {
int k = partition(arr,left,right);
quickSort(arr, left, k - 1);
quickSort(arr, k + 1, right);
}
}
public 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`方法中,我们首先将`pivot`设为待排序列的第一个元素,然后从右往左找到第一个小于`pivot`的元素,将其赋值给`arr[left]`,然后从左往右找到第一个大于`pivot`的元素,将其赋值给`arr[right]`,重复这个过程直到`left`和`right`相遇,最后将`pivot`赋值给`arr[left]`,返回`left`即可。