Java排序算法介绍与实现 |21xrx.com

Java排序算法介绍与实现

2023-06-15 11:26:24 深夜i -- --

Java排序算法冒泡排序选择排序插入排序快速排序归并排序

在Java中，常见的排序方法包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。本文将简单介绍这些排序算法的原理和Java代码实现。

1. 冒泡排序

冒泡排序是一种比较简单的排序算法，其基本思想是比较相邻的两个元素，如果前一个比后一个大，则交换位置。在一轮循环后，最大的元素就会移到最后，然后再进行下一轮循环。因为每一次循环都会把一个元素放入其最终位置，所以需要进行n-1次循环，才能把n个元素排序完成。

Java代码实现：


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

2. 选择排序

选择排序是一种不稳定的排序算法，其基本思想是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放到序列的起始位置，直到全部待排序的数据元素排完。

Java代码实现：


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

3. 插入排序

插入排序是一种稳定的排序算法，其基本思想是将未排序数据依次插入已排序序列中，插入时从已排序序列末尾比较，找到插入位置。

Java代码实现：


public static void insertSort(int[] arr) {
  int preIndex, current;
  for (int i = 1; i < arr.length; i++) {
    preIndex = i - 1;
    current = arr[i];
    while (preIndex >= 0 && arr[preIndex] > current) {
      arr[preIndex + 1] = arr[preIndex];
      preIndex--;
    }
    arr[preIndex + 1] = current;
  }
}

4. 快速排序

快速排序是一种不稳定的排序算法，其基本思想是选择一个基准元素，将序列分成两部分，一部分比基准元素小，一部分比基准元素大，再递归地对左右两部分进行排序。

Java代码实现：


public static void quickSort(int[] arr, int left, int right) {
  if (left < right) {
    int partitionIndex = partition(arr, left, right);
    quickSort(arr, left, partitionIndex - 1);
    quickSort(arr, partitionIndex + 1, right);
  }
}
private static int partition(int[] arr, int left, int right) {
  int pivot = left;
  int index = pivot + 1;
  for (int i = index; i <= right; i++) {
    if (arr[i] < arr[pivot]) {
      swap(arr, i, index);
      index++;
    }
  }
  swap(arr, pivot, index - 1);
  return index - 1;
}
private static void swap(int[] arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

5. 归并排序

归并排序是一种稳定的排序算法，其基本思想是先将待排序的序列划分成多个子序列，然后对每个子序列进行排序，最后再将排好序的子序列合并成一个完整的序列。

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);
  }
}
private static void merge(int[] arr, int left, int mid, int right) {
  int[] temp = new int[right - left + 1];
  int startIndex = left;
  int secondIndex = mid + 1;
  int index = 0;
  while (startIndex <= mid && secondIndex <= right) {
    if (arr[startIndex] < arr[secondIndex]) {
      temp[index++] = arr[startIndex++];
    } else {
      temp[index++] = arr[secondIndex++];
    }
  }
  while (startIndex <= mid) {
    temp[index++] = arr[startIndex++];
  }
  while (secondIndex <= right) {
    temp[index++] = arr[secondIndex++];
  }
  for (int i = 0; i < temp.length; i++) {
    arr[left + i] = temp[i];
  }
}

本文介绍了Java常见的排序算法及其实现。冒泡排序、选择排序、插入排序均属于比较简单的排序算法，容易理解和实现；快速排序、归并排序则是一些经典的排序算法，属于高级算法，需要掌握其原理和Java代码实现方式。通过学习这些排序算法，可以提高我们的算法和编程能力，加深对Java的理解和应用。

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

下一篇: 如何避免Java栈溢出错误？

评论区

()

相似文章