算法的可视化
https://visualgo.net/zh/sorting
算法教学
https://www.geeksforgeeks.org/quick-sort/
Problem 1.1 #
解决选择问题，先排序，随后找出第k项，令k=N/2。
冒泡排序 Bubble Sort #
将数组分为两个子表，[未排序][已排序]。
遍历未排序子表相邻的两个元素比较大小，并交换顺序(将较大的移动到后面)。则每次遍历后的最后一个元素归为已排序，对这个操作进行遍历。
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++) {
if (arr[j] < arr[j + 1]) {
int m = arr[j];
arr[j] = arr[j + 1];
arr[j + 1] = m;
}
}
}1.a
c++实现
for (int i = 0; i < n - 1; i++) {
for (int j = 0; j < n - i - 1; j++)
if(p[j]<p[j+1]) {
swap(p[j], p[j + 1]);
}
}1.a
选择排序 Select Sort #
将数组分为两个子表，[已排序][未排序]。
取未排序子表中第一个元素作为基准，与剩下的未排序子表元素遍历比较，如果有更小的元素，则重设基准，遍历完成后将基准元素移到已排序子表的末尾。
选择排序是在外循环交换数据，速度略快于冒泡。
for (int i = 0; i < n - 1; i++) {
int mini = i;
for (int j = i + 1; j < n; j++) {
if (arr[j] < arr[mini]) {
mini = j;
}
}
int m = arr[mini];
arr[mini] = arr[i];
arr[i] = m;
}1.b
插入排序 Insert Sort #
如字面意思，选择一个元素，如果它比前面的元素小，则与它交换位置，重复这个过程。
for (int i = 1; i < arr.length; i++) {
int key = arr[i];
// 寻找插入位置，j为位置的Index
int j = i - 1;
while (j >= 0 && arr[j] > key) {
// 如果插入位置的数值较大，向左移一位
arr[j + 1] = arr[j];
j -= 1;
}
arr[j + 1] = key;
}1.c
归并排序 Merge Sort #
该算法是采用分治法的典型应用。 核心思路: 归并与分解。先使每个子序列有序，有序的子序列合并，得到完全有序的序列。这称为二路归并。 将待排序序列R[0...n-1]看成是n个长度为1的有序序列，将相邻的有序表成对归并，得到n/2个长度为2的有序表；将这些有序序列再次归并，得到n/4个长度为4的有序序列；如此反复进行下去，最后得到一个长度为n的有序序列。
初始关键字 49 38 65 97 76 13 27 第一趟归并 (38 49) (65 97) (13 76) 27 第二趟归并 (38 49 65 97) (13 27 76) 第三趟归并 (13 27 38 49 65 76 97)
static void mergeSort() {
long prev = System.currentTimeMillis();
int[] array = generateArray();
int size = array.length;
int step = 2; // 设定一个步长
for (; step <= size; step *= 2) { // 步长每次以2的指数级增长
for (int i = 0; i < size; i += step) {
if (i + step <= size) {
mergeSort(array, i, i + step / 2 - 1, i + step - 1);
}
}
}
// 对越出的部分(非2的次幂)进行处理
int lost = size % (step / 2);
if (lost != 0) {
mergeSort(array, 0, size - lost - 1, size - 1);
}
long runtime = System.currentTimeMillis() - prev;
System.out.println("time cost=" + runtime);
}
static void mergeSort(int[] array, int start, int mid, int end) {
int i = start;
int j = mid + 1;
int index = 0;
int[] temp = new int[end - start + 1];
// 对有序列进行排序
while (i <= mid && j <= end) {
temp[index++] = array[i] < array[j] ? array[i++] : array[j++];
}
while (i <= mid) {
temp[index++] = array[i++];
}
while (j <= end) {
temp[index++] = array[j++];
}
// 数据转移
index = 0;
for (int k = start; k <= end; k++) {
array[k] = temp[index++];
}
}1.d
快速排序 Quick Sort #
快速排序使用分治法（Divide and conquer）策略来把一个表分为较小和较大的2个子表，然后递归地排序两个子表。
步骤为：
挑选基准值：从表中挑出一个元素(这里的选择最后一个元素)，称为“基准”（pivot），
分割：重新排序数列，所有比基准值小的元素放在基准前面，这个操作结束后，基准值的位置已经完成排序。
递归排序子序列：递归地将小于基准值的子序列和大于基准值的子序列排序。
static int partition(int[] arr, int start, int end) {
// 设最后一位为pivot, 有i个元素比pivot小，就把pivot移到i+1位上
int i = start - 1;
for (int j = start; j < end; j++) {
if (arr[j] <= arr[end]) {
swap(arr, ++i, j);
}
}
swap(arr, i + 1, end);
return i + 1;
}
static void sort(int[] arr, int start, int end) {
if (start < end) {
// pi 是已经排序的pivot的位置 arr[pi] 现在位于正确的位置
int pi = partition(arr, start, end);
sort(arr, start, pi - 1);
sort(arr, pi + 1, end);
}
}1.e
耗时 #
取值范围为[0,10000]的数据进行测试。
Sort
10
100
1000
10000
Bubble
8660ns
472406ns
8.87ms
175.53ms
Select
5238ns
188711ns
4.43ms
8.58ms
Insert
4331ns
147016ns
4.45ms
3.25ms
Merge
12990ns
109581ns
0.86ms
0.54ms
Quick
9569ns
66629ns
0.88ms
0.36ms
Problem 1.2 #
Word Puzzle，在给定的二维数组中查找单词
核心思路：
查找，左右翻转，查找，左右翻转，转置…
package com.masoniclab.problem.one;
import java.io.File;
import java.io.FileNotFoundException;
import java.io.FileOutputStream;
import java.io.PrintStream;
import java.util.Scanner;
public class Puzzle {
private static String puzzle_path = System.getProperty("user.dir") + "//src//com//masoniclab//problem//one//puzzle.txt";
private static String dict_path = System.getProperty("user.dir") + "//src//com//masoniclab//problem//one//dict.txt";
private static String output_path = System.getProperty("user.dir") + "//src//com//masoniclab//problem//one//output.csv";
private static int row = 16; // 行
private static int col = row; // 列
// 生成字谜
// http://puzzlemaker.discoveryeducation.com/WordSearchSetupForm.asp
// 只处理矩阵，不检测对角线方向
public static void main(String[] args) throws FileNotFoundException {
char[][] puzzle = new char[row][col];
String[] dict = new String[10];
File txt = new File(puzzle_path);
Scanner input = new Scanner(txt);
for (int i = 0; i < puzzle[0].length; i++) {
puzzle[i] = input.nextLine().toLowerCase().toCharArray();
}
txt = new File(dict_path);
input = new Scanner(txt);
for (int i = 0; i < dict.length; i++) {
dict[i] = input.nextLine().toLowerCase();
}
// 查找
long prev = System.nanoTime();
puzzle = find(puzzle, dict);
long runtime = System.nanoTime() - prev;
System.out.println("Word Puzzle time cost= " + runtime + " ns");
// 写入CSV
File out = new File(output_path);
PrintStream ps = new PrintStream(new FileOutputStream(out));
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
ps.append(String.valueOf(puzzle[i][j])).append(",");
}
ps.append(System.lineSeparator());
}
}
private static char[][] find(char[][] puzzle, String[] dict) {
findWord(puzzle, dict);
puzzle = reverse(puzzle);
findWord(puzzle, dict);
puzzle = reverse(puzzle);
puzzle = transpose(puzzle);
findWord(puzzle, dict);
puzzle = reverse(puzzle);
findWord(puzzle, dict);
puzzle = reverse(puzzle);
puzzle = transpose(puzzle);
return puzzle;
}
private static void findWord(char[][] puzzle, String[] dict) {
for (int i = 0; i < row; i++) {
String s = String.valueOf(puzzle[i]);
for (String key : dict) {
if (s.contains(key)) {
int start = s.indexOf(key);
for (int k = 0; k < key.length(); k++) {
puzzle[i][start + k] = Character.toTitleCase(puzzle[i][start + k]);
}
}
}
}
}
// 更换行列
private static char[][] transpose(char[][] arr) {
char[][] t = new char[row][col];
for (int i = 0; i < row; i++) {
for (int j = 0; j < col; j++) {
t[i][j] = arr[j][i];
}
}
return t;
}
// 更换左右顺序
private static char[][] reverse(char[][] arr) {
char[][] t = new char[arr.length][arr[0].length];
for (int i = 0; i < arr.length; i++) {
int k = arr[i].length;
for (int j = 0; j < k; j++) {
t[i][j] = arr[i][k - 1 - j];
}
}
return t;
}
}1.f
耗时
Size
TIme Cost
8x8
630318 ns
12x12
1120324ns
16x16
1451791ns
Problem 1.5 #
计算输入数据N的二进制表示中1的个数。奇数的二进制1的个数等于N/2的商的二进制中1的个数+1。
十进制
二进制
整除
1的个数
78
1001110
T
4
39
100111
F
4
19
10011
F
3
9
1001
F
2
4
100
T
1
2
10
T
1
能整除2末尾加0，不能整除2末尾加1.
public static int ones( int n ) {
if( n < 2 )
return n;
return n % 2 + ones( n / 2 );
}Problem 1.10 #
2100(mod5)=? 利用同余，2100=242524mod5=1
Problem 1.13 #
设计泛型类Collection，存储Object对象，以及元素数量，提供isEmpty, makeEmpty, insert, remove, isPresent方法。
思考: 一个基于数组(Array)的Collection，其元素连续地存储在数组内部，核心方法是insert和remove，而不是set和get。 size指的是内部数组储存的非null元素数量，而不是数组的长度。
Each ArrayList instance has a capacity. The capacity is the size of the array used to store the elements in the list. It is always at least as large as the list size. As elements are added to an ArrayList, its capacity grows automatically. The details of the growth policy are not specified beyond the fact that adding an element has constant amortized time cost.
路径: problem.one.GenericCollection 参考资料 List源代码 https://www.javaguides.net/2018/09/java-generics-best-practices.htmlhttps://www.geeksforgeeks.org/generics-in-java/
核心组件
- Index溢出检查
reSize实现 参考ArrayList类的ensureCapacity方法。 要注意的问题:
- 数组存储上限2147483647
- 溢出问题，参考
grow方法
insert实现 要注意的问题:
- 数组范围检查，不够要扩增
- 在某处插入元素后，把后续的元素index+1
参考资料 #
static int partition(int[] arr, int start, int end) {
// 设最后一位为pivot, 有i个元素比pivot小，就把pivot移到i+1位上
int i = start - 1;
for (int j = start; j < end; j++) {
if (arr[j] <= arr[end]) {
swap(arr, ++i, j);
}
}
swap(arr, i + 1, end);
return i + 1;
}
static void sort(int[] arr, int start, int end) {
if (start < end) {
// pi 是已经排序的pivot的位置 arr[pi] 现在位于正确的位置
int pi = partition(arr, start, end);
sort(arr, start, pi - 1);
sort(arr, pi + 1, end);
}
}Geek https://www.geeksforgeeks.org/quick-sort/
VisualGo https://visualgo.net/zh/sorting
Algorithm-Visualizer https://algorithm-visualizer.org/brute-force/bubble-sort
Wiki https://zh.wikipedia.org/wiki/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F