十大排序算法（Java实现）
十大排序算法（Java实现）
十大排序算法（Java实现）
排序算法框架
排序算法性质
插入排序
直接插入排序
希尔排序
选择排序
简单选择排序
堆排序
交换排序
冒泡排序
快速排序
归并排序
基数排序
计数排序
桶排序
更多文章点击 >> 这里
排序算法框架
排序算法性质
插入排序
直接插入排序
从第一个元素开始，认为该元素是已排序的。
取出下一元素，与前面已经排好序的部分进行比较。
若比排好序部分的元素小，则将排好序部分的元素后移到下一位置。
遍历数组，直至结束。
最好的情况是数组有序，时间复杂度为 O ( n ) O(n)O(n) ，平均复杂度是 O ( n 2 ) O(n^2)O(n
2
) 。
代码实现
public class Solution {
public static void main(String[] args) {
int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
insertSort(array);
System.out.println(Arrays.toString(array));
}
private static void insertSort(int[] array) {
for (int i = 0; i < array.length - 1; i++) {
int data = array;
int index = i;
while(index >= 0 && array > data) {
array = array;
index--;
}
array = data;
}
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
希尔排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
代码实现
public class Solution {
public static void main(String[] args) {
int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
shellSort(array);
System.out.println(Arrays.toString(array));
}
private static void shellSort(int[] array) {
int gap = array.length / 2;
while (gap > 0) {
for (int i = gap; i < array.length; i++) {
int index = i - gap;
int temp = array;
while (index >= 0 && array > temp) {
swap(array, index, index + gap);
index -= gap;
}
// array = temp;
}
gap /= 2;
System.out.println(Arrays.toString(array));
}
}
private static void swap(int[] array, int i, int index) {
int temp = array;
array = array;
array = temp;
}
}
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
选择排序
简单选择排序
从未排序的初始数组中寻找最小元素放置首位。
从剩余元素中继续寻找最小元素，放到已排序序列的尾部
遍历数组，直至结束。
时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。
代码实现**
public class Solution {
public static void main(String[] args) {
int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
selectionSort(array);
System.out.println(Arrays.toString(array));
}
private static void selectionSort(int[] array) {
for (int i = 0; i < array.length; i++) {
int index = i;
for (int j = i; j < array.length; j++) {
if (array < array) {
index = j;
}
}
swap(array, index, i);
}
}
private static void swap(int[] array, int index, int i) {
int temp = array;
array = array;
array = temp;
}
}
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
堆排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
代码实现**
public class Solution {
// 建堆
public static void creatHeap(int[] arr, int n) {
// 因为数组是从0开始的
for (int i = (n - 1) / 2; i >= 0; i--) {
percolateDown(arr, i, n);
}
}
// 插入
private static void insertHeap(int[] array, int data, int n) {
array = data;
percolatrUp(array, n);
}
// 删除栈顶元素
private static void deleteHeap(int[] arr, int n) {
arr = arr;
arr = -1;
percolateDown(arr, 0, n - 1);
}
// 上浮
private static void percolatrUp(int[] array, int n) {
int data = array;
int father = (n - 1) / 2;
while (data < array && father >= 0) {
array = array;
array = data;
n = father;
father = (n - 1) / 2;
}
array = data;
}
// 下滤
private static void percolateDown(int[] arr, int i, int n) {
int father = arr;
int child = 2 * i + 1;
// 遍历整个该根结点的子树
while (child <= n) {
// 定位左右结点小的那一个
if (child + 1 <= n && arr < arr) {
child += 1;
}
// 若根结点比子结点小，说明已经是个小堆
if (father < arr) {
break;
}
// 互换根结点和子结点
arr = arr;
arr = father;
// 重新定位根结点和子结点
i = child;
child = i * 2 + 1;
}
}
public static void main(String[] args) {
int[] array = { 15, 13, 12, 5, 20, 1, 8, 9 };
creatHeap(array, array.length - 1);
System.out.println(Arrays.toString(array));
deleteHeap(array, array.length - 1);
System.out.println(Arrays.toString(array));
deleteHeap(array, array.length - 2);
System.out.println(Arrays.toString(array));
insertHeap(array, 3, array.length - 2);
System.out.println(Arrays.toString(array));
}
}
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
60
61
62
63
64
65
66
67
68
69
70
交换排序
冒泡排序
依次比较相邻的两个元素，若前者比后者大则交换，这样数组的最后一位是最大值。
在除了最后一位的未排序数组上继续重复以上步骤，每一步都能找到一个最大值放在后面。
遍历数组，直至结束。
最好的情况是数组已排序，时间复杂为 O ( n ) O(n)O(n) ，平均时间复杂度为 O ( n 2 ) O(n^2)O(n
2
) 。
代码实现
import java.util.Arrays;
public class Solution {
private static void bubbleSort(int[] nums) {
// 循环次数
for (int i = 0; i < nums.length - 1; i++) {
// 比较次数
for (int j = 0; j < nums.length - 1 - i; j++) {
if (nums > nums) {
swap(nums, j, j + 1);
}
}
}
}
private static void swap(int[] nums, int j, int i) {
int temp = nums;
nums = nums;
nums= temp;
}
public static void main(String[] args) {
int[] nums = { 6, 3, 8, 2, 9, 1 };
bubbleSort(nums);
System.out.println(Arrays.toString(nums));
}
}
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
快速排序
时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
代码实现
public class Solution {
// Median-of-Three Partitioning
public static int selectPivot(int[] array, int left, int right) {
int middle = (left + right) / 2;
if (array > array)
swap(array, middle, left);
if (array > array)
swap(array, left, right);
if (array > array)
swap(array, left, middle);
return array;
}
public static void sort(int[] array, int left, int right) {
if (left >= right)
return;
int index = partition(array, left, right);
sort(array, left, index - 1);
sort(array, index + 1, right);
}
public static int partition(int[] array, int left, int right){
int pivot = selectPivot(array, left, right);
while(left < right){
while(left < right && array >= pivot){
right--;
}
if (left < right) {
array = array;
}
while(left < right && array < pivot){
left++;
}
if (left < right) {
array = array;
}
}
array = pivot;
return right;
}
public static void swap(int[] array, int left, int right){
int value = array;
array = array;
array = value;
}
public static void main(String[] args) {
int[] array = {8, 1, 4, 9, 3, 5, 2, 7, 0, 6};
// System.out.println(Arrays.toString(array));
sort(array, 0, array.length - 1);
System.out.println(Arrays.toString(array));
}
}
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
归并排序
将长序列从中间分成两个子序列。
对这两个子序列依次继续执行重复分裂，直至不能再分。
递归返回两两排好序的子序列。
平均时间复杂度为 O ( n l o g n ) O(nlogn)O(nlogn) 。
代码实现**
public class Solution {
public static void main(String[] args) {
int[] array = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
int[] arr = MergeSort(array);
System.out.println(Arrays.toString(arr));
}
private static int[] MergeSort(int[] array) {
if (array.length < 2)
return array;
int middle = array.length / 2;
int[] leftArray = Arrays.copyOfRange(array, 0, middle);
int[] rightArray = Arrays.copyOfRange(array, middle, array.length);
return merge(MergeSort(leftArray), MergeSort(rightArray));
}
private static int[] merge(int[] leftArray, int[] rightArray) {
int[] result = new int;
for (int index = 0, i = 0, j = 0; index < result.length; index++) {
if (i >= leftArray.length) {
result = rightArray;
} else if (j >= rightArray.length) {
result = leftArray;
} else if (leftArray > rightArray) {
result = rightArray;
} else {
result = leftArray;
}
}
return result;
}
}
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
基数排序
找到数组中最大的数，确定最多一共有几位数。
按照每个数字的最后一位，放入辅助数组中；同时设置一个计数数组，统计以数字 i 结尾的数字个数。
将辅助数组中的元素重新放入原数组中，然后按照下一位继续重复以上动作。
时间复杂度为 O ( n ∗ k ) O(n*k)O(n∗k) 。
代码实现**
public class RadixSort {
public static void main(String[] args) {
int[] array = {3, 44, 38, 4, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 32};
int[] arr = radixSort(array);
System.out.println(Arrays.toString(arr));
}
private static int[] radixSort(int[] array) {
if (array == null || array.length < 2) {
return array;
}
// 根据最大值找到最大位数
int max = 0;
for (int i = 0; i < array.length; i++) {
max = Math.max(max, array);
}
int maxDigit = 0;
while (max != 0) {
max /= 10;
maxDigit++;
}
// 第一维: 0~9
int[][] radix = new int;
// 该位为 i 的元素个数
int[] count = new int;
int m = 1;
int n = 1;
while (m <= maxDigit) {
for (int i = 0; i < array.length; i++) {
int lsd = (array / n) % 10;
radix] = array;
count++;
}
for (int i = 0, k = 0; i < 10; i++) {
if (count != 0) {
for (int j = 0; j < count; j++) {
array = radix;
}
}
count = 0;
}
n *= 10;
m++;
}
return array;
}
}
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
计数排序
找到数组中最小值和最大值，辅助数组的大小为两者之差。设最小值为 2，最大值为 9，则辅助数组大小为 7。
统计数组中每个元素出现的次数，减去最小值，存入辅助数组中。比如 2，存放在辅助数组的第 0 位，7 放在辅助数组的第 5 位。
最后反向填充数组。遍历原数组，依次将辅助数组中不为 0 的元素下标加最小值，放回原数组对应位置。
时间复杂度为 O ( n + k ) O(n + k)O(n+k) 。
代码实现
public class Solution {
public static void main(String[] args) {
int[] array = {8, 9, 4, 7, 2, 3, 5, 4, 6, 8};
int[] arr = countSort(array);
System.out.println(Arrays.toString(arr));
}
private static int[] countSort(int[] array) {
if (array.length == 0)
return array;
int min = array, max = array;
for (int i = 0; i < array.length; i++) {
if (min > array) {
min = array;
}
if (max < array) {
max = array;
}
}
int[] count = new int;
for (int i = 0; i < array.length; i++) {
count - min]++;
}
int i = 0;
int index = 0;
while (index < array.length) {
if (count != 0) {
array = i + min;
count--;
index++;
} else {
i++;
}
}
return array;
}
}
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
桶排序
————————————————
版权声明：本文为CSDN博主「iTensor」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/wshixinshouaaa/article/details/118683153
页:
[1]