ToB企服应用市场:ToB评测及商务社交产业平台

标题: java 实现排序的几种方式 [打印本页]

---

作者: 羊蹓狼    时间: 2024-12-24 11:38
标题: java 实现排序的几种方式

• 冒泡排序(Bubble Sort)
  

     

• 基本原理：
  

     

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

     

• 示例代码如下：
  

                                   登录后复制                        

1. public class BubbleSort {
2.     public static void bubbleSort(int[] arr) {
3.         int n = arr.length;
4.         for (int i = 0; i < n - 1; i++) {
5.             for (int j = 0; j < n - i - 1; j++) {
6.                 if (arr[j] > arr[j + 1]) {
7.                     // 交换元素
8.                     int temp = arr[j];
9.                     arr[j] = arr[j + 1];
10.                     arr[j + 1] = temp;
11.                 }
12.             }
13.         }
14.     }
15.     public static void main(String[] args) {
16.         int[] arr = {5, 4, 3, 2, 1};
17.         System.out.println("Before sorting:");
18.         for (int num : arr) {
19.             System.out.print(num + " ");
20.         }
21.         System.out.println();
22.         bubbleSort(arr);
23.         System.out.println("After sorting:");
24.         for (int num : arr) {
25.             System.out.print(num + " ");
26.         }
27.     }
28. }

复制代码

      

• 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)
  

     

• 基本原理：
  

     

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

     

• 示例代码如下：
  

                                   登录后复制                        

1. public class SelectionSort {
2.     public static void selectionSort(int[] arr) {
3.         int n = arr.length;
4.         for (int i = 0; i < n - 1; i++) {
5.             int minIndex = i;
6.             for (int j = i + 1; j < n; j++) {
7.                 if (arr[j] < arr[minIndex]) {
8.                     minIndex = j;
9.                 }
10.             }
11.             // 交换元素
12.             if (minIndex!= i) {
13.                 int temp = arr[i];
14.                 arr[i] = arr[minIndex];
15.                 arr[minIndex] = temp;
16.             }
17.         }
18.     }
19.     public static void main(String[] args) {
20.         int[] arr = {5, 4, 3, 2, 1};
21.         System.out.println("Before sorting:");
22.         for (int num : arr) {
23.             System.out.print(num + " ");
24.         }
25.         System.out.println();
26.         selectionSort(arr);
27.         System.out.println("After sorting:");
28.         for (int num : arr) {
29.             System.out.print(num + " ");
30.         }
31.     }
32. }

复制代码

      

• 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 排序(即只需用到的额外空间的排序)，因而在从后向前扫描过程中，必要反复把已排序元素逐步向后挪位，为最新元素提供插入空间。
  

     

• 示例代码如下：
  

                                   登录后复制                        

1. public class InsertionSort {
2.     public static void insertionSort(int[] arr) {
3.         int n = arr.length;
4.         for (int i = 1; i < n; i++) {
5.             int key = arr[i];
6.             int j = i - 1;
7.             while (j >= 0 && arr[j] > key) {
8.                 arr[j + 1] = arr[j];
9.                 j = j - 1;
10.             }
11.             arr[j + 1] = key;
12.         }
13.     }
14.     public static void main(String[] args) {
15.         int[] arr = {5, 4, 3, 2, 1};
16.         System.out.println("Before sorting:");
17.         for (int num : arr) {
18.             System.out.print(num + " ");
19.         }
20.         System.out.println();
21.         insertionSort(arr);
22.         System.out.println("After sorting:");
23.         for (int num : arr) {
24.             System.out.print(num + " ");
25.         }
26.     }
27. }

复制代码

      

• 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)操纵。递归地把小于基准值元素的子数列和大于基准值元素的子数列排序。
  

     

• 示例代码如下：
  

                                   登录后复制                        

1. public class QuickSort {
2.     public static void quickSort(int[] arr, int low, int high) {
3.         if (low < high) {
4.             int pivotIndex = partition(arr, low, high);
5.             quickSort(arr, low, pivotIndex - 1);
6.             quickSort(arr, pivotIndex + 1, high);
7.         }
8.     }
9.     private static int partition(int[] arr, int low, int high) {
10.         int pivot = arr[high];
11.         int i = low - 1;
12.         for (int j = low; j < high; j++) {
13.             if (arr[j] <= pivot) {
14.                 i++;
15.                 // 交换元素
16.                 int temp = arr[i];
17.                 arr[i] = arr[j];
18.                 arr[j] = temp;
19.             }
20.         }
21.         // 交换元素
22.         int temp = arr[i + 1];
23.         arr[i + 1] = arr[high];
24.         arr[high] = temp;
25.         return i + 1;
26.     }
27.     public static void main(String[] args) {
28.         int[] arr = {5, 4, 3, 2, 1};
29.         System.out.println("Before sorting:");
30.         for (int num : arr) {
31.             System.out.print(num + " ");
32.         }
33.         System.out.println();
34.         quickSort(arr, 0, arr.length - 1);
35.         System.out.println("After sorting:");
36.         for (int num : arr) {
37.             System.out.print(num + " ");
38.         }
39.     }
40. }

复制代码

      

• 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)的一个非常典型的应用。将已有序的子序列归并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表归并成一个有序表，称为二路归并。
  

     

• 示例代码如下：
  

                                   登录后复制                        

1. public class MergeSort {
2.     public static void mergeSort(int[] arr) {
3.         if (arr.length > 1) {
4.             int mid = arr.length / 2;
5.             int[] left = new int[mid];
6.             int[] right;
7.             if (arr.length % 2 == 0) {
8.                 right = new int[mid];
9.             } else {
10.                 right = new int[mid + 1];
11.             }
12.             for (int i = 0; i < mid; i++) {
13.                 left[i] = arr[i];
14.             }
15.             for (int i = mid; i < arr.length; i++) {
16.                 right[i - mid] = arr[i];
17.             }
18.             mergeSort(left);
19.             mergeSort(right);
20.             merge(arr, left, right);
21.         }
22.     }
23.     private static void merge(int[] result, int[] left, int[] right) {
24.         int i = 0, j = 0, k = 0;
25.         while (i < left.length && j < right.length) {
26.             if (left[i] < right[j]) {
27.                 result[k] = left[i];
28.                 i++;
29.             } else {
30.                 result[k] = right[j];
31.                 j++;
32.             }
33.             k++;
34.         }
35.         while (i < left.length) {
36.             result[k] = left[i];
37.             i++;
38.             k++;
39.         }
40.         while (j < right.length) {
41.             result[k] = right[j];
42.             j++;
43.             k++;
44.         }
45.     }
46.     public static void main(String[] args) {
47.         int[] arr = {5, 4, 3, 2, 1};
48.         System.out.println("Before sorting:");
49.         for (int num : arr) {
50.             System.out.print(num + " ");
51.         }
52.         System.out.println();
53.         mergeSort(arr);
54.         System.out.println("After sorting:");
55.         for (int num : arr) {
56.             System.out.print(num + " ");
57.         }
58.     }
59. }

复制代码

      

• 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)
  

     

• 基本原理：
  

     

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

     

• 示例代码如下：
  

                                   登录后复制                        

1. public class HeapSort {
2.     public static void heapSort(int[] arr) {
3.         int n = arr.length;
4.         // 构建最大堆
5.         for (int i = n / 2 - 1; i >= 0; i--) {
6.             heapify(arr, n, i);
7.         }
8.         for (int i = n - 1; i > 0; i--) {
9.             // 交换堆顶元素和最后一个元素
10.             int temp = arr[0];
11.             arr[0] = arr[i];
12.             arr[i] = temp;
13.             // 调整堆
14.             heapify(arr, i, 0);
15.         }
16.     }
17.     private static void heapify(int[] arr, int n, int i) {
18.         int largest = i;
19.         int l = 2 * i + 1;
20.         int r = 2 * i + 2;
21.         if (l < n && arr[l] > arr[largest]) {
22.             largest = l;
23.         }
24.         if (r < n && arr[r] > arr[largest]) {
25.             largest = r;
26.         }
27.         if (largest!= i) {
28.             int temp = arr[i];
29.             arr[i] = arr[largest];
30.             arr[largest] = temp;
31.             heapify(arr, n, largest);
32.         }
33.     }
34.     public static void main(String[] args) {
35.         int[] arr = {5, 4, 3, 2, 1};
36.         System.out.println("Before sorting:");
37.         for (int num : arr) {
38.             System.out.print(num + " ");
39.         }
40.         System.out.println();
41.         heapSort(arr);
42.         System.out.println("After sorting:");
43.         for (int num : arr) {
44.             System.out.print(num + " ");
45.         }
46.     }
47. }

复制代码

      

• 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企服之家，中国第一个企服评测及商务社交产业平台。

---

欢迎光临 ToB企服应用市场:ToB评测及商务社交产业平台 (https://dis.qidao123.com/)

Powered by Discuz! X3.4