复习
常用排序
排序问题经典的计算机问题，凡是有数组的地方，基本都会有排序，而计算机底层非常多的数据结构都是基于数组的。之前咱们学习了常见的三种排序，选择排序，冒泡排序和插入排序：
-
选择排序：从左到右，每次找最小的放左边 -
冒泡排序：从左到右，两两比较，最大的放最右边 -
插入排序：从左到右，构建一个小的有序数组，每次将右边那个数插入到左边的有序位置
使用Java实现：
package com.zhangdapeng520.z05_review;
import java.util.Arrays;
/**
* @文件 Z01Review.java
* @作者 张大鹏
* @版本 v0.1.0
* @描述 复习1
* @创建时间 2022-10-19 07:34:00
* @更新时间 2022-10-19 07:34:00
*/
public class Z01Review {
public static void swap(int[] arr, int a, int b) {
int t = arr[a];
arr[a] = arr[b];
arr[b] = t;
}
public static void selectSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 0; i < arr.length - 1; i++) {
int minIndex = i;
for (int j = i; j < arr.length; j++) {
if (arr[minIndex] > arr[j]) {
minIndex = j;
}
}
swap(arr, minIndex, i);
}
}
public static void bubbleSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
System.out.println("数组长度：" + arr.length);
for (int i = 0; i < arr.length - 1; i++) {
System.out.print("第" + (i + 1) + "次：");
int swapCount = 0;
for (int j = 0; j < arr.length - 1 - i; j++) {
System.out.print(j + "," + (j + 1) + " ");
if (arr[j] > arr[j + 1]) {
swap(arr, j, j + 1);
swapCount++;
}
}
System.out.println();
if (swapCount == 0) {
break;
}
}
}
public static void insertSort(int[] arr) {
if (arr == null || arr.length < 2) {
return;
}
for (int i = 1; i < arr.length; i++) {
for (int j = i - 1; j >= 0 && arr[j] > arr[j + 1]; j--) {
swap(arr, j, j + 1);
}
}
}
public static void main(String[] args) {
int[] arr;
arr = new int[]{3, 2, 1, 33, 22, 11, 333, 222, 111, -1, -2, -3};
selectSort(arr);
System.out.println(Arrays.toString(arr));
arr = new int[]{3, 2, 1, 33, 22, 11, 333, 222, 111, -1, -2, -3};
bubbleSort(arr);
System.out.println(Arrays.toString(arr));
arr = new int[]{3, 2, 1, 33, 22, 11, 333, 222, 111, -1, -2, -3};
insertSort(arr);
System.out.println(Arrays.toString(arr));
}
}
使用Go实现：
package main
import "fmt"
/*
@Time : 2022/10/19 7:56
@Author : 张大鹏
@File : main
@Software: Goland2021.3.1
@Description:
*/
func swap(arr []int, a, b int) {
arr[a], arr[b] = arr[b], arr[a]
}
func selectSort(arr []int) {
if len(arr) < 2 {
return
}
for i := 0; i < len(arr)-1; i++ {
minIndex := i
for j := i; j < len(arr); j++ {
if arr[minIndex] > arr[j] {
minIndex = j
}
}
swap(arr, minIndex, i)
}
}
func bubbleSort(arr []int) {
if len(arr) < 2 {
return
}
for i := 0; i < len(arr)-1; i++ {
for j := 0; j < len(arr)-1-i; j++ {
if arr[j] > arr[j+1] {
swap(arr, j, j+1)
}
}
}
}
func insertSort(arr []int) {
if len(arr) < 2 {
return
}
for i := 1; i < len(arr); i++ {
for j := i - 1; j >= 0 && arr[j] > arr[j+1]; j-- {
swap(arr, j, j+1)
}
}
}
func main() {
var arr []int
arr = []int{3, 2, 1, 33, 22, 11, 333, 222, 111, -1, -2, -3}
selectSort(arr)
fmt.Println(arr)
arr = []int{3, 2, 1, 33, 22, 11, 333, 222, 111, -1, -2, -3}
bubbleSort(arr)
fmt.Println(arr)
arr = []int{3, 2, 1, 33, 22, 11, 333, 222, 111, -1, -2, -3}
insertSort(arr)
fmt.Println(arr)
}
前缀数组
之前咱们学习了前缀数组，这是一种用于解决求数组指定范围类所有数累加和的算法。比如arr=[1...n]，要求x-y之间所有数的连续累加和，其中x<y且x<0,y<数组长度-1。解决这种问题提供了两种方案，一种是占用内存高，但是查询效率最快的建表方案，一种的占用内存相对较低，查询效率稍微较差的构建前缀数组的方案。
Java实现前缀和数组：
package com.zhangdapeng520.z01_pre_num;
import java.util.Arrays;
/**
* @文件 Z01Table.java
* @作者 张大鹏
* @版本 v0.1.0
* @描述 实现前缀和
* @创建时间 2022-10-19 08:46:00
* @更新时间 2022-10-19 08:46:00
*/
public class Z01PreNum {
public static int[] getPreNumArr(int[] arr) {
if (arr == null || arr.length < 2) {
return arr;
}
int[] preArr = new int[arr.length];
preArr[0] = arr[0];
for (int i = 1; i < arr.length; i++) {
preArr[i] = preArr[i - 1] + arr[i];
}
return preArr;
}
public static int getSumByPreNumArr(int[] arr, int L, int R) {
if (arr == null || L > R) {
return 0;
}
if (L == 0) {
return arr[R];
}
return arr[R] - arr[L - 1];
}
public static int getSumByPreNumTable(int[][] table, int L, int R) {
if (table == null || L > R) {
return 0;
}
return table[L][R];
}
public static int[][] getPreNumTable(int[] arr) {
int[][] arr2 = new int[arr.length][arr.length];
for (int i = 0; i < arr.length; i++) {
for (int j = i; j < arr.length; j++) {
arr2[i][j] = getSumByPreNumArr(arr, i, j);
}
}
return arr2;
}
public static void main(String[] args) {
int[] arr = {1, 2, 3, 4, 5};
int[] preNumArr = getPreNumArr(arr);
int[][] preNumTable = getPreNumTable(preNumArr);
System.out.println(Arrays.toString(preNumArr));
// `2-4`的和：`arr[2][4] = 12`，验证`3+4+5=12`
System.out.print(getSumByPreNumArr(preNumArr, 2, 4) + " " + getSumByPreNumTable(preNumTable, 2, 4) + "\n");
// `0-3`的和：`arr[0][3]=10`，验证`1+2+3+4=10`
System.out.print(getSumByPreNumArr(preNumArr, 0, 3) + " " + getSumByPreNumTable(preNumTable, 0, 3) + "\n");
// `1-3`的和：`arr[1][3]=9`，验证`2+3+4=9`
System.out.print(getSumByPreNumArr(preNumArr, 1, 3) + " " + getSumByPreNumTable(preNumTable, 1, 3) + "\n");
}
}
Go实现前缀和数组：
package main
import "fmt"
/*
@Time : 2022/10/19 12:56
@Author : 张大鹏
@File : main
@Software: Goland2021.3.1
@Description: 前缀数组
*/
func GetPreNumArr(arr []int) []int {
if len(arr) < 2 {
return arr
}
var result = []int{arr[0]}
for i := 1; i < len(arr); i++ {
t := result[i-1] + arr[i]
result = append(result, t)
}
return result
}
func GetPreNumTable(preNumArr []int) [][]int {
var result [][]int
if len(preNumArr) < 2 {
return result
}
for i := 0; i < len(preNumArr); i++ {
var tmpArr []int
for j := 0; j < len(preNumArr); j++ {
if j < i {
tmpArr = append(tmpArr, 0)
} else {
tmpArr = append(tmpArr, GetSumByPreNumArr(preNumArr, i, j))
}
}
result = append(result, tmpArr)
}
return result
}
func GetSumByPreNumArr(preNumArr []int, L, R int) int {
if L > R || len(preNumArr) == 0 {
return 0
}
if L == 0 {
return preNumArr[R]
}
return preNumArr[R] - preNumArr[L-1]
}
func GetSumByPreNumTable(table [][]int, L, R int) int {
if L > R || len(table) == 0 {
return 0
}
return table[L][R]
}
func main() {
arr := []int{1, 2, 3, 4, 5}
fmt.Println(arr)
preNumArr := GetPreNumArr(arr)
fmt.Println(preNumArr)
table := GetPreNumTable(preNumArr)
fmt.Println(table)
// `2-4`的和：`arr[2][4] = 12`，验证`3+4+5=12`
var L, R int
L, R = 2, 4
fmt.Println(GetSumByPreNumArr(preNumArr, L, R), GetSumByPreNumTable(table, L, R))
// `0-3`的和：`arr[0][3]=10`，验证`1+2+3+4=10`
L, R = 0, 3
fmt.Println(GetSumByPreNumArr(preNumArr, L, R), GetSumByPreNumTable(table, L, R))
// `1-3`的和：`arr[1][3]=9`，验证`2+3+4=9`
L, R = 1, 3
fmt.Println(GetSumByPreNumArr(preNumArr, L, R), GetSumByPreNumTable(table, L, R))
}
二分查找
问题引出
加入我们有一个有序的数组[1,2,3,4,5]，想要从里面找到元素1的索引是多少，该如何实现呢？
二分查找是目前关于有序数组查找最高效的算法之一。基本思路是将一个有序数组拆分为左右两个部分，每次都去找中间那个数，然后比较大小，大了就继续拆分数组，往左边找，小了就往右边找。
基本实现
需求：从数组[1,2,3,4,5]中找到1
实现步骤：
找中间的数3，大了，往左边[1,2]里面找。
因为是偶数位，可以按左边拆数组，找到1，比较以后发现找到了。
伪代码
二分查找就是不断将有序数组从中间拆分为两个新数组，比较中间那个数。
// 传入数组和目标值，返回目标值的索引，找不到返回-1
func f(arr,target)int{
// 数组为空
if len(arr)==0{
return -1
}
// 记录小数组的左边索引和右边索引
int L,R=0,len(arr)-1
// 如果左边索引大于右边索引，则数组结束了
for L<=R{
// 中间索引
mid:=(L+R)/2
if arr[mid]==target{
// 找到了
return mid
}else if(arr[mid]<num){
// 小了
L=mid+1
}else{
// 大了
R=mid-1
}
}
// 没找到
return -1
}
Java实现二分查找
基本实现：
package com.zhangdapeng520.z01_binary_search;
import java.util.Arrays;
/**
* @文件 Z01BinarySearch.java
* @作者 张大鹏
* @版本 v0.1.0
* @描述 二分查找
* @创建时间 2022-10-19 22:52:00
* @更新时间 2022-10-19 22:52:00
*/
public class Z01BinarySearch2 {
// 二分查找
public static int find(int[] arr, int num) {
if (arr == null || arr.length == 0) {
return -1;
}
int L = 0;
int R = arr.length - 1;
while (L <= R) {
int mid = (L + R) / 2;
if (arr[mid] == num) {
return mid;
} else if (arr[mid] < num) {
L = mid + 1;
} else {
R = mid - 1;
}
}
return -1;
}
public static void main(String[] args) {
int[] arr = new int[]{-75, -45, -39, -12, 8, 19, 26, 32, 35, 51};
Arrays.sort(arr);
System.out.println(Arrays.toString(arr));
System.out.println("length: " + arr.length);
System.out.println("二分找到的索引：" + find(arr, -39));
}
}
基于大量的随机数据测试：
package com.zhangdapeng520.z01_binary_search;
import java.util.Arrays;
/**
* @文件 Z01BinarySearch.java
* @作者 张大鹏
* @版本 v0.1.0
* @描述 二分查找
* @创建时间 2022-10-19 22:52:00
* @更新时间 2022-10-19 22:52:00
*/
public class Z01BinarySearch3 {
// 二分查找
public static int binarySearch(int[] arr, int num) {
if (arr == null || arr.length == 0) {
return -1;
}
int L = 0;
int R = arr.length - 1;
while (L <= R) {
int mid = (L + R) / 2;
if (arr[mid] == num) {
return mid;
} else if (arr[mid] < num) {
L = mid + 1;
} else {
R = mid - 1;
}
}
return -1;
}
public static int getRandomInt(int min, int max) {
return (int) (Math.random() * max) + min;
}
public static int[] getRandomArrBySize(int min, int max, int size) {
int[] arr = new int[size];
for (int i = 0; i < arr.length; i++) {
arr[i] = getRandomInt(min, max);
}
return arr;
}
public static int[] getRandomArr(int min, int max) {
int size = getRandomInt(10, 1000);
return getRandomArrBySize(min, max, size);
}
public static void main(String[] args) {
int testTime = 500000;
int min = 10;
int max = 100;
boolean succeed = true;
for (int i = 0; i < testTime; i++) {
int size = getRandomInt(10, 1000);
int[] arr = getRandomArrBySize(min, max, size);
Arrays.sort(arr);
int index = getRandomInt(0, size);
int value = arr[index];
int findIndex = binarySearch(arr, value);
if (arr[index] != arr[findIndex]) {
System.out.println(Arrays.toString(arr));
System.out.println("出错了！" + "index:" + index + " value:" + value + " size:" + size + " findIndex:" + findIndex);
System.out.println(arr[index] + " " + arr[findIndex]);
succeed = false;
break;
}
}
System.out.println(succeed ? "测试通过" : "测试失败");
}
}
Go实现二分查找
基本实现：
package main
import (
"fmt"
)
/*
@Time : 2022/10/19 12:56
@Author : 张大鹏
@File : main
@Software: Goland2021.3.1
@Description: 二分查询
*/
func BinarySearch(arr []int, target int) int {
if len(arr) == 0 {
return -1
}
L, R := 0, len(arr)-1
for L <= R {
mid := (L + R) / 2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
L = mid + 1
} else {
R = mid - 1
}
}
return -1
}
func main() {
arr := []int{1, 2, 3, 4, 5}
fmt.Println(BinarySearch(arr, 3))
}
基于大量测试数据：
package main
import (
"fmt"
"math/rand"
"time"
)
/*
@Time : 2022/10/19 12:56
@Author : 张大鹏
@File : main
@Software: Goland2021.3.1
@Description: 二分查询
*/
func init() {
rand.Seed(time.Now().UnixNano())
}
func BubbleSort(arr []int) {
if len(arr) <= 1 {
return
}
for i := 0; i < len(arr); i++ {
for j := 0; j < len(arr)-1-i; j++ {
if arr[j] > arr[j+1] {
arr[j], arr[j+1] = arr[j+1], arr[j]
}
}
}
}
func GetRandomInt(min, max int) int {
n := max - min
return rand.Intn(n) + min
}
func GetRandomArr(min, max, size int) []int {
var result []int
for i := 0; i < size; i++ {
result = append(result, GetRandomInt(min, max))
}
return result
}
func BinarySearch(arr []int, target int) int {
if len(arr) == 0 {
return -1
}
L, R := 0, len(arr)-1
for L <= R {
mid := (L + R) / 2
if arr[mid] == target {
return mid
} else if arr[mid] < target {
L = mid + 1
} else {
R = mid - 1
}
}
return -1
}
func main() {
var (
testTime = 500000
min = 10
max = 100
succeed = true
)
for i := 0; i < testTime; i++ {
size := GetRandomInt(10, 1000)
arr := GetRandomArr(min, max, size)
BubbleSort(arr)
index := GetRandomInt(1, size)
value := arr[index]
findIndex := BinarySearch(arr, value)
if arr[index] != arr[findIndex] {
fmt.Println(arr)
fmt.Println("出错了！", "index:", index, " value:", value, " size:", size, " findIndex:", findIndex)
fmt.Println(arr[index], " ", arr[findIndex])
succeed = false
break
}
}
if succeed {
fmt.Println("测试通过")
} else {
fmt.Println("测试失败")
}
}
文章评论