Java基础学习四---数组基础和排序算法

成功其实很简单，就是强迫自己干下去

活动地址：CSDN21天学习挑战赛

数组

数组就是用来存储一批同种类型数据的内存区域（可以理解成容器）

数组适合做一批同种类型数据的存储

1. 数组的定义

1.1 静态初始化数组

定义数组的时候直接给数组赋值
静态初始化数组的格式：

// 完整格式
数据类型[] 数组名 = new 数据类型[]{元素1，元素2 ，元素3… };
double[] scores = new double[]{89.9, 99.5, 59.5, 88.0};
int[] ages = new int[]{12, 24, 36}

// 简化格式
数据类型[] 数组名 = { 元素1，元素2 ，元素3，… };
int[] ages = {12, 24, 36};
1
2
3
4
5
6
7
8

数组是属于引用数据类型，数组变量名中存储的是存储的数组在内存中的地址信息.

1.1.1 数组的访问

注意事项：

1. 数据类型[] 数组名”也可以写成 “数据类型 数组名[] ”。
2. 什么类型的数组存放什么类型的数据，否则报错。
3. 数组一旦定义出来，程序执行的过程中，长度、类型就固定了。

1.2 动态初始化数组

定义数组的时候只确定元素的类型和数组的长度，之后再存入具体数据。
数据类型[] 数组名 = new 数据类型[长度];

数组的动态初始化格式：
数据类型[] 数组名 = new 数据类型[长度];
int[] arr = new int[3];

// 后赋值
arr[0] = 10;
System.out.println(arr[0]); // 10
1
2
3
4
5
6
7

⚫ 当前已经知道存入的元素值，用静态初始化。
⚫ 当前还不清楚要存入哪些数据，用动态初始化

总结：
⚫ 动态初始化：只指定数组长度，后期赋值，适合开始知道数据的数量，但是不确定具体元素值的业务场景。
⚫静态初始化：开始就存入元素值，适合一开始就能确定元素值的业务场景。
⚫ 两种格式的写法是独立的，不可以混用。 int[] arrs = new int[3]{30，40,50}; 错误的

2. 数组的遍历

int[] ages = {20, 30, 40, 50};
for (int i = 0; i < ages.length; i++) {
	System.out.println(ages[i]);
}
1
2
3
4

计算机算法基础---余祥宣

pdf 4星 超过75%的资源 19.47MB

下载

案例：
数组元素求最大值
for (int i = 1; i < faceScores.length; i++) {
	if(faceScores[i] > max) {
		// 替换
		max = faceScores[i];
	}
}
1
2
3
4
5
6
7
8

数组排序：就是对数组中的元素，进行升序(由小到大)或者降序（由大到小）的操作。

2.1 数组排序的技术

2.1.1 ⚫ 冒泡排序

1. 冒泡排序的思想
   ⚫ 从头开始两两比较，把较大的元素与较小的元素进行交换
   ⚫ 每轮把当前最大的一个元素存入到数组当前的末尾。
2. 冒泡排序的实现步骤。
   ⚫ 定义一个外部循环控制总共需要冒几轮（数组的长度-1）
   ⚫ 定义一个内部循环，控制每轮依次往后比较几个位置（数组长度-i-1）。
   ⚫ 如果当前位置的元素值>后一个位置的元素值，两者交换。

public class HelloWorld {
    public static void main(String []args) {
		int[] arr = {18,13,50,15,4,17,18};
		 System.out.println("arr的各个元素是：18  13  50  15  4  17  18 ");
		int temp  = 0 ;
		for(int i = 0 ;i< arr.length -1; i++){
			for(int j = 0; j<arr.length-1-i; j++){
				if(arr[j]>arr[j+1]){
					temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
		 System.out.println("arr排序后：");	
        for(int i = 0; i<arr.length; i++){
			 System.out.print(arr[i]+"\t");
		}	
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

2.1.2 ⚫ 选择排序

随机确定一个标志位（一般为第一个数字）作为最小数，然后向后遍历，找到比标志位更小的数便与标志位互换位置并更新最小数，实现步骤为：

将数组的第一个数字设置为标志位最小数并记录最小数下标。 向后遍历，发现更小数后将该数与标志位互换位置并更新最小数与最小数下标。 循环完成排序

public static void main(String[] args){
    int int[] arr = new int[]{1,6,8,9,2,3,5,4,7};
    for(int i = 0;i < arr.length-1 ; i++){//每次循环都会找出最小的数
            int minIndex = i;//记录最小数的下标
            int minNum = arr[i];//记录最小数
            for(int j=i+1 ; j<arr.length ; j++){//每次循环都会找出最小的数
                if(arr[j] < minNum){//如果当前数比最小数小，则更新最小数
                    minNum = arr[j];//更新最小数
                    minIndex = j;//更新最小数的下标
                }
            }
            arr[minIndex]=arr[i];//将最小数放到最前面
            arr[i]=minNum;//将标志位放到最小数原来所在的位置
        }
     for(int i=0;i<arr.length;i++){
            System.out.print(arr[i]);
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

2.1.3 ⚫ 快速排序 https://www.jb51.net/article/211611.htm

Mendix敏捷开发零基础学习.pdf

pdf 0星 超过10%的资源 16.68MB

下载

快速排序由于排序效率在同为O(N*logN)的几种排序方法中效率较高，因此经常被采用，再加上快速排序思想----分治法也确实实用，因此很多软件公司的笔试面试，包括像腾讯，微软等知名IT公司都喜欢考这个，还有大大小的程序方面的考试如软考，考研中也常常出现快速排序的身影。

快速排序在几种排序方法中是效率较高的

6 1 2 7 9 3 4 5 10 8
思考：在初始状态下，数字6在序列的第1位。我们的目标是将6挪到序列中间的某个位置，假设这个位置是k。现在就需要寻找这个k，并且以第k位为分界点，左边的数都小于等于6，右边的数都大于等于6

1. 分别从初始序列“6 1 2 7 9 3 4 5 10 8”两端开始“探测”。先从右往左找一个小于6的数，再从左往右找一个大于6的数，然后交换他们。这里可以用两个变量i和j，分别指向序列最左边和最右边
   

public class TestQuickOrder {
    public static void quickSort(int[] arr,int low,int high){
        int i,j,temp,t;
        if(low>high){
            return;
        }
        i=low;
        j=high;
        //temp就是基准位，默认传过来的low是最左边的数，即下标为0
        temp = arr[low];
        //[10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19] i=0,j=12,temp=10
        while (i<j) {
            //1.--------先看右边（temp是最左边的数，那么接下来肯定和最右边的数比较，然后从右往左依次挪位，一直比到有比最左边还小的数为止），依次往左递减
            while (temp<=arr[j]&&i<j) {
                j--;
            }
            //[10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19] i=0,j=11,temp=10 （右往左 因为 10>=9 下标是[11] ）
            //再看左边，依次往右递增
            while (temp>=arr[i]&&i<j) {
                i++;
            }
            //[10, 7, 2, 4, 7, 62, 3, 4, 2, 1, 8, 9, 19] i=5,j=11,temp=10 （左往右 因为 10<=62 下标是[5] ）
            //如果满足条件则交换
            if (i<j) {
                t = arr[j];
                arr[j] = arr[i];
                arr[i] = t;
            }
            //[10, 7, 2, 4, 7, 9, 3, 4, 2, 1, 8, 62, 19] i=5,j=11,temp=10 （9和62换位 ）

            //2.--------接下来5<11 继续执行
            //[10, 7, 2, 4, 7, 9, 3, 4, 2, 1, 8, 62, 19] i=0,j=10,temp=10 （右往左 因为 10>=8 下标是[10] ）
            //[10, 7, 2, 4, 7, 9, 3, 4, 2, 1, 8, 62, 19] i=10,j=10,temp=10 （左往右 因为 10<=62 下标是[11]，下表大于j=10,所以i=10 ）
            //i=j=10 退出循环
        }
        //最后将基准为与i和j相等位置的数字交换
        arr[low] = arr[i];
        arr[i] = temp;
        //[8, 7, 2, 4, 7, 9, 3, 4, 2, 1, 10, 62, 19]  （10和8换位 ）

        //递归调用左半数组 【8, 7, 2, 4, 7, 9, 3, 4, 2, 1】
        quickSort(arr, low, j-1);
        //3.-------- 后面三个不会影响到
        //[8, 7, 2, 4, 7, 9, 3, 4, 2, 1, 10, 62, 19] i=0,j=9,temp=8
        //[8, 7, 2, 4, 7, 9, 3, 4, 2, 1, 10, 62, 19] i=0,j=9,temp=8 （右往左 因为 8>=1 下标是[9] ）
        //[8, 7, 2, 4, 7, 9, 3, 4, 2, 1, 10, 62, 19] i=5,j=9,temp=8 （左往右 因为 8<=9 下标是[5] ）
        //[8, 7, 2, 4, 7, 1, 3, 4, 2, 9, 10, 62, 19] i=5,j=9,temp=8 （1和9换位 ）

        //4.-------- 接下来5<9 继续执行
        //[8, 7, 2, 4, 7, 1, 3, 4, 2, 9, 10, 62, 19] i=5,j=8,temp=8 （右往左 因为 8>=2 下标是[8] ）
        //[8, 7, 2, 4, 7, 1, 3, 4, 2, 9, 10, 62, 19] i=8,j=8,temp=8 （左往右 因为 8<=9 下标是[9]，下表大于j=8,所以i=8  ）
        //[2, 7, 2, 4, 7, 1, 3, 4, 8, 9, 10, 62, 19] i=5,j=9,temp=8 （8和2换位 ）

        //5..----又一次递归开始---- 。。。。。。接下来就不写了

        quickSort(arr, j+1, high);


    }


    public static void main(String[] args){
        int[] arr = {10,7,2,4,7,62,3,4,2,1,8,9,19};
        //默认传过去最左边和最右边的数
        quickSort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i]+"\t");
        }
    }
}

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
67
68
69
70
71

快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。

2.1.4 ⚫ 插入排序 https://www.jb51.net/article/110428.htm

如果目标是把n个元素的序列升序排列，那么采用插入排序存在最好情况和最坏情况如下。
最好情况：序列已经是升序排列了，在这种情况下，需要进行的比较操作需(n-1)次即可。
最坏情况：序列是降序排列，那么此时需要进行的比较共有n(n-1)/2次。
直接插入排序属于稳定的排序，最坏时间复杂度为O(n^2)，最好时间复杂度为O(n)，空间复杂度为O(1)。
插入排序的赋值操作是比较操作的次数加上(n-1)次。
因此，插入排序不适合对于数据量比较大的排序应用。

1、从第一个元素开始，该元素可以认为已经被排序。
2、取出下一个元素，在已经排序的元素序列中从后向前扫描。
3、如果该元素（已排序）大于新元素，则将该元素移到下一位置。
4、重复步骤3，直到找到已排序的元素小于或者大于新元素的位置。
5、将新元素插入到该位置。
6、重复步骤2。

public class TestInsertOrder {
    public static void InsertSort(int[] source) {
        int i, j;
        int insertNode;// 要插入的数据
        // 从数组的第二个元素开始循环将数组中的元素插入
        for (i = 1; i < source.length; i++) {
            // 设置数组中的第2个元素为第一次循环要插入的数据
            insertNode = source[i];
            j = i - 1;
            // 如果要插入的元素小于第j个元素，就将第j个元素向后移
            while ((j >= 0) && insertNode < source[j]) {
                source[j + 1] = source[j];
                j--;
            }
            // 直到要插入的元素不小于第j个元素,将insertNote插入到数组中
            source[j + 1] = insertNode;
//            初始关键字：53	27	36	15	69	42
//            第1趟排序：	27	53	36	15	69	42 i=1 j=0 insertNode=27 , 27和53互换
//            第2趟排序：	27	36	53	15	69	42 i=2 j=1 insertNode=53 , 53和36互换
//            第3趟排序：	15	27	36	53	69	42 i=3 j=2 insertNode=15 , 15和27,36,53互换  挪位置
//            第4趟排序：	15	27	36	53	69	42 i=4 j=3 insertNode=69 , 69是左边里面最大的，不动
//            第5趟排序：	15	27	36	42	53	69 i=5 j=4 insertNode=42 , 42和53,69互换  挪位置
        }
    }
    public static void main(String[] args) {
        int source[] = new int[] { 53, 27, 36, 15, 69, 42 };
        InsertSort(source);
        for (int i = 0; i < source.length; i++) {
            System.out.print(source[i]+"\t");
        }
    }
}
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

数组搜索相关的技术（之后再细看吧）
⚫ 二分搜索
⚫ 分块查找
⚫ 哈希表查找
⚫ …