算法实现及比较 |21xrx.com

算法实现及比较

2023-06-16 10:18:31 深夜i -- --

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

Java作为一门非常常用的编程语言，对于排序算法的实现也有很多种方法。本文将介绍Java中常见的几种排序算法，包括冒泡排序、插入排序、选择排序、快速排序和归并排序，并且对它们的效率进行一定比较。

1.冒泡排序

冒泡排序是最简单的排序算法之一，其实现原理是每次比较相邻两个数的大小，将大的数向右移动，直到没有需要移动的数为止。以下是冒泡排序的Java代码实现：

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

2.插入排序

插入排序也是比较简单的一种排序算法，其实现原理是将未排序的数逐个插入到已排序的数列中。以下是插入排序的Java代码实现：

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

3.选择排序

选择排序的实现原理是每次在未排序的数列中找到最小（or最大）的数，将其放在已排序的数列的末尾。以下是选择排序的Java代码实现：

public void selectSort(int[] arr) {
  int minIndex, 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;
      
    }
    temp = arr[i];
    arr[i] = arr[minIndex];
    arr[minIndex] = temp;
  }
}

4.快速排序

快速排序是比较常用的一种排序算法，其实现原理是采用分治法递归实现。以下是快速排序的Java代码实现：

public 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 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 void swap(int[] arr, int i, int j) {
  int temp = arr[i];
  arr[i] = arr[j];
  arr[j] = temp;
}

5.归并排序

归并排序是采用分治法实现的一种排序算法，其实现原理是将数列分为两个子序列，再对两个子序列进行排序并合并。以下是归并排序的Java代码实现：


public 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 void merge(int[] arr, int left, int mid, int right) {
  int[] temp = new int[right - left + 1];
  int i = left;
  int j = mid + 1;
  int k = 0;
  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 k2 = 0; k2 < temp.length; k2++) {
    arr[left + k2] = temp[k2];
  }
}

通过以上五种排序算法的Java实现，我们可以对它们的效率进行一定比较，也可以更好地了解到它们的工作原理。

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

下一篇: C语言中如何输入坐标

评论区

相似文章