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

Java快速排序算法实现

2023-10-27 02:06:35 深夜i -- --

Java 快速排序算法实现

快速排序是一种常用的排序算法，它的实现思路非常巧妙和高效。快速排序的核心思想是将一个数组分成两个子数组，然后对这两个子数组分别进行排序，最终使整个数组有序。

具体实现快速排序算法的关键步骤如下：

1. 选择一个基准元素，可以选择数组的第一个元素作为基准。

2. 设定两个指针（i 和 j），分别指向数组的第一个元素和最后一个元素。同时，还需要设置一个枢轴元素用来比较。

3. 将指针 i 从左向右移动，直到找到一个大于枢轴元素的元素。

4. 将指针 j 从右向左移动，直到找到一个小于枢轴元素的元素。

5. 如果 i 小于 j，则交换这两个元素的位置。

6. 重复步骤 3 和步骤 4，直到 i 大于等于 j。

7. 交换基准元素和指针 j 所指的元素的位置。

8. 分别对基准元素左侧的子数组和右侧的子数组进行递归调用上述步骤。

这样，通过不断地将数组划分成子数组，再对子数组进行排序，最终可以实现整个数组的排序。

下面是使用 Java 语言实现快速排序算法的示例代码：


public class QuickSort {
  public static void quickSort(int[] arr, int low, int high) {
    if (low < high) {
      int pivot = partition(arr, low, high);
      quickSort(arr, low, pivot - 1);
      quickSort(arr, pivot + 1, high);
    }
  }
  public static int partition(int[] arr, int low, int high) {
    int pivot = arr[low];
    int i = low + 1;
    int j = high;
    while (true) {
      while (i <= j && arr[i] <= pivot) {
        i++;
      }
      while (i <= j && arr[j] >= pivot)
        j--;
      
      if (i > j)
        break;
      
      int temp = arr[i];
      arr[i] = arr[j];
      arr[j] = temp;
    }
    arr[low] = arr[j];
    arr[j] = pivot;
    return j;
  }
  public static void main(String[] args) {
    int[] arr = 9;
    int n = arr.length;
    quickSort(arr, 0, n - 1);
    System.out.println("排序后的数组：");
    for (int i = 0; i < n; i++) {
      System.out.print(arr[i] + " ");
    }
  }
}

以上是一个简单的快速排序算法的实现。这个算法具有较高的效率和较高的可读性，因此在实际应用中被广泛使用。对于大规模的数据集，快速排序算法相对其他排序算法来说有着更好的性能。

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

下一篇: 您的系统上未找到ffmpeg

评论区

()

相似文章