Java中的排序算法是程序员们在日常开发中经常使用的一个重要部分。对于不同的排序算法，其时间复杂度也不相同，因此，本文将介绍Java中常见的排序算法的时间复杂度，并介绍排序算法的具体实现。这样，大家就可以根据自己的需求选择合适的排序算法。

1. 插入排序

插入排序的时间复杂度为O(n^2)，其主要思路是将待排序的数插入到已排序序列中的合适位置。下面是插入排序的Java代码实现：

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

2. 归并排序

归并排序的时间复杂度为O(n log n)，其主要思路是将待排序序列分成若干个子序列，对每个子序列进行排序，然后再将排好序的子序列合并起来。下面是归并排序的Java代码实现：

public static void mergeSort(int[] arr, int left, int right) {
  if (left < right) {
    int mid = (left + right) / 2;
    mergeSort(arr, left, mid);
    mergeSort(arr, mid + 1, right);
    merge(arr, left, mid, right);
  }
}
public static void merge(int[] arr, int left, int mid, int right) {
  int[] temp = new int[arr.length];
  int i = left;
  int j = mid + 1;
  int k = left;
  while (i <= mid && j <= right) {
    if (arr[i] <= arr[j]) {
      temp[k++] = arr[i++];
    } else {
      temp[k++] = arr[j++];
    }
  }
  while (i <= mid) {
    temp[k++] = arr[i++];
  }
  while (j <= right) {
    temp[k++] = arr[j++];
  }
  for (int l = left; l <= right; l++) {
    arr[l] = temp[l];
  }
}

3. 快速排序

快速排序的时间复杂度为O(n log n)，其主要思路是选取一个基准元素，将待排序序列分成两部分，在其中一部分中寻找比基准元素小的数，在另一部分中寻找比基准元素大的数，然后将找到的两个数进行交换。下面是快速排序的Java代码实现：

public static void quickSort(int[] arr, int left, int right) {
  if (left < right) {
    int p = partition(arr, left, right);
    quickSort(arr, left, p - 1);
    quickSort(arr, p + 1, right);
  }
}
public static int partition(int[] arr, int left, int right) {
  int pivot = arr[left];
  int i = left + 1;
  int j = right;
  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;
  }
  int temp = arr[left];
  arr[left] = arr[j];
  arr[j] = temp;
  return j;
}

相似文章
• Java排序算法总结及代码案例
  Java排序算法总结及代码案例
  
  

友情链接
• 网站定制开发
• 帮你发
• 小蓄群站获客
• 雅圣洁家政