复习
常用的排序算法
昨天主要学习了常用的排序算法：
-
选择排序：从左到右，每次找最小的放前面 -
冒泡排序：从左到右，每次把最大的放后面 -
插入排序：从左到右，每次保证左边的小数组是有序的，将右边的一个数插入到左边排序后的某个位置
伪代码
选择排序：
for (i=0;i<len(arr)-1;i++){
minIndex=i;
for (j=i+1;j<len(arr);j++){
if arr(minIndex)>arr[j]{
minIndex=j;
}
}
交换 minIndex 和 i 位置的元素
}
冒泡排序：
for (i=0;i<len(arr)-1;i++){
for(j=0;j<len(arr)-1-i;j++){
if arr(j)>arr[j+1]{
交换 j 和 j+1 位置的元素
}
}
}
插入排序：
for (i=1;i<len(arr);i++){
for(j=i-1;j>0&&arr[j]>arr[j+1];j--){
交换 j 和 j+1 位置的元素
}
}
使用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)
}
前缀和数组
问题引出
假设我们有一个数组：[1,2,3,4,5,6,7,8,9,...10000]，我想要知道这个数组的索引位置0到索引位置3的和连续位置和是多少？
这里，我们直接求arr[0]+arr[1]+arr[2]+arr[3]就行。
当规模扩大的时候，我们想要求任意索引位置L到任意索引位置N的值是多少的时候，怎么办呢？
这里，我们依旧可以采用最简单的方案：结果 = 遍历索引L到索引R的所有元素的和。
当频率变大，可能在短时间内，需要查询上亿次的时候呢？
上面的方案依旧是可以的，不过效率极其低下。
以上问题就是前缀和问题，是非常经典的一个算法问题，要解决这个问题，目前主要有两种思路，给大家介绍一下。
解决前缀和问题
解决上面的问题，有两种思路：
-
方案1：建立一张二维数组表，存储每个索引范围的累加和，需要的时候，直接去表里面查。 -
方案2：建立一个前缀和辅助数组，存储的是连续累加和数，当需要的时候，利用数学公式进行查询。
建表方案
假设我们有数组[1,2,3,4,5]，索引是0到4，我们可以建立二维数组表如下：
[
[1, 3, 6, 10, 15],
[0, 2, 5, 9, 14],
[0, 0, 3, 7, 12],
[0, 0, 0, 4, 9 ],
[0, 0, 0, 0, 5 ],
]
二维数组的横坐标表示R右边索引，纵坐标表示L左边索引。比如我们想要求0到4所有元素的累加和，结果就是arr[0][4]，从数组中取出该元素的值为15。
其他示例：
-
2-4的和：arr[2][4] = 12，验证3+4+5=12 -
0-3的和：arr[0][3]=10，验证1+2+3+4=10 -
1-3的和：arr[1][3]=9，验证2+3+4=9
这种方案的优点是查询快，无需计算，缺点是需要耗费非常大的内存空间。
前缀和数组方案
假设我们有数组[1,2,3,4,5]，索引是0到4，我们可以建立前缀和数组表如下：
[1,3,6,10,15]
数组的每个元素是连续累加和，比如0-1，0-2，0-3等的连续累加和。建立好这个前缀和数组以后，我们可以利用公式进行计算：
-
如果 L=0：L-R的累加和为arr[R] -
如果 L!=0：L-R的累加和为arr[R]-arr[L-1]
利用公式计算一下：
-
2-4的和：arr[4]-arr[1]=15-3= 12，验证3+4+5=12 -
0-3的和：arr[3]=10，验证1+2+3+4=10 -
1-3的和：arr[3]-arr[0]=10-1=9，验证2+3+4=9
这种方案的优点是占用内存空间小，缺点是当L不为0的时候，每次都需要计算。如果查询频率非常高的话，将会非常的影响性能。
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))
}
文章评论