21xrx.com
2024-11-22 07:02:01 Friday
登录
文章检索 我的文章 写文章
Java排序算法详解：实现及性能分析
2023-06-15 20:07:07 深夜i     --     --
Java排序 冒泡排序 插入排序 选择排序 归并排序 快速排序 算法实现 性能分

在Java中，排序是最常用的算法之一，可以用于对数组或集合等数据结构进行排列。本文将介绍Java中常见的排序算法，包括冒泡排序、插入排序、选择排序、归并排序、快速排序等，并对这些排序算法的实现和性能进行详细分析。

1.冒泡排序

冒泡排序是一种简单的排序算法，其基本思想是通过不断比较相邻两个元素的大小关系，并进行交换，将最小或最大的元素逐渐“浮”到数组的一端。具体实现过程如下：

  public static void bubbleSort(int[] array) {

    int length = array.length;

    for (int i = 0; i < length - 1; i++) {

      for (int j = 0; j < length - i - 1; j++) {

        if (array[j] > array[j+1]) {

          int temp = array[j];

          array[j] = array[j+1];

          array[j+1] = temp;

        }

      }

    }

  }

2.插入排序

插入排序是一种简单且高效的排序算法，其基本思想是将待排序的元素插入到已排序序列中的适当位置。具体实现过程如下：

  public static void insertSort(int[] array) {

    int length = array.length;

    for (int i = 1; i < length; i++) {

      int value = array[i];

      int j = i - 1;

      while (j >= 0 && array[j] > value) {

        array[j+1] = array[j];

        j--;

      }

      array[j+1] = value;

    }

  }

3.选择排序

选择排序是一种简单但效率较低的排序算法，其基本思想是通过不断选择数组中最小或最大的元素，并交换到相应位置。具体实现过程如下：

  public static void selectSort(int[] array) {

    int length = array.length;

    for (int i = 0; i < length - 1; i++) {

      int minIndex = i;

      for (int j = i + 1; j < length; j++) {

        if (array[j] < array[minIndex])

          minIndex = j;

      }

      if (minIndex != i) {

        int temp = array[i];

        array[i] = array[minIndex];

        array[minIndex] = temp;

      }

    }

  }

4.归并排序

归并排序是一种基于分治思想的高效排序算法，其基本思想是先将待排序序列逐层划分为若干个子序列，再将子序列两两合并，直到最终得到有序序列。具体实现过程如下：

  public static void mergeSort(int[] array) {

    int length = array.length;

    if (length < 2)

      return;

    int mid = length / 2;

    int[] leftArray = Arrays.copyOfRange(array, 0, mid);

    int[] rightArray = Arrays.copyOfRange(array, mid, length);

    mergeSort(leftArray);

    mergeSort(rightArray);

    merge(array, leftArray, rightArray);

  }

  private static void merge(int[] array, int[] leftArray, int[] rightArray) {

    int leftLength = leftArray.length;

    int rightLength = rightArray.length;

    int i = 0, j = 0, k = 0;

    while (i < leftLength && j < rightLength) {

      if (leftArray[i] <= rightArray[j]) {

        array[k++] = leftArray[i++];

      } else {

        array[k++] = rightArray[j++];

      }

    }

    while (i < leftLength) {

      array[k++] = leftArray[i++];

    }

    while (j < rightLength) {

      array[k++] = rightArray[j++];

    }

  }

5.快速排序

快速排序是一种高效的排序算法，其基本思想是通过分治策略将待排序序列逐层划分为若干个子序列，并将子序列分别进行快速排序。具体实现过程如下：

  public static void quickSort(int[] array, int left, int right) {

    if (left >= right)

      return;

    int pivotIndex = partition(array, left, right);

    quickSort(array, left, pivotIndex - 1);

    quickSort(array, pivotIndex + 1, right);

  }

  private static int partition(int[] array, int left, int right) {

    int pivotValue = array[right];

    int i = left - 1;

    for (int j = left; j < right; j++) {

      if (array[j] < pivotValue) {

        i++;

        swap(array, i, j);

      }

    }

    swap(array, i+1, right);

    return i + 1;

  }

  private static void swap(int[] array, int i, int j) {

    int temp = array[i];

    array[i] = array[j];

    array[j] = temp;

  }

通过对以上几种常见排序算法的介绍和实现，可以看出每种算法都有其优缺点，选择合适的排序算法取决于所排序数组的大小和特征。因此，在实际开发过程中，需要根据具体情况进行选择。

  
  

评论区

{{item['qq_nickname']}}
()
回复
回复