在Java中,数组排序是一个重要的算法。在实际开发中,我们经常需要对数组进行排序来满足业务需求。Java中提供了多种排序方式,包括冒泡排序、选择排序、插入排序、快速排序、归并排序等。下面将对这些排序方式进行详细介绍。
一、冒泡排序
冒泡排序是一种简单的排序算法。它重复地遍历数组,比较相邻的元素,如果它们的顺序错误就把它们交换过来。经过一轮遍历之后,最大的元素就会经过交换沉到数组末尾,然后再对剩余元素进行遍历。
public static void bubbleSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
for (int j = 0; j < len - 1 - i; j++) {
if (arr[j] > arr[j + 1]) {
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
冒泡排序的时间复杂度为 O(n^2)。
二、选择排序
选择排序的思想是每次在待排序的元素中选出一个最小的元素,然后再把它放在已排好序的序列的末尾。它的内部循环实现采用的是打擂台的方法,即先假设当前元素是最小的,然后与其它元素进行比较,找到最小的元素后再进行交换。
public static void selectSort(int[] arr) {
int len = arr.length;
for (int i = 0; i < len - 1; i++) {
int min = i;
for (int j = i + 1; j < len; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (i != min) {
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}
}
选择排序的时间复杂度也为 O(n^2)。
三、插入排序
插入排序的思想是依次将每个元素插入到已排好序的序列中。它的内部循环实现采用的是类似于打扑克牌的方法,即每次从未排序的元素中抽取一个,与已排好序的元素依次比较后找到自己的位置插入。
public static void insertSort(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
int curr = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > curr) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = curr;
}
}
插入排序的时间复杂度为 O(n^2)。
四、快速排序
快速排序是一种基于分治思想的排序算法,它实现的基本思路是选取一个基准元素(比如第一个元素),然后将数组划分为两个部分,一部分是所有小于等于基准元素的元素,另一部分是所有大于基准元素的元素。然后对这两个部分分别进行递归调用,直到数组大小为 1 时终止递归。
public static void quickSort(int[] arr, int left, int right) {
int pivot;
if (left < right) {
pivot = partition(arr, left, right);
quickSort(arr, left, pivot - 1);
quickSort(arr, pivot + 1, right);
}
}
public static int partition(int[] arr, int left, int right) {
int pivot = arr[left];
while (left < right) {
while (left < right && arr[right] >= pivot) {
right--;
}
arr[left] = arr[right];
while (left < right && arr[left] <= pivot) {
left++;
}
arr[right] = arr[left];
}
arr[left] = pivot;
return left;
}
快速排序的时间复杂度为 O(nlogn)。
五、归并排序
归并排序是一种基于分治思想的排序算法,它将待排序的序列不断分成两半,直到每个子序列只有一个元素,然后将这些子序列两两合并并排序,直到整个序列完成排序。
public static void mergeSort(int[] arr, int left, int right, int[] temp) {
if (left < right) {
int mid = (left + right) / 2;
mergeSort(arr, left, mid, temp);
mergeSort(arr, mid + 1, right, temp);
merge(arr, left, mid, right, temp);
}
}
public static void merge(int[] arr, int left, int mid, int right, int[] temp) {
int i = left, j = mid + 1, 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++];
}
k = 0;
while (left <= right) {
arr[left++] = temp[k++];
}
}
归并排序的时间复杂度也为 O(nlogn)。