EightAlgorithmsByJava

Java八大算法

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
package sort;


import java.util.Arrays;

/**
* @author WANGYEKUN
* @version 1.0
* @date 2019/7/5 0005 20:28
* 冒泡排序
*/
public class BubbleSort {
private static void bubbleSort(int[] a) {
//外层循环控制比较的次数
for (int i = 0; i < a.length - 1; i++) {
//内层循环控制到达位置
for (int j = 0; j < a.length - i - 1; j++) {
//前面的元素比后面大就交换
if (a[j] > a[j + 1]) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
System.out.println("shellSort: " + Arrays.toString(a));
}
}
}
}

public static void main(String[] args) {
int[] b = new int[]{1, 8, 2, 9, 7, 10};
System.out.println("BubbleSortBefore: " + Arrays.toString(b));
bubbleSort(b);
System.out.println("BubbleSortAfter: " + Arrays.toString(b));
}
}

2、堆排序

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
package sort;

import java.util.Arrays;

/**
* @author WANGYEKUN
* @version 1.0
* @date 2019/7/5 0005 21:05
* 堆排序
*/
public class HeapSort {
private static void heapSort(int[] arr) {
for (int i = arr.length; i > 0; i--) {
maxHeap(arr, i);
// 堆顶元素(第一个元素)与Kn交换
int temp = arr[0];
arr[0] = arr[i - 1];
arr[i - 1] = temp;
}
}

private static void maxHeap(int[] arr, int limit) {
if (arr.length <= 0 || arr.length < limit) {
return;
}
int parentIdx = limit / 2;

for (; parentIdx >= 0; parentIdx--) {
if (parentIdx * 2 >= limit) {
continue;
}
// 左子节点位置
int left = parentIdx * 2;
// 右子节点位置,如果没有右节点,默认为左节点位置
int right = (left + 1) >= limit ? left : (left + 1);

int maxChildId = arr[left] >= arr[right] ? left : right;
// 交换父节点与左右子节点中的最大值
if (arr[maxChildId] > arr[parentIdx]) {
int temp = arr[parentIdx];
arr[parentIdx] = arr[maxChildId];
arr[maxChildId] = temp;
System.out.println("maxHeap: " + Arrays.toString(arr));
}
}
}

public static void main(String[] args) {
int[] b = new int[]{1, 8, 2, 9, 7, 10};
System.out.println("HeapSortBefore: " + Arrays.toString(b));
heapSort(b);
System.out.println("HeapSortAfter: " + Arrays.toString(b));
}
}

3、二分查询插入排序

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
package sort;

import java.util.Arrays;

/**
* @author WANGYEKUN
* @version 1.0
* @date 2019/7/5 0005 20:54
* 二分查找插入排序
*/
public class InsertSort {
private static void insertSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
for (int j = i + 1; j > 0; j--) {
if (arr[j - 1] <= arr[j]) {
break;
}
//交换操作
int temp = arr[j];
arr[j] = arr[j - 1];
arr[j - 1] = temp;
System.out.println("insertSort: " + Arrays.toString(arr));
}

}

}

public static void main(String[] args) {
int[] b = new int[]{1, 8, 2, 9, 7, 10};
System.out.println("InsertSortBefore: " + Arrays.toString(b));
insertSort(b);
System.out.println("InsertSortAfter: " + Arrays.toString(b));
}
}

4、归并查询排序

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
package sort;

import java.util.Arrays;

/**
* @author WANGYEKUN
* @version 1.0
* @date 2019/7/5 0005 21:25
* 归并排序
*/
public class MergingSort {
private static int[] mergingSort(int[] arr) {
if (arr.length <= 1) {
return arr;
}

int num = arr.length >> 1;
int[] leftArr = Arrays.copyOfRange(arr, 0, num);
int[] rightArr = Arrays.copyOfRange(arr, num, arr.length);
System.out.println("split two array: " + Arrays.toString(leftArr) + " And " + Arrays.toString(rightArr));
//不断拆分为最小单元,再排序合并
return mergeTwoArray(mergingSort(leftArr), mergingSort(rightArr));
}

private static int[] mergeTwoArray(int[] arr1, int[] arr2) {
int i = 0, j = 0, k = 0;
//申请额外的空间存储合并之后的数组
int[] result = new int[arr1.length + arr2.length];
//选取两个序列中的较小值放入新数组
while (i < arr1.length && j < arr2.length) {
if (arr1[i] <= arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}
//序列1中多余的元素移入新数组
while (i < arr1.length) {
result[k++] = arr1[i++];
}
//序列2中多余的元素移入新数组
while (j < arr2.length) {
result[k++] = arr2[j++];
}
System.out.println("Merging: " + Arrays.toString(result));
return result;
}

public static void main(String[] args) {
int[] b = new int[]{1, 8, 2, 9, 7, 10};
System.out.println("MergingSortBefore: " + Arrays.toString(b));
mergingSort(b);
System.out.println("MergingSortAfter: " + Arrays.toString(b));
}
}

5、快速排序

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
package sort;

import java.util.Arrays;

/**
* @author WANGYEKUN
* @version 1.0
* @date 2019/7/5 0005 21:16
* 快速排序
*/
public class QuickSort {
private static void quickSort(int[] arr, int low, int high) {
if (arr.length <= 0) {
return;
}
if (low >= high) {
return;
}
int left = low;
int right = high;

// 挖坑1:保存基准的值
int temp = arr[left];
while (left < right) {
// 坑2:从后向前找到比基准小的元素,插入到基准位置坑1中
while (left < right && arr[right] >= temp) {
right--;
}
arr[left] = arr[right];
// 坑3:从前往后找到比基准大的元素,放到刚才挖的坑2中
while (left < right && arr[left] <= temp) {
left++;
}
arr[right] = arr[left];
}
// 基准值填补到坑3中,准备分治递归快排
arr[left] = temp;
System.out.println("quickSort: " + Arrays.toString(arr));
quickSort(arr, low, left - 1);
quickSort(arr, left + 1, high);
}

public static void main(String[] args) {
int[] b = new int[]{1, 8, 2, 9, 7, 10};
System.out.println("quickSortBefore: " + Arrays.toString(b));
quickSort(b, 0, 5);
System.out.println("quickSortAfter: " + Arrays.toString(b));
}
}

6、基数排序

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
package sort;

import java.util.Arrays;

/**
* @author WANGYEKUN
* @version 1.0
* @date 2019/7/5 0005 21:27
* 基数排序
*/
public class RadixSort {
public static void radixSort(int[] arr) {
if (arr.length <= 1) {
return;
}

//取得数组中的最大数,并取得位数
int max = 0;
for (int i = 0; i < arr.length; i++) {
if (max < arr[i]) {
max = arr[i];
}
}
int maxDigit = 1;
while (max / 10 > 0) {
maxDigit++;
max = max / 10;
}
System.out.println("maxDigit: " + maxDigit);

//申请一个桶空间
int[][] buckets = new int[10][arr.length];
int base = 10;

//从低位到高位,对每一位遍历,将所有元素分配到桶中
for (int i = 0; i < maxDigit; i++) {
//存储各个桶中存储元素的数量
int[] bktLen = new int[10];

//分配:将所有元素分配到桶中
for (int j = 0; j < arr.length; j++) {
int whichBucket = (arr[j] % base) / (base / 10);
buckets[whichBucket][bktLen[whichBucket]] = arr[j];
bktLen[whichBucket]++;
}

//收集:将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
int k = 0;
for (int b = 0; b < buckets.length; b++) {
for (int p = 0; p < bktLen[b]; p++) {
arr[k++] = buckets[b][p];
}
}

System.out.println("Sorting: " + Arrays.toString(arr));
base *= 10;
}
}

public static void main(String[] args) {
int[] b = new int[]{1, 8, 2, 9, 7, 10};
System.out.println("RadixSortBefore: " + Arrays.toString(b));
radixSort(b);
System.out.println("RadixSortAfter: " + Arrays.toString(b));
}
}

7、选择排序

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
package sort;

import java.util.Arrays;

/**
* @author WANGYEKUN
* @version 1.0
* @date 2019/7/5 0005 21:01
* 选择排序
*/
public class SelectSort {
private static void selectSort(int[] arr) {
for (int i = 0; i < arr.length - 1; i++) {
int min = i;
// 选出之后待排序中值最小的位置
for (int j = i + 1; j < arr.length; j++) {
if (arr[j] < arr[min]) {
min = j;
}
}
if (min != i) {
// 交换操作
int temp = arr[min];
arr[min] = arr[i];
arr[i] = temp;
System.out.println("selectSort: " + Arrays.toString(arr));
}
}
}

public static void main(String[] args) {
int[] b = new int[]{1, 8, 2, 9, 7, 10};
System.out.println("SelectSortBefore: " + Arrays.toString(b));
selectSort(b);
System.out.println("SelectSortAfter: " + Arrays.toString(b));
}
}

8、希尔排序

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
package sort;

import java.util.Arrays;

/**
* @author WANGYEKUN
* @version 1.0
* @date 2019/7/5 0005 20:58
* 希尔排序
*/
public class ShellSort {
private static void shellSort(int[] arr) {
int gap = arr.length / 2;
// 不断缩小gap,直到1为止
for (; gap > 0; gap /= 2) {
// 使用当前gap进行组内插入排序
for (int j = 0; (j + gap) < arr.length; j++) {
for (int k = 0; (k + gap) < arr.length; k += gap) {
if (arr[k] > arr[k + gap]) {
// 交换操作
int temp = arr[k + gap];
arr[k + gap] = arr[k];
arr[k] = temp;
System.out.println("shellSort: " + Arrays.toString(arr));
}
}
}
}
}

public static void main(String[] args) {
int[] b = new int[]{1, 8, 2, 9, 7, 10};
System.out.println("ShellSortBefore: " + Arrays.toString(b));
shellSort(b);
System.out.println("ShellSortAfter: " + Arrays.toString(b));
}
}
  • 注:参考网友的算法,加上自己编写测试,仅供参考。
------------------------------------本文结束感谢您的阅读--------------------------------
wangyekun wechat
扫一扫关注一波
坚持原创,您的支持将鼓励我继续创作!