快速排序,java详细示例代码,谢谢,代码用markdown格式,谢谢
时间: 2023-08-31 15:34:03 浏览: 170
快速排序 java代码
### 回答1:
```Java
// Java program for implementation of QuickSort
class QuickSort
{
/* This function takes last element as pivot,
places the pivot element at its correct
position in sorted array, and places all
smaller (smaller than pivot) to left of
pivot and all greater elements to right
of pivot */
int partition(int arr[], int low, int high)
{
int pivot = arr[high];
int i = (low-1); // index of smaller element
for (int j=low; j<high; j++)
{
// If current element is smaller than or
// equal to pivot
if (arr[j] <= pivot)
{
i++;
// swap arr[i] and arr[j]
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// swap arr[i+1] and arr[high] (or pivot)
int temp = arr[i+1];
arr[i+1] = arr[high];
arr[high] = temp;
return i+1;
}
/* The main function that implements QuickSort()
arr[] --> Array to be sorted,
low --> Starting index,
high --> Ending index */
void sort(int arr[], int low, int high)
{
if (low < high)
{
/* pi is partitioning index, arr[pi] is
now at right place */
int pi = partition(arr, low, high);
// Recursively sort elements before
// partition and after partition
sort(arr, low, pi-1);
sort(arr, pi+1, high);
}
}
/* A utility function to print array of size n */
static void printArray(int arr[])
{
int n = arr.length;
for (int i=0; i<n; ++i)
System.out.print(arr[i]+" ");
System.out.println();
}
// Driver program
public static void main(String args[])
{
int arr[] = {10, 7, 8, 9, 1, 5};
int n = arr.length;
QuickSort ob = new QuickSort();
ob.sort(arr, 0, n-1);
System.out.println("sorted array");
printArray(arr);
}
}
```
### 回答2:
快速排序是一种高效的排序算法,Java示例代码如下:
```java
public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int partitionIndex = partition(arr, low, high);
quickSort(arr, low, partitionIndex - 1);
quickSort(arr, partitionIndex + 1, high);
}
}
public 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++;
// 交换元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 将轴值放到正确的位置上
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {10, 7, 8, 9, 1, 5};
int n = arr.length;
quickSort(arr, 0, n - 1);
System.out.println("排序后的数组:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}
```
此代码展示了使用快速排序算法对一个整数数组进行排序。快速排序的核心思想是通过选择一个轴值(一般选择数组的最后一个元素),将数组分为小于轴值和大于轴值的两部分,然后对这两部分进行递归排序。在每次将元素移动到正确的位置上时,使用分区函数进行交换。最后,数组将按照升序排列。
以上代码输出结果为:1 5 7 8 9 10,即排序后的数组。
### 回答3:
以下是快速排序算法的详细示例代码,使用Java编写。在快速排序算法中,我们通过选择一个基准元素,将数组分为两部分,其中一部分的元素小于基准元素,另一部分的元素大于基准元素。然后,对这两部分分别进行递归的快速排序操作。
```java
public class QuickSort {
public static void main(String[] args) {
int[] nums = {5, 2, 9, 1, 3, 6, 8, 7, 4};
quickSort(nums, 0, nums.length-1);
for (int num : nums) {
System.out.print(num + " ");
}
}
public static void quickSort(int[] nums, int low, int high) {
if (low < high) {
int pivotIndex = partition(nums, low, high);
quickSort(nums, low, pivotIndex-1);
quickSort(nums, pivotIndex+1, high);
}
}
public static int partition(int[] nums, int low, int high) {
int pivot = nums[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (nums[j] < pivot) {
i++;
swap(nums, i, j);
}
}
swap(nums, i+1, high);
return i+1;
}
public static void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
```
上述代码首先定义了一个`QuickSort`类,其中包含了`main`方法和三个辅助方法`quickSort`、`partition`和`swap`。
在`main`方法中,我们定义了一个整数数组`nums`,并将其赋初值。然后调用`quickSort`方法对数组进行排序,并通过`for`循环遍历数组,依次输出排序后的元素。
`quickSort`方法用于实现快速排序算法。它接收数组`nums`、排序范围的起始索引`low`和结束索引`high`作为参数。在每一次递归调用中,我们选择数组的最后一个元素作为基准元素,并通过`partition`方法将数组分为两部分。然后,对这两部分分别进行递归的快速排序操作。
`partition`方法用于实现分区操作。它接收数组`nums`、排序范围的起始索引`low`和结束索引`high`作为参数。在分区过程中,我们选择了数组的最后一个元素作为基准元素`pivot`,并用变量`i`来记录小于基准元素的位置。我们通过遍历数组,若当前元素小于基准元素,则将其与`i`所指向的元素进行交换,并递增`i`。最后,将基准元素放置到`i+1`的位置,并返回`i+1`作为分区点的索引。
`swap`方法用于交换数组中两个元素的位置。它接收数组`nums`和两个索引`i`、`j`作为参数,通过一个辅助变量`temp`实现元素的交换。
阅读全文