21xrx.com
2024-11-22 07:06:53 Friday
登录
文章检索 我的文章 写文章
算法实现及比较
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实现,我们可以对它们的效率进行一定比较,也可以更好地了解到它们的工作原理。

  
  

评论区

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