各大排序算法（Java实现）

排序 算  法框架

 排序算法性质

 插入排序

直接插入排序

1. 从第一个元素开始，认为该元素是已排序的。
2. 取出下一元素，与前面已经排好序的部分进行比较。
3. 若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
4. 遍历数组，直至结束。

最好的情况是数组有序，时间复杂度为O（n）,平均复杂度是O（n²）。

 代码 实现 

1. public class Solution {
2.     public static void main(String[] args) {
3.         int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
4.         insertSort(array);
5.         System.out.println(Arrays.toString(array));
6.     }
7.     private static void insertSort(int[] array) {
8.         for (int i = 0; i < array.length - 1; i++) {
9.             int data = array[i + 1];
10.             int index = i;
11.             while(index >= 0 && array[index] > data) {
12.                 array[index + 1] = array[index];
13.                 index--;
14.             }
15.             array[index + 1] = data;
16.         }
17.     }
18. }

希尔排序

时间复杂度为 O (nlogn ) 。

代码实现 

1. public class Solution {
2.     public static void main(String[] args) {
3.         int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
4.         shellSort(array);
5.         System.out.println(Arrays.toString(array));
6.     }
7.     private static void shellSort(int[] array) {
8.         int gap = array.length / 2;
9.         while (gap > 0) {
10.             for (int i = gap; i < array.length; i++) {
11.                 int index = i - gap;
12.                 int temp = array[i];
13.                 while (index >= 0 && array[index] > temp) {
14.                     swap(array, index, index + gap);
15.                     index -= gap;
16.                 }
17. //                array[index + gap] = temp;
18.             }
19.             gap /= 2;
20.             System.out.println(Arrays.toString(array));
21.         }
22.     }
23.     private static void swap(int[] array, int i, int index) {
24.         int temp = array[i];
25.         array[i] = array[index];
26.         array[index] = temp;
27.     }
28. }

选择排序

简单选择排序

从未排序的初始数组中寻找最小元素放置首位。

从剩余元素中继续寻找最小元素，放到已排序序列的尾部

遍历数组，直至结束。

时间复杂度为 O (n²) 。

代码实现

1. public class Solution {
2.     public static void main(String[] args) {
3.         int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
4.         selectionSort(array);
5.         System.out.println(Arrays.toString(array));
6.     }
7.     private static void selectionSort(int[] array) {
8.         for (int i = 0; i < array.length; i++) {
9.             int index = i;
10.             for (int j = i; j < array.length; j++) {
11.                 if (array[j] < array[index]) {
12.                     index = j;
13.                 }
14.             }
15.             swap(array, index, i);
16.         }
17.     }
18.     private static void swap(int[] array, int index, int i) {
19.         int temp = array[index];
20.         array[index] = array[i];
21.         array[i] = temp;
22.     }
23. }

堆排序

时间复杂度为 O (nlogn)  。

代码实现

1. public class Solution {
2.     // 建堆
3.     public static void creatHeap(int[] arr, int n) {
4.         // 因为数组是从0开始的
5.         for (int i = (n - 1) / 2; i >= 0; i--) {
6.             percolateDown(arr, i, n);
7.         }
8.     }
9.     // 插入
10.     private static void insertHeap(int[] array, int data, int n) {
11.         array[n] = data;
12.         percolatrUp(array, n);
13.     }
14.     // 删除栈顶元素
15.     private static void deleteHeap(int[] arr, int n) {
16.         arr[0] = arr[n];
17.         arr[n] = -1;
18.         percolateDown(arr, 0, n - 1);
19.     }
20.     // 上浮
21.     private static void percolatrUp(int[] array, int n) {
22.         int data = array[n];
23.         int father = (n - 1) / 2;
24.         while (data < array[father] && father >= 0) {
25.             array[n] = array[father];
26.             array[father] = data;
27.             n = father;
28.             father = (n - 1) / 2;
29.         }
30.         array[father] = data;
31.     }
32.     // 下滤
33.     private static void percolateDown(int[] arr, int i, int n) {
34.         int father = arr[i];
35.         int child = 2 * i + 1;
36.         // 遍历整个该根结点的子树
37.         while (child <= n) {
38.             // 定位左右结点小的那一个
39.             if (child + 1 <= n && arr[child + 1] < arr[child]) {
40.                 child += 1;
41.             }
42.             // 若根结点比子结点小，说明已经是个小堆
43.             if (father < arr[child]) {
44.                 break;
45.             }
46.             // 互换根结点和子结点
47.             arr[i] = arr[child];
48.             arr[child] = father;
49.             // 重新定位根结点和子结点
50.             i = child;
51.             child = i * 2 + 1;
52.         }
53.     }
54.     
55.     public static void main(String[] args) {
56.         int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
57.         
58.         creatHeap(array, array.length - 1);
59.         System.out.println(Arrays.toString(array));
60.         
61.         deleteHeap(array, array.length - 1);
62.         System.out.println(Arrays.toString(array));
63.         
64.         deleteHeap(array, array.length - 2);
65.         System.out.println(Arrays.toString(array));
66.         
67.         insertHeap(array, 3, array.length - 2);
68.         System.out.println(Arrays.toString(array));
69.     }
70. }

交换排序

冒泡排序

依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。

在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。

遍历数组，直至结束。

最好的情况是数组已排序，时间复杂为 O (n) ，平均时间复杂度为 O（n²）

代码实现

1. import java.util.Arrays;
2. public class Solution {
3.     
4.     private static void bubbleSort(int[] nums) {
5.         // 循环次数
6.         for (int i = 0; i < nums.length - 1; i++) {
7.             // 比较次数
8.             for (int j = 0; j < nums.length - 1 - i; j++) {
9.                 if (nums[j] > nums[j + 1]) {
10.                     swap(nums, j, j + 1);
11.                 }
12.             }
13.         }
14.     }
15.     private static void swap(int[] nums, int j, int i) {
16.         int temp = nums[j];
17.         nums[j] = nums[i];
18.         nums[i]= temp; 
19.     }
20.     public static void main(String[] args) {
21.         int[] nums = { 6, 3, 8, 2, 9, 1 };
22.         bubbleSort(nums);
23.         System.out.println(Arrays.toString(nums));
24.     }
25. }

快速排序

时间复杂度为 O (nlogn) 。

代码实现

1. public class Solution {
2.     
3.     // Median-of-Three Partitioning
4.     public static int selectPivot(int[] array, int left, int right) {
5.         int middle = (left + right) / 2;
6.         
7.         if (array[middle] > array[right])
8.             swap(array, middle, left);
9.         if (array[left] > array[right])
10.             swap(array, left, right);
11.         if (array[middle] > array[left])
12.             swap(array, left, middle);
13.         
14.         return array[left];
15.     }
16.     
17.     public static void sort(int[] array, int left, int right) {
18.         if (left >= right)
19.             return;
20.         int index = partition(array, left, right);
21.         sort(array, left, index - 1);
22.         sort(array, index + 1, right);
23.     }
24.     
25.     public static int partition(int[] array, int left, int right){
26.         int pivot = selectPivot(array, left, right);
27.         while(left < right){
28.             while(left < right && array[right] >= pivot){
29.                 right--;
30.             }
31.             if (left < right) {
32.                 array[left++] = array[right];
33.             }
34.             while(left < right && array[left] < pivot){
35.                 left++;
36.             }
37.             if (left < right) {
38.                 array[right--] = array[left];
39.             }
40.         }
41.         array[right] = pivot;
42.         return right;
43.     }
44.     public static void swap(int[] array, int left, int right){
45.         int value = array[left];
46.         array[left] = array[right];
47.         array[right] = value;
48.     }
49.     public static void main(String[] args) {
50.         int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
51.         // System.out.println(Arrays.toString(array));
52.         sort(array, 0, array.length - 1);
53.         System.out.println(Arrays.toString(array));
54.     }
55. }

归并排序

将长序列从中间分成两个子序列。

对这两个子序列依次继续执行重复分裂，直至不能再分。

递归返回两两排好序的子序列。

平均时间复杂度为 O (nlogn) 。

代码实现

1. public class Solution {
2.     public static void main(String[] args) {
3.         int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
4.         int[] arr = MergeSort(array);
5.         System.out.println(Arrays.toString(arr));
6.     }
7.     private static int[] MergeSort(int[] array) {
8.         if (array.length < 2)
9.             return array;
10.         int middle = array.length / 2;
11.         int[] leftArray = Arrays.copyOfRange(array, 0, middle);
12.         int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
13.         return merge(MergeSort(leftArray), MergeSort(rightArray));
14.     }
15.     private static int[] merge(int[] leftArray, int[] rightArray) {
16.         int[] result = new int[leftArray.length + rightArray.length];
17.         for (int index = 0, i = 0, j = 0; index < result.length; index++) {
18.             if (i >= leftArray.length) {
19.                 result[index] = rightArray[j++];
20.             } else if (j >= rightArray.length) {
21.                 result[index] = leftArray[i++];
22.             } else if (leftArray[i] > rightArray[j]) {
23.                 result[index] = rightArray[j++];
24.             } else {
25.                 result[index] = leftArray[i++];
26.             }
27.         }
28.         return result;
29.     }
30. }

基数排序

1. 找到数组中最大的数，确定最多一共有几位数。
2. 按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
3. 将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。

时间复杂度为 O ( n ∗ k )  。

代码实现

1. public class RadixSort {
2.     public static void main(String[] args) {
3.         int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
4.         int[] arr = radixSort(array);
5.         System.out.println(Arrays.toString(arr));
6.     }
7.     private static int[] radixSort(int[] array) {
8.         if (array == null || array.length < 2) {
9.             return array;
10.         }
11.         // 根据最大值找到最大位数
12.         int max = 0;
13.         for (int i = 0; i < array.length; i++) {
14.             max = Math.max(max, array[i]);
15.         }
16.         
17.         int maxDigit = 0;
18.         while (max != 0) {
19.             max /= 10;
20.             maxDigit++;
21.         }
22.         
23.         // 第一维: 0~9
24.         int[][] radix = new int[10][array.length];
25.         // 该位为 i 的元素个数
26.         int[] count = new int[10];
27.         
28.         int m = 1;
29.         int n = 1;
30.         
31.         while (m <= maxDigit) {
32.             for (int i = 0; i < array.length; i++) {
33.                 int lsd = (array[i] / n) % 10;
34.                 radix[lsd][count[lsd]] = array[i];
35.                 count[lsd]++;
36.             }
37.             for (int i = 0, k = 0; i < 10; i++) {
38.                 if (count[i] != 0) {
39.                     for (int j = 0; j < count[i]; j++) {
40.                         array[k++] = radix[i][j];
41.                     }
42.                 }
43.                 count[i] = 0;
44.             }
45.             n *= 10;
46.             m++;
47.         }
48.         return array;
49.     }
50. }

计数排序

1. 找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
2. 统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
3. 最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。

时间复杂度为 O(n+k) 。

代码实现

1. public class Solution {
2.     public static void main(String[] args) {
3.         int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
4.         int[] arr = countSort(array);
5.         System.out.println(Arrays.toString(arr));
6.     }
7.     private static int[] countSort(int[] array) {
8.         if (array.length == 0)
9.             return array;
10.         
11.         int min = array[0], max = array[0];
12.         
13.         for (int i = 0; i < array.length; i++) {
14.             if (min > array[i]) {
15.                 min = array[i];
16.             }
17.             if (max < array[i]) {
18.                 max = array[i];
19.             }
20.         }
21.         
22.         int[] count = new int[max - min + 1];
23.         
24.         for (int i = 0; i < array.length; i++) {
25.             count[array[i] - min]++;
26.         }
27.         
28.         int i = 0;
29.         int index = 0;
30.         while (index < array.length) {
31.             if (count[i] != 0) {
32.                 array[index] = i + min;
33.                 count[i]--;
34.                 index++;
35.             } else {
36.                 i++;
37.             }
38.         }
39.         return array;
40.     }
41.     
42. }​​​​​​​

————————————————

版权声明：本文为CSDN博主「iTensor」的原创文章。

原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153