数据结构之八大排序算法详解

排序算法是计算机科学中一类重要的算法，用于将数据按照特定的顺序举行排列。以下是对八大排序算法的详细解说，包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序和计数排序。

一、冒泡排序（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.                     // 交换 arr[j] 和 arr[j+1]
8.                     int temp = arr[j];
9.                     arr[j] = arr[j + 1];
10.                     arr[j + 1] = temp;
11.                 }
12.             }
13.         }
14.     }
16.     public static void main(String[] args) {
17.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
18.         bubbleSort(arr);
19.         System.out.println("Sorted array: " + Arrays.toString(arr));
20.     }
21. }

复制代码

时间复杂度

• 均匀时间复杂度：O(n²)
  
• 最优时间复杂度：O(n)（当数组已经排序时）
  
• 最差时间复杂度：O(n²)
  

二、选择排序（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.             // 交换 arr[i] 和 arr[minIndex]
12.             int temp = arr[i];
13.             arr[i] = arr[minIndex];
14.             arr[minIndex] = temp;
15.         }
16.     }
18.     public static void main(String[] args) {
19.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
20.         selectionSort(arr);
21.         System.out.println("Sorted array: " + Arrays.toString(arr));
22.     }
23. }

复制代码

时间复杂度

• 均匀时间复杂度：O(n²)
  
• 最优时间复杂度：O(n²)
  
• 最差时间复杂度：O(n²)
  

三、插入排序（Insertion Sort）

原理

插入排序将数组分为已排序和未排序两个部分，每次从未排序部分取出一个元素，插入到已排序部分的正确位置。
代码实现

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.     }
15.     public static void main(String[] args) {
16.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
17.         insertionSort(arr);
18.         System.out.println("Sorted array: " + Arrays.toString(arr));
19.     }
20. }

复制代码

时间复杂度

• 均匀时间复杂度：O(n²)
  
• 最优时间复杂度：O(n)（当数组已经排序时）
  
• 最差时间复杂度：O(n²)
  

四、希尔排序（Shell Sort）

原理

希尔排序是一种改进的插入排序，通过将数组分成多个子数组，对每个子数组举行插入排序，然后渐渐缩小子数组的间隔。
代码实现

1. public class ShellSort {
2.     public static void shellSort(int[] arr) {
3.         int n = arr.length;
4.         for (int gap = n / 2; gap > 0; gap /= 2) {
5.             for (int i = gap; i < n; i += 1) {
6.                 int temp = arr[i];
7.                 int j;
8.                 for (j = i; j >= gap && arr[j - gap] > temp; j -= gap) {
9.                     arr[j] = arr[j - gap];
10.                 }
11.                 arr[j] = temp;
12.             }
13.         }
14.     }
16.     public static void main(String[] args) {
17.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
18.         shellSort(arr);
19.         System.out.println("Sorted array: " + Arrays.toString(arr));
20.     }
21. }

复制代码

时间复杂度

• 均匀时间复杂度：O(n^(3/2))
  
• 最优时间复杂度：O(n)
  
• 最差时间复杂度：O(n²)
  

五、归并排序（Merge Sort）

原理

归并排序是一种分治算法，将数组分为两部分，分别排序，然后将排序后的两部分归并。
代码实现

1. public class MergeSort {
2.     public static void mergeSort(int[] arr) {
3.         if (arr == null || arr.length <= 1) {
4.             return;
5.         }
6.         mergeSort(arr, 0, arr.length - 1);
7.     }
9.     private static void mergeSort(int[] arr, int left, int right) {
10.         if (left < right) {
11.             int mid = (left + right) / 2;
12.             mergeSort(arr, left, mid);
13.             mergeSort(arr, mid + 1, right);
14.             merge(arr, left, mid, right);
15.         }
16.     }
18.     private static void merge(int[] arr, int left, int mid, int right) {
19.         int[] temp = new int[right - left + 1];
20.         int i = left, j = mid + 1, k = 0;
21.         while (i <= mid && j <= right) {
22.             if (arr[i] <= arr[j]) {
23.                 temp[k++] = arr[i++];
24.             } else {
25.                 temp[k++] = arr[j++];
26.             }
27.         }
28.         while (i <= mid) {
29.             temp[k++] = arr[i++];
30.         }
31.         while (j <= right) {
32.             temp[k++] = arr[j++];
33.         }
34.         System.arraycopy(temp, 0, arr, left, temp.length);
35.     }
37.     public static void main(String[] args) {
38.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
39.         mergeSort(arr);
40.         System.out.println("Sorted array: " + Arrays.toString(arr));
41.     }
42. }

复制代码

时间复杂度

• 均匀时间复杂度：O(n log n)
  
• 最优时间复杂度：O(n log n)
  
• 最差时间复杂度：O(n log n)
  

六、快速排序（Quick Sort）

原理

快速排序也是一种分治算法，通过选择一个基准元素，将数组分为小于基准和大于基准的两部分，然后递归地对两部分举行排序。
代码实现

1. public class QuickSort {
2.     public static void quickSort(int[] arr) {
3.         if (arr == null || arr.length <= 1) {
4.             return;
5.         }
6.         quickSort(arr, 0, arr.length - 1);
7.     }
9.     private static void quickSort(int[] arr, int left, int right) {
10.         if (left >= right) {
11.             return;
12.         }
13.         int pivotIndex = partition(arr, left, right);
14.         quickSort(arr, left, pivotIndex - 1);
15.         quickSort(arr, pivotIndex + 1, right);
16.     }
18.     private static int partition(int[] arr, int left, int right) {
19.         int pivot = arr[right];
20.         int i = left - 1;
21.         for (int j = left; j < right; j++) {
22.             if (arr[j] <= pivot) {
23.                 i++;
24.                 swap(arr, i, j);
25.             }
26.         }
27.         swap(arr, i + 1, right);
28.         return i + 1;
29.     }
31.     private static void swap(int[] arr, int i, int j) {
32.         int temp = arr[i];
33.         arr[i] = arr[j];
34.         arr[j] = temp;
35.     }
37.     public static void main(String[] args) {
38.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
39.         quickSort(arr);
40.         System.out.println("Sorted array: " + Arrays.toString(arr));
41.     }
42. }

复制代码

时间复杂度

• 均匀时间复杂度：O(n log n)
  
• 最优时间复杂度：O(n log n)
  
• 最差时间复杂度：O(n²)
  

七、堆排序（Heap Sort）

原理

堆排序是一种基于堆数据结构的排序算法。首先将数组构建成一个最大堆，然后通过交换堆顶元素与数组末尾元素，并重新调整堆，以实现排序。
代码实现

1. public class HeapSort {
2.     public static void heapSort(int[] arr) {
3.         int n = arr.length;
5.         // 构建最大堆
6.         for (int i = n / 2 - 1; i >= 0; i--) {
7.             heapify(arr, n, i);
8.         }
10.         // 提取元素并重新构建堆
11.         for (int i = n - 1; i > 0; i--) {
12.             swap(arr, 0, i);
13.             heapify(arr, i, 0);
14.         }
15.     }
17.     private static void heapify(int[] arr, int n, int i) {
18.         int largest = i;
19.         int left = 2 * i + 1;
20.         int right = 2 * i + 2;
22.         if (left < n && arr[left] > arr[largest]) {
23.             largest = left;
24.         }
26.         if (right < n && arr[right] > arr[largest]) {
27.             largest = right;
28.         }
30.         if (largest != i) {
31.             swap(arr, i, largest);
32.             heapify(arr, n, largest);
33.         }
34.     }
36.     private static void swap(int[] arr, int i, int j) {
37.         int temp = arr[i];
38.         arr[i] = arr[j];
39.         arr[j] = temp;
40.     }
42.     public static void main(String[] args) {
43.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
44.         heapSort(arr);
45.         System.out.println("Sorted array: " + Arrays.toString(arr));
46.     }
47. }

复制代码

时间复杂度

• 均匀时间复杂度：O(n log n)
  
• 最优时间复杂度：O(n log n)
  
• 最差时间复杂度：O(n log n)
  

八、计数排序（Counting Sort）

原理

计数排序是一种非比较排序算法，实用于整数排序。通过统计元素出现的次数，然后根据累计的次数将元素放置到正确的位置。
代码实现

1. public class CountingSort {
2.     public static void countingSort(int[] arr) {
3.         if (arr == null || arr.length == 0) {
4.             return;
5.         }
7.         int max = arr[0];
8.         int min = arr[0];
9.         for (int num : arr) {
10.             if (num > max) {
11.                 max = num;
12.             }
13.             if (num < min) {
14.                 min = num;
15.             }
16.         }
18.         int range = max - min + 1;
19.         int[] count = new int[range];
20.         int[] output = new int[arr.length];
22.         for (int num : arr) {
23.             count[num - min]++;
24.         }
26.         for (int i = 1; i < range; i++) {
27.             count[i] += count[i - 1];
28.         }
30.         for (int i = arr.length - 1; i >= 0; i--) {
31.             output[count[arr[i] - min] - 1] = arr[i];
32.             count[arr[i] - min]--;
33.         }
35.         System.arraycopy(output, 0, arr, 0, arr.length);
36.     }
38.     public static void main(String[] args) {
39.         int[] arr = {64, 34, 25, 12, 22, 11, 90};
40.         countingSort(arr);
41.         System.out.println("Sorted array: " + Arrays.toString(arr));
42.     }
43. }

复制代码

时间复杂度

• 均匀时间复杂度：O(n + k)（此中 k 是元素的范围）
  
• 最优时间复杂度：O(n + k)
  
• 最差时间复杂度：O(n + k)
  

总结

这八大排序算法各有优缺点，实用于不同的场景。在实际应用中，应根据数据的规模和特点选择符合的排序算法。

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