Java排序算法及实现

排序算法是编程中常用到的算法之一,Java中提供了多种排序算法的实现,本文将介绍Java常用的排序算法及其实现。

一、Bubble Sort(冒泡排序)

冒泡排序是最简单的排序算法之一,其核心思想是不断比较相邻的两个数大小,如果顺序错误则交换位置,该算法的时间复杂度为O(n^2)。

Java代码实现如下:

public static void bubbleSort(int[] arr) {

int temp = 0;

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;

}

}

}

}

二、Insertion Sort(插入排序)

插入排序是将未排序的元素插入到已排序的元素中,其核心思想是将一个元素插入到当前有序序列中适当的位置,该算法的时间复杂度也为O(n^2),但是在数据量小的情况下表现良好。

Java代码实现如下:

public static void insertionSort(int[] arr) {

int n = arr.length;

for (int i = 1; i < n; i ) {

int key = arr[i];

int j = i 1;

while (j >= 0 && arr[j] > key) {

arr[j 1] = arr[j];

j;

}

arr[j 1] = key;

}

}

三、Selection Sort(选择排序)

选择排序是每次找到未排序序列中最小的元素,将其放到已排序序列的末尾,该算法的时间复杂度也为O(n^2)。

Java代码实现如下:

public static void selectionSort(int[] arr) {

int n = arr.length;

for (int i = 0; i < n 1; i ) {

int minIndex = i;

for (int j = i 1; j < n; j ) {

if (arr[j] < arr[minIndex]) {

minIndex = j;

}

}

int temp = arr[minIndex];

arr[minIndex] = arr[i];

arr[i] = temp;

}

}

四、Merge Sort(归并排序)

归并排序是将一个大序列分成两个小序列,递归地对其进行排序,最后将两个已排序的小序列合并成一个大的已排序序列,该算法的时间复杂度为O(nlogn)。

Java代码实现如下:

public static int[] mergeSort(int[] arr) {

int n = arr.length;

if (n < 2) {

return arr;

}

int mid = n / 2;

int[] left = Arrays.copyOfRange(arr, 0, mid);

int[] right = Arrays.copyOfRange(arr, mid, n);

return merge(mergeSort(left), mergeSort(right));

}

public static int[] merge(int[] left, int[] right) {

int[] result = new int[left.length right.length];

for (int index = 0, i = 0, j = 0; index < result.length; index ) {

if (i >= left.length) {

result[index] = right[j ];

} else if (j >= right.length) {

result[index] = left[i ];

} else if (left[i] > right[j]) {

result[index] = right[j ];

} else {

result[index] = left[i ];

}

}

return result;

}

以上是Java中常用的四种排序算法及其实现方法,开发人员可以根据具体需求选择合适的算法。在使用排序算法的过程中,需要注意数据规模和算法时间复杂度的关系,以及特定场景下有没有更优的算法可用。

免责声明:本网站部分内容由用户自行上传,若侵犯了您的权益,请联系我们处理,谢谢!联系QQ:2760375052 沪ICP备2023024866号-10

分享:

扫一扫在手机阅读、分享本文

评论