Skip to content

Commit 0c81ed9

Browse files
mood321mood321
committed
一些算法笔记和题目
1 parent 6b2bf88 commit 0c81ed9

11 files changed

Lines changed: 856 additions & 98 deletions

File tree

‎src/main/java/Conllection/SelectSort.java‎

Lines changed: 21 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -18,24 +18,43 @@ public static void main(String[] args) {
1818

1919

2020
}
21+
22+
/**
23+
* 归并排序法 主函数
24+
* @param arr
25+
*/
2126
public static void mergeSort(int[] arr) {
2227
if (arr == null || arr.length < 2) {
2328
return;
2429
}
2530
mergeSort(arr, 0, arr.length - 1);
2631
}
2732

33+
/**
34+
* 归并排序法 分治 并合并拆开的结果集
35+
* @param arr
36+
* @param l
37+
* @param r
38+
*/
2839
public static void mergeSort(int[] arr, int l, int r) {
2940
if (l == r) {
3041
return;
3142
}
32-
int mid = l + ((r - l) >> 1);
43+
int mid = l + ((r - l) >> 1); //正中间一个元素下标
3344
mergeSort(arr, l, mid);
3445
mergeSort(arr, mid + 1, r);
3546
merge(arr, l, mid, r);
3647
}
48+
49+
/**
50+
* 归并排序法 对数组 起始位置l 结束r 中间点m 两段进行合并排序
51+
* @param arr
52+
* @param l
53+
* @param m
54+
* @param r
55+
*/
3756
public static void merge(int[] arr, int l, int m, int r) {
38-
int[] help = new int[r - l + 1];
57+
int[] help = new int[r - l + 1]; //辅助数组
3958
int i = 0;
4059
int p1 = l;
4160
int p2 = m + 1;

‎src/main/java/algorithm/basic/Code_03_HeapSort.java‎

Lines changed: 163 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,163 @@
1+
package algorithm.basic;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* @Created by mood321
7+
* @Date 2019/10/6 0006
8+
* @Description 堆的操作 入堆 出堆 和堆 排序
9+
*/
10+
public class Code_03_HeapSort {
11+
/**
12+
* 堆排序 代码
13+
*
14+
* @param arr
15+
*/
16+
public static void heapSort(int[] arr) {
17+
if (arr == null || arr.length < 2) {
18+
return;
19+
}
20+
//加入堆
21+
for (int i = 0; i < arr.length; i++) {
22+
heapInsert(arr, i);
23+
}
24+
25+
int size = arr.length;
26+
swap(arr, 0, --size);// 把最大值放到最后 堆范围-1
27+
while (size > 0) {
28+
heapify(arr, 0, size);
29+
swap(arr, 0, --size);
30+
}
31+
}
32+
33+
/**
34+
* <p> 1.把需要入堆的元素放在 heapsize+1 位置（最后一个节点）
35+
* <p> 2.去和父节点比较大小 如大顶堆 比父节点大就交换 （父节点index= (子节点index-1) /2） 然后继续比较
36+
*
37+
* @param arr
38+
* @param index
39+
*/
40+
public static void heapInsert(int[] arr, int index) {
41+
while (arr[index] > arr[(index - 1) / 2]) {
42+
swap(arr, index, (index - 1) / 2);
43+
index = (index - 1) / 2;
44+
}
45+
}
46+
47+
/**
48+
* 出堆 操作
49+
* <p> 1.头结点和最后一个节点交换 交换后最后一个节点是需要弹出的值 堆大小-1
50+
*
51+
* <p> 2.继续堆化 此时顶点的数据 不一定是最大的 他需要和子节点大的比较 大于则不动 小于交换
52+
* <p> ps:（此处不是和每个节点比较 因为堆只要求父节点大于子节点 不要求左节点小于右节点）
53+
* <p> 3.交换后 继续2的操作
54+
* 此方法只做2-3
55+
*
56+
* @param arr
57+
* @param index
58+
* @param size
59+
*/
60+
public static void heapify(int[] arr, int index, int size) {
61+
int left = index * 2 + 1; // 拿到左节点下标
62+
while (left < size) { // 规定范围 且让左节点必须存在
63+
int largest = left + 1 < size && arr[left + 1] > arr[left] ? left + 1 : left;// 有节点存在 且大于右节点 给右节点 不然返回左节点
64+
largest = arr[largest] > arr[index] ? largest : index;//
65+
if (largest == index) {
66+
break;
67+
}
68+
// 走到这 说明子节点较大
69+
swap(arr, index, largest);// 交换
70+
index = largest;// 当前节点来到交换后的节点
71+
left = index * 2 + 1;
72+
73+
}
74+
75+
}
76+
77+
public static void swap(int[] arr, int i, int j) {
78+
int tmp = arr[i];
79+
arr[i] = arr[j];
80+
arr[j] = tmp;
81+
}
82+
83+
// for test
84+
public static void comparator(int[] arr) {
85+
Arrays.sort(arr);
86+
}
87+
88+
// for test
89+
public static int[] generateRandomArray(int maxSize, int maxValue) {
90+
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
91+
for (int i = 0; i < arr.length; i++) {
92+
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
93+
}
94+
return arr;
95+
}
96+
97+
// for test
98+
public static int[] copyArray(int[] arr) {
99+
if (arr == null) {
100+
return null;
101+
}
102+
int[] res = new int[arr.length];
103+
for (int i = 0; i < arr.length; i++) {
104+
res[i] = arr[i];
105+
}
106+
return res;
107+
}
108+
109+
// for test
110+
public static boolean isEqual(int[] arr1, int[] arr2) {
111+
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
112+
return false;
113+
}
114+
if (arr1 == null && arr2 == null) {
115+
return true;
116+
}
117+
if (arr1.length != arr2.length) {
118+
return false;
119+
}
120+
for (int i = 0; i < arr1.length; i++) {
121+
if (arr1[i] != arr2[i]) {
122+
return false;
123+
}
124+
}
125+
return true;
126+
}
127+
128+
// for test
129+
public static void printArray(int[] arr) {
130+
if (arr == null) {
131+
return;
132+
}
133+
for (int i = 0; i < arr.length; i++) {
134+
System.out.print(arr[i] + " ");
135+
}
136+
System.out.println();
137+
}
138+
139+
// for test
140+
public static void main(String[] args) {
141+
int testTime = 500000;
142+
int maxSize = 100;
143+
int maxValue = 100;
144+
boolean succeed = true;
145+
for (int i = 0; i < testTime; i++) {
146+
int[] arr1 = generateRandomArray(maxSize, maxValue);
147+
int[] arr2 = copyArray(arr1);
148+
heapSort(arr1);
149+
comparator(arr2);
150+
if (!isEqual(arr1, arr2)) {
151+
succeed = false;
152+
break;
153+
}
154+
}
155+
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
156+
157+
int[] arr = generateRandomArray(maxSize, maxValue);
158+
printArray(arr);
159+
heapSort(arr);
160+
printArray(arr);
161+
}
162+
163+
}

‎src/main/java/algorithm/basic/Code_04_QuickSort.java‎

Lines changed: 132 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,132 @@
1+
package algorithm.basic;
2+
3+
import java.util.Arrays;
4+
5+
/**
6+
* @Created by mood321
7+
* @Date 2019/10/5 0005
8+
* @Description 荷兰国旗问题来改进快速排序
9+
*/
10+
public class Code_04_QuickSort {
11+
12+
public static void quickSort(int[] arr) {
13+
if(arr==null || arr.length<2){
14+
return;
15+
}
16+
quickSort(arr,0,arr.length-1);
17+
}
18+
public static void quickSort(int[] arr, int l, int r) {
19+
if(l<r){ //只有数组 有多个元素才排序 这也是递归结束条件
20+
// 在普通快速排序中 排序时间复杂度 受数据状况有关 如果最后一个数据项正好是整个数组的等于区域的数 是O(N*log(N))
21+
// 改进 不固定用最后一个 书籍用一个数放在最后 去拍
22+
swap(arr, l + (int) (Math.random() * (r - l + 1)), r);
23+
int[] p = partition(arr, l, r); // 递归 分治
24+
quickSort(arr,l,p[0]-1);// 小于区域 在排序
25+
quickSort(arr,p[1]+1,r);// 大于
26+
}
27+
}
28+
public static int[] partition(int[] arr, int l, int r) {
29+
int less = l - 1, more = r;//less 和花旗国问题一致 more 向前一个 用最后一个作为num 划分区域
30+
while (l < more) {
31+
if (arr[l] < arr[r]) {
32+
swap(arr, l++, ++less); // 小于的时候 小于区域范围+1（++less） 把当前l 的值和（++less）的值交换 这里（++less）的值要要么是l 要么是等于范围的值 所以交换不会出错
33+
}else if(arr[l]>arr[r]){
34+
swap(arr,l,--more); // 和 小于逻辑一样 但交换玩l不++ 因为小于的交换回来的数要么是小于的（没找到等于的） 要么是等于（找到等于的） 而大于的交换回来的就不一定了
35+
}else {
36+
l++;
37+
}
38+
39+
}
40+
swap(arr,more,r);// r位置必定是 等于r的 交换到等于区域
41+
return new int[]{less+1,more}; // 返回等于区域的下标
42+
}
43+
44+
public static void swap(int[] arr, int i, int j) {
45+
int tmp = arr[i];
46+
arr[i] = arr[j];
47+
arr[j] = tmp;
48+
}
49+
// for test
50+
public static void comparator(int[] arr) {
51+
Arrays.sort(arr);
52+
}
53+
54+
// for test
55+
public static int[] generateRandomArray(int maxSize, int maxValue) {
56+
int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
57+
for (int i = 0; i < arr.length; i++) {
58+
arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
59+
}
60+
return arr;
61+
}
62+
63+
// for test
64+
public static int[] copyArray(int[] arr) {
65+
if (arr == null) {
66+
return null;
67+
}
68+
int[] res = new int[arr.length];
69+
for (int i = 0; i < arr.length; i++) {
70+
res[i] = arr[i];
71+
}
72+
return res;
73+
}
74+
75+
// for test
76+
public static boolean isEqual(int[] arr1, int[] arr2) {
77+
if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
78+
return false;
79+
}
80+
if (arr1 == null && arr2 == null) {
81+
return true;
82+
}
83+
if (arr1.length != arr2.length) {
84+
return false;
85+
}
86+
for (int i = 0; i < arr1.length; i++) {
87+
if (arr1[i] != arr2[i]) {
88+
return false;
89+
}
90+
}
91+
return true;
92+
}
93+
94+
// for test
95+
public static void printArray(int[] arr) {
96+
if (arr == null) {
97+
return;
98+
}
99+
for (int i = 0; i < arr.length; i++) {
100+
System.out.print(arr[i] + " ");
101+
}
102+
System.out.println();
103+
}
104+
105+
// for test
106+
public static void main(String[] args) {
107+
int testTime = 500000;
108+
int maxSize = 100;
109+
int maxValue = 100;
110+
boolean succeed = true;
111+
for (int i = 0; i < testTime; i++) {
112+
int[] arr1 = generateRandomArray(maxSize, maxValue);
113+
int[] arr2 = copyArray(arr1);
114+
quickSort(arr1);
115+
comparator(arr2);
116+
if (!isEqual(arr1, arr2)) {
117+
succeed = false;
118+
printArray(arr1);
119+
printArray(arr2);
120+
break;
121+
}
122+
}
123+
System.out.println(succeed ? "Nice!" : "Fucking fucked!");
124+
125+
int[] arr = generateRandomArray(maxSize, maxValue);
126+
printArray(arr);
127+
quickSort(arr);
128+
printArray(arr);
129+
130+
}
131+
132+
}

0 commit comments

Comments
 (0)