Java 中有许多种排序算法,其中较为常见的是快速排序和冒泡排序。本文将会详细介绍这两种排序算法的原理与实现方法。
快速排序
快速排序是一种基于分治法的排序算法,它的基本思想是通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字都比另一部分记录的关键字小,然后分别对这两部分记录继续进行排序,以达成整个序列有序。
public static void quickSort(int arr[], int left, int right) {
int i = left, j = right;
int temp;
int pivot = arr[(left + right) / 2];
while (i <= j) {
while (arr[i] < pivot)
i++;
while (arr[j] > pivot)
j--;
if (i <= j) {
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
i++;
j--;
}
}
if (left < j)
quickSort(arr, left, j);
if (i < right)
quickSort(arr, i, right);
}
上面是一个快速排序的函数实现,它使用了递归来实现分治的操作。函数接受三个参数,分别代表待排序数组、待排序序列的起始下标和终止下标。算法的时间复杂度为 O(nlogn)。
冒泡排序
冒泡排序是一种基本的排序算法,它通过按照顺序遍历数组并多次比较相邻两个元素的值来对数组进行排序,每次遍历过程中,会将当前最大的元素沉到数组底部,然后继续进行下一轮遍历。
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;
}
}
}
}
上面是一个冒泡排序的函数实现。函数接受一个待排序数组作为参数。算法的时间复杂度为 O(n²)。