Java排序算法的时间复杂度与实现 |21xrx.com

Java排序算法的时间复杂度与实现

2023-06-18 21:05:31 深夜i 13 0

Java 排序算法时间复杂度

Java是一种广泛使用的编程语言，其中的排序算法也很重要。排序算法可以以不同的方式实现，每种实现都有不同的时间复杂度。本文将探讨Java中的一些常见排序算法的时间复杂度和实现方法。

1. 冒泡排序

冒泡排序是最简单的排序算法之一，在Java中也很常见。下面是一个基本的冒泡排序实现：

public static void bubbleSort(int[] arr) {
  int n = arr.length;
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        int temp = arr[j];
        arr[j] = arr[j + 1];
        arr[j + 1] = temp;
      }
    }
  }
}

该代码的时间复杂度为O(n^2)。

2. 插入排序

插入排序是另一个常见的排序算法，也可以在Java中实现。下面是一个基本的插入排序实现：

public static void insertionSort(int[] arr) {
  int n = arr.length;
  for (int i = 1; i < n; ++i) {
    int key = arr[i];
    int j = i - 1;
    while (j >= 0 && arr[j] > key) {
      arr[j + 1] = arr[j];
      j = j - 1;
    }
    arr[j + 1] = key;
  }
}

该代码的时间复杂度为O(n^2)。

3. 快速排序

快速排序是一个更快的排序算法，也可以在Java中实现。下面是一个基本的快速排序实现：

public static void quickSort(int[] arr, int low, int high) {
  if (low < high) {
    int pi = partition(arr, low, high);
    quickSort(arr, low, pi - 1);
    quickSort(arr, pi + 1, high);
  }
}
private 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;
}

该代码的时间复杂度为O(n * log n)。

结论

以上是Java中一些常见的排序算法和它们的实现。在选择排序算法时，需要考虑到时间复杂度和排序数组的大小。

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

下一篇: 《探究Java开发平台工作框架工具》

评论区

相似文章