Java代码实现快速排序算法 |21xrx.com

Java代码实现快速排序算法

2024-05-18 22:19:03 深夜i -- --

Java代码快速排序算法实现

快速排序是一种常用的排序算法，其基本思想是将一个数组按照某个参考值（一般称为pivot）进行划分，使得小于pivot的元素都位于它的左边，大于等于pivot的元素都位于它的右边。然后对左右两个子数组分别进行递归地快速排序，直到子数组的长度为1或0时停止。

下面是用Java代码实现快速排序算法的一个简单例子：

public class QuickSort {
  public static void main(String[] args) {
    int[] arr = 2;
    
    quickSort(arr, 0, arr.length - 1);
    
    System.out.println("排序结果：");
    for (int num : arr) {
      System.out.print(num + " ");
    }
  }
  
  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);
    }
  }
  
  public static int partition(int[] arr, int left, int right) {
    int pivot = arr[right];
    int i = left - 1;
    
    for (int j = left; j < right; j++) {
      if (arr[j] < pivot) {
        i++;
        swap(arr, i, j);
      }
    }
    
    swap(arr, i + 1, right);
    
    return i + 1;
  }
  
  public static void swap(int[] arr, int i, int j) {
    int temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
  }
}

上述代码首先定义了一个`QuickSort`类，其中包含了`main`方法作为程序入口。在`main`方法中，我们定义了一个待排序的数组`arr`，然后调用`quickSort`方法对其进行排序，并输出排序结果。

`quickSort`方法是实现快速排序的关键方法，它接收三个参数：待排序数组、左边界和右边界。在方法中，我们首先判断左边界是否小于右边界，若是，则继续进行排序操作。接着定义一个`pivot`作为参考值，选择数组最右端的元素作为`pivot`。然后定义一个`i`变量表示分界点的位置，并初始化为`left - 1`。

接下来，我们使用一个循环来遍历数组，并与`pivot`进行比较。若当前元素小于`pivot`，则将`i`增加1，并将当前元素与`arr[i]`交换位置。这样可以保证小于`pivot`的元素都被放到左边。最后，我们将`arr[i + 1]`（即`pivot`）与数组最右端的元素交换位置，以完成一次划分操作。然后，我们递归地调用`quickSort`方法对划分后的左右子数组进行排序。

最后，我们使用一个`swap`方法来交换数组中两个元素的位置。这个方法在快速排序中用来交换`pivot`和小于`pivot`的元素。

通过以上的Java代码实现，我们可以实现快速排序算法来对一个数组进行排序。这个算法的核心在于利用划分操作将一个数组拆分为左右两个子数组，并递归地对子数组进行排序。这样，最终可以得到一个有序的数组。快速排序是一种高效的排序算法，其时间复杂度为O(nlogn)，是常用的排序算法之一。

上一篇: idea打包java可执行jar包

下一篇: OpenCV双目标定后的视觉匹配研究

评论区

相似文章