常用排序算法及Java实现
# 排序算法
# 选择排序
# 算法思想
从数组中选择最小元素，将它与数组的第一个元素交换位置。再从数组剩下的元素中选择出最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
# 代码实现
/**
* 选择排序
*
* @param arr /
*/
public static void selection(int[] arr) {
int len = arr.length;
for (int i = 0; i < len; i++) {
int min = i;
for (int j = i + 1; j < len; j++) {
if (arr[min] > arr[j]) {
min = j;
}
}
if(i!=min){
swap(arr, i, min);
}
}
System.out.println(Arrays.toString(arr));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
# 冒泡排序
# 算法思想
从左到右不断交换相邻逆序的元素，在一轮的循环之后，可以让未排序的最大元素上浮到右侧。
在一轮循环中，如果没有发生交换，那么说明数组已经是有序的，此时可以直接退出。
# 代码实现
/**
* 冒泡排序
*/
public static void bubble(int[] arr) {
int len = arr.length;
boolean sorted = false;
//一轮下来都没有发生交换，则已经有序了
for (int i = len - 1; i > 0 && !sorted; i--) {
sorted = true;
for (int j = 0; j < i; j++) {
if (arr[j + 1] < arr[j]) {
sorted = false;
swap(arr, i, j);
}
}
}
System.out.println("冒泡排序结果：" + Arrays.toString(arr));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 插入排序
# 算法思想
每一步将一个待排序的数据插入到前面已经排好序的有序序列中，直到插完所有元素为止。
算法实现：直接插入排序是将无序序列中的数据插入到有序的序列中，在遍历无序序列时，首先拿无序序列中的首元素去与有序序列中的每一个元素比较并插入到合适的位置，一直到无序序列中的所有元素插完为止。对于一个无序序列arr{4，6，8，5，9}来说，我们首先先确定首元素4是有序的，然后在无序序列中向右遍历，6大于4则它插入到4的后面，再继续遍历到8，8大于6则插入到6的后面，这样继续直到得到有序序列{4，5，6，8，9}。
# 代码实现
public static void insert(int[] arr) {
int len = arr.length;
for (int i = 1; i < len; i++) {
//arr[j] < arr[j - 1] 如果比最后一个都大那就不用排了
for (int j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
swap(arr, j - 1, j);
}
}
System.out.println("插入排序结果：" + Arrays.toString(arr));
}
1
2
3
4
5
6
7
8
9
10
2
3
4
5
6
7
8
9
10
# 希尔排序
# 算法思想
希尔排序是把序列按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量的逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个序列恰好被分为一组，算法便终止。
算法实现：希尔排序需要定义一个增量，这里选择增量为gap=length/2，缩小增量以gap=gap/2的方式，这个增量可以用一个序列来表示，{n/2,(n/2)/2....1}，称为增量序列，这个增量是比较常用的，也是希尔建议的增量，称为希尔增量，但其实这个增量序列不是最优的。
也可以采用一种更复杂的增量序列
// 1, 4, 13, 40, ...
while (h < lengh / 3) {
h = 3 * h + 1;
}
1
2
3
4
2
3
4
# 代码实现
public static void shell(int[] arr) {
int len = arr.length;
int gap = 1;
//找到合适的间隙
while (gap < len / 3) {
gap = gap * 3 + 1;
}
while (gap >= 1) {
for (int i = gap; i < len; i++) {
for (int j = i; j >= gap && arr[j] < arr[j - gap]; j -= gap) {
swap(arr, j - gap, j);
}
}
gap /= 3;
}
System.out.println("希尔排序结果：" + Arrays.toString(arr));
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 归并排序
# 算法思想
归并排序（Merge sort）是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
算法步骤
- 申请空间，使其大小为两个已经排序序列之和，该空间用来存放合并后的序列；
- 设定两个指针，最初位置分别为两个已经排序序列的起始位置；
- 比较两个指针所指向的元素，选择相对小的元素放入到合并空间，并移动指针到下一位置；
- 重复步骤 3 直到某一指针达到序列尾；
- 将另一序列剩下的所有元素直接复制到合并序列尾。
# 代码实现
public static void main(String[] args) {
int arr[] = {5, 11, 7, 9, 2, 3, 12, 8, 6, 1, 4, 10};
mergeSort(arr, 0, arr.length - 1);
System.out.println("归并排序结果：" + Arrays.toString(arr));
}
/**
* 归并排序(治)
*/
public static void merge(int[] arr, int low, int middle, int high) {
int[] tmpArray = new int[high - low + 1];
int left = low;
int right = middle + 1;
int index = 0;
//左边或者右边的拷贝完了，则不再比较
while (left <= middle && right <= high) {
if (arr[left] < arr[right]) {
tmpArray[index++] = arr[left++];
} else {
tmpArray[index++] = arr[right++];
}
}
//如果是左边的剩下了
if (left <= middle) {
System.arraycopy(arr, left, tmpArray, index, middle - left + 1);
}
//如果是右边的剩下了
if (right <= high) {
System.arraycopy(arr, right, tmpArray, index, high - right + 1);
}
if (tmpArray.length >= 0) {
System.arraycopy(tmpArray, 0, arr, low, tmpArray.length);
}
}
/**
* 归并排序(分) 自顶向上
*/
public static void mergeSort(int[] arr, int low, int high) {
//分 完成
if (low >= high) {
return;
}
int middle = ((high - low) >> 1) + low;
mergeSort(arr, low, middle);
mergeSort(arr, middle + 1, high);
merge(arr, low, middle, high);
}
/**
* 归并排序(分) 自底向上
*/
public static void mergeSort(int[] arr) {
int len = arr.length;
for (int size = 1; size < len; size += size) {
for (int i = 0; i < len - size; i += size + size) {
merge(arr, i, i + size - 1, Math.min(i + size + size - 1, len-1));
}
}
}
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
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
# 快速排序
# 算法思想
快速排序通过一个切分元素将数组分为两个子数组，左子数组小于等于切分元素，右子数组大于等于切分元素，将这两个子数组排序也就将整个数组排序了。
# 代码实现
public static void sort(int[] arr, int low, int high) {
if (low < high) {
int partition = partition(arr, low, high);
sort(arr, low, partition);
sort(arr, partition + 1, high);
}
}
/**
* 切分
*/
private static int partition(int[] arr, int low, int high) {
int index = low + 1;
for (int i = index; i <= high; i++) {
if (arr[i] < arr[low]) {
swap(arr, index++, i);
}
}
swap(arr, --index, low);
return index;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 堆排序
# 算法思想
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列； 小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列； 堆排序的平均时间复杂度为 Ο(nlogn)。
现代操作系统很少使用堆排序，因为它无法利用局部性原理进行缓存，也就是数组元素很少和相邻的元素进行比较和交换。
构建堆
无序数组建立堆最直接的方法是从左到右遍历数组进行上浮操作。一个更高效的方法是从右至左进行下沉操作，如果一个节点的两个节点都已经是堆有序，那么进行下沉操作可以使得这个节点为根节点的堆有序。叶子节点不需要进行下沉操作，可以忽略叶子节点的元素，因此只需要遍历一半的元素即可。
# 代码实现
/**
* @author blog.unclezs.com
* @date 2020/7/30 18:19
*/
public class HeapSort {
public static void main(String[] args) {
int arr[] = {88, 11, 22, 3, 5, 1, 19};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static void sort(int[] arr) {
int len = arr.length;
buildHeap(arr, len);
for (int i = len - 1; i > 0; i--) {
//首尾交换
swap(arr, 0, i);
//重新维护堆性质
heapify(arr, 0, --len);
}
}
private static void buildHeap(int[] arr, int len) {
for (int i = 0; i < len / 2; i++) {
heapify(arr, i, len);
}
}
private static void heapify(int[] arr, int index, int len) {
int left = 2 * index + 1;
int right = 2 * index + 2;
int max = index;
if (left < len && arr[left] > arr[max]) {
max = left;
}
if (right < len && arr[right] > arr[max]) {
max = right;
}
if (max != index) {
swap(arr, max, index);
heapify(arr, max, len);
}
}
/**
* 交换
*
* @param arr 数组
* @param self 自身
* @param other 另一个
*/
private static void swap(int[] arr, int self, int other) {
int tmp = arr[self];
arr[self] = arr[other];
arr[other] = tmp;
}
}
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
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
# 计数排序
# 算法思想
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序，计数排序要求输入的数据必须是有确定范围的整数。
算法的步骤如下：
- 找出待排序的数组中最大和最小的元素
- 统计数组中每个值为i的元素出现的次数，存入数组C的第i项
- 对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）
- 反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1
# 代码实现
/**
* 计数排序
*
* @author blog.unclezs.com
* @date 2020/7/30 19:01
*/
public class CountSort {
public static void main(String[] args) {
int arr[] = {5, 11, 7, 9, 2, 3, 12, 8, 6, 1, 4, 10};
sort(arr);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr) {
//找出最大值
OptionalInt optionalInt = Arrays.stream(arr).max();
if (optionalInt.isPresent()) {
int max = optionalInt.getAsInt();
int[] bucket = new int[max + 1];
for (int v : arr) {
bucket[v] += 1;
}
int index = 0;
for (int i = 0; i < bucket.length; i++) {
while (bucket[i] > 0) {
bucket[i] -= 1;
arr[index++] = i;
}
}
}
}
}
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
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
# 桶排序
# 算法思想
桶排序是计数排序的升级版。它利用了函数的映射关系，高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效，我们需要做到这两点：
在额外空间充足的情况下，尽量增大桶的数量 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中 同时，对于桶中元素的排序，选择何种比较排序算法对于性能的影响至关重要。
# 代码实现
/**
* @author blog.unclezs.com
* @date 2020/7/30 19:35
*/
public class BucketSort {
public static void main(String[] args) {
int arr[] = {5, 11, 7, 9, 2, 3, 12, 8, 6, 1, 4, 10};
sort(arr, 5);
System.out.println(Arrays.toString(arr));
}
private static void sort(int[] arr, int bucketSize) {
if (arr.length == 0) {
return;
}
int minValue = arr[0];
int maxValue = arr[0];
for (int value : arr) {
if (value < minValue) {
minValue = value;
} else if (value > maxValue) {
maxValue = value;
}
}
int bucketCount = (maxValue - minValue) / bucketSize + 1;
int[][] buckets = new int[bucketCount][0];
// 利用映射函数将数据分配到各个桶中
for (int item : arr) {
int index = (item - minValue) / bucketSize;
buckets[index] = arrAppend(buckets[index], item);
}
int arrIndex = 0;
for (int[] bucket : buckets) {
if (bucket.length <= 0) {
continue;
}
// 对每个桶进行排序，这里使用了归并排序
MergeSort.sort(bucket);
for (int value : bucket) {
arr[arrIndex++] = value;
}
}
}
/**
* 自动扩容，并保存数据
*/
private static int[] arrAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
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
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
# 基数排序
# 算法思想
基数排序是一种非比较型整数排序算法，其原理是将整数按位数切割成不同的数字，然后按每个位数分别比较。由于整数也可以表达字符串（比如名字或日期）和特定格式的浮点数，所以基数排序也不是只能使用于整数。
基数排序有两种方法：
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
- 基数排序：根据键值的每位数字来分配桶；
- 计数排序：每个桶只存储单一键值；
- 桶排序：每个桶存储一定范围的数值；
# 代码实现
/**
* 基数排序
* 考虑负数的情况还可以参考： https://code.i-harness.com/zh-CN/q/e98fa9
*/
public class RadixSort {
public static void main(String[] args) {
int arr[] = {5, 11, 7, 9, 2, 3, 12, 8, 6, 1, 4, 10};
sort(arr);
System.out.println(Arrays.toString(arr));
}
public static int[] sort(int[] arr) {
int maxDigit = getMaxDigit(arr);
return radixSort(arr, maxDigit);
}
/**
* 获取最高位数
*/
private static int getMaxDigit(int[] arr) {
int maxValue = getMaxValue(arr);
return getNumLength(maxValue);
}
private static int getMaxValue(int[] arr) {
int maxValue = arr[0];
for (int value : arr) {
if (maxValue < value) {
maxValue = value;
}
}
return maxValue;
}
protected static int getNumLength(long num) {
if (num == 0) {
return 1;
}
int lenght = 0;
for (long temp = num; temp != 0; temp /= 10) {
lenght++;
}
return lenght;
}
private static int[] radixSort(int[] arr, int maxDigit) {
int mod = 10;
int dev = 1;
for (int i = 0; i < maxDigit; i++, dev *= 10, mod *= 10) {
// 考虑负数的情况，这里扩展一倍队列数，其中 [0-9]对应负数，[10-19]对应正数 (bucket + 10)
int[][] counter = new int[mod * 2][0];
for (int j = 0; j < arr.length; j++) {
int bucket = ((arr[j] % mod) / dev) + mod;
counter[bucket] = arrayAppend(counter[bucket], arr[j]);
}
int pos = 0;
for (int[] bucket : counter) {
for (int value : bucket) {
arr[pos++] = value;
}
}
}
return arr;
}
/**
* 自动扩容，并保存数据
*
* @param arr
* @param value
*/
private static int[] arrayAppend(int[] arr, int value) {
arr = Arrays.copyOf(arr, arr.length + 1);
arr[arr.length - 1] = value;
return arr;
}
}
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
71
72
73
74
75
76
77
78
79
80
81
82
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
71
72
73
74
75
76
77
78
79
80
81
82
# 算法对比
# 参考
在 GitHub 编辑此页 (opens new window)
上次更新: 2024/02/25, 12:11:11