java 实现排序的几种方式

羊蹓狼 · 2024-12-24 11:38:25

冒泡排序(Bubble Sort)

基本原理：

它重复地走访要排序的数列，一次比力两个元素，如果它们的次序错误就把它们互换过来。走访数列的工作是重复地进行直到没有再必要互换，也就是说该数列已经排序完成。

示例代码如下：

登录后复制

public class BubbleSort {
public static void bubbleSort(int[] arr) {
int n = arr.length;
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] > arr[j + 1]) {
// 交换元素
int temp = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = temp;
}
}
}
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
System.out.println("Before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
bubbleSort(arr);
System.out.println("After sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}

复制代码

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.

时间复杂度：

最好情况(数组已经有序)：时间复杂度为，因为只必要进行一次遍历比力，没有互换操纵。
最坏情况(数组完全逆序)：时间复杂度为，因为每次遍历都要进行互换操纵，统共必要进行大约次比力。
平均情况：时间复杂度为。

空间复杂度：

空间复杂度为，因为只必要有限的额外空间来进行元素互换。

选择排序(Selection Sort)

基本原理：

首先在未排序序列中找到最小(大)元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小(大)元素，然后放到已排序序列的末了。以此类推，直到全部元素均排序完毕。

示例代码如下：

登录后复制

public class SelectionSort {
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;
}
}
// 交换元素
if (minIndex!= i) {
int temp = arr[i];
arr[i] = arr[minIndex];
arr[minIndex] = temp;
}
}
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
System.out.println("Before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
selectionSort(arr);
System.out.println("After sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}

复制代码

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.

时间复杂度：

最好情况、最坏情况宁静均情况的时间复杂度都是。因为无论数组初始状态怎样，都必要进行次比力操纵来确定元素的位置。

空间复杂度：

空间复杂度为，因为它只必要有限的额外空间来互换元素。

插入排序(Insertion Sort)

基本原理：

它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。插入排序在实现上，通常接纳 in - place 排序(即只需用到的额外空间的排序)，因而在从后向前扫描过程中，必要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。

示例代码如下：

登录后复制

public class InsertionSort {
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 = j - 1;
}
arr[j + 1] = key;
}
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
System.out.println("Before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
insertionSort(arr);
System.out.println("After sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}

复制代码

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.

时间复杂度：

最好情况(数组已经有序)：时间复杂度为，因为只必要进行次比力操纵，没有移动元素的操纵。
最坏情况(数组完全逆序)：时间复杂度为，因为每次插入一个元素都必要移动大量元素。
平均情况：时间复杂度为。

空间复杂度：

空间复杂度为，因为插入排序是一种原地排序算法，只必要有限的额外空间来进行元素的移动和插入。

快速排序(Quick Sort)

基本原理：

它接纳了分治法(Divide - and - Conquer)的策略。从数列中挑出一个元素，称为 “基准”(pivot)，重新排序数列，全部元素比基准小的摆放在基准前面，全部元素比基准大的摆放在基准背面(雷同的数可以到任一边)。在这个分区退出之后，该基准就处于数列的中间位置。这个过程称为分区(partition)操纵。递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。

示例代码如下：

登录后复制

public class QuickSort {
public static void quickSort(int[] arr, int low, int high) {
if (low < high) {
int pivotIndex = partition(arr, low, high);
quickSort(arr, low, pivotIndex - 1);
quickSort(arr, pivotIndex + 1, high);
}
}
private static int partition(int[] arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for (int j = low; j < high; j++) {
if (arr[j] <= pivot) {
i++;
// 交换元素
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
// 交换元素
int temp = arr[i + 1];
arr[i + 1] = arr[high];
arr[high] = temp;
return i + 1;
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
System.out.println("Before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
quickSort(arr, 0, arr.length - 1);
System.out.println("After sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}

复制代码

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.

时间复杂度：

最好情况：时间复杂度为，当每次分别都能将数组分为两个大小相近的子数组时，递归树的深度为，每层的时间复杂度为。
最坏情况：时间复杂度为，比方数组已经有序，每次分别只能得到一个比上一次分别少一个元素的子数组。
平均情况：时间复杂度为。

空间复杂度：

最好情况：空间复杂度为，因为递归栈的深度为。
最坏情况：空间复杂度为，比方数组已经有序，递归栈必要存储个元素。
平均情况：空间复杂度为。

归并排序(Merge Sort)

基本原理：

它是创建在归并操纵上的一种有效的排序算法。该算法是接纳分治法(Divide - and - Conquer)的一个非常典型的应用。将已有序的子序列归并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表归并成一个有序表，称为二路归并。

示例代码如下：

登录后复制

public class MergeSort {
public static void mergeSort(int[] arr) {
if (arr.length > 1) {
int mid = arr.length / 2;
int[] left = new int[mid];
int[] right;
if (arr.length % 2 == 0) {
right = new int[mid];
} else {
right = new int[mid + 1];
}
for (int i = 0; i < mid; i++) {
left[i] = arr[i];
}
for (int i = mid; i < arr.length; i++) {
right[i - mid] = arr[i];
}
mergeSort(left);
mergeSort(right);
merge(arr, left, right);
}
}
private static void merge(int[] result, int[] left, int[] right) {
int i = 0, j = 0, k = 0;
while (i < left.length && j < right.length) {
if (left[i] < right[j]) {
result[k] = left[i];
i++;
} else {
result[k] = right[j];
j++;
}
k++;
}
while (i < left.length) {
result[k] = left[i];
i++;
k++;
}
while (j < right.length) {
result[k] = right[j];
j++;
k++;
}
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
System.out.println("Before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
mergeSort(arr);
System.out.println("After sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}

复制代码

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.

时间复杂度：

最好情况、最坏情况宁静均情况的时间复杂度都是。因为归并排序每次分别都将数组分为两个子数组，统共必要分别层，每层归并操纵的时间复杂度为。

空间复杂度：

空间复杂度为，因为在归并过程中必要创建额外的数组来存储左右子数组。

堆排序(Heap Sort)

基本原理：

堆排序是使用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满意堆积的性子：即子结点的键值或索引总是小于(或者大于)它的父节点。将数组构建成最大堆(对于升序排序)，然后每次将堆顶元素(最大值)与堆的最后一个元素互换，再对剩下的堆进行调解，使其重新满意最大堆的性子，重复这个过程直到整个数组排序完成。

示例代码如下：

登录后复制

public class HeapSort {
public static void heapSort(int[] arr) {
int n = arr.length;
// 构建最大堆
for (int i = n / 2 - 1; i >= 0; i--) {
heapify(arr, n, i);
}
for (int i = n - 1; i > 0; i--) {
// 交换堆顶元素和最后一个元素
int temp = arr[0];
arr[0] = arr[i];
arr[i] = temp;
// 调整堆
heapify(arr, i, 0);
}
}
private static void heapify(int[] arr, int n, int i) {
int largest = i;
int l = 2 * i + 1;
int r = 2 * i + 2;
if (l < n && arr[l] > arr[largest]) {
largest = l;
}
if (r < n && arr[r] > arr[largest]) {
largest = r;
}
if (largest!= i) {
int temp = arr[i];
arr[i] = arr[largest];
arr[largest] = temp;
heapify(arr, n, largest);
}
}
public static void main(String[] args) {
int[] arr = {5, 4, 3, 2, 1};
System.out.println("Before sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
System.out.println();
heapSort(arr);
System.out.println("After sorting:");
for (int num : arr) {
System.out.print(num + " ");
}
}
}

复制代码

1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.

时间复杂度：

最好情况、最坏情况宁静均情况的时间复杂度都是。构建堆的时间复杂度为，每次调解堆的时间复杂度为，统共必要进行次调解。

空间复杂度：

空间复杂度为，因为堆排序是一种原地排序算法，只必要有限的额外空间来互换元素。

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。

		自动登录	找回密码
密码			立即注册

java 实现排序的几种方式

0 个回复

快速回复

楼主热帖

标签云