排序算法

啊哈！算法！这本书的笔记！！

桶排序

小哼的班上只有 5 个同学，这 5 个同学分别考了 5 分、3 分、
5 分、2 分和 8 分，哎考得真是惨不忍睹（满分是 10 分）。接下来将分数进行从大到小排序，
排序后是 8 5 5 3 2。
思路分析：
桶排序，确定他的内存大小，这里面最大的是10个，我们的数组大小就是8个。用下标记录数字 重复 +1，打印数组里面非0的数字的下标。
分析一下：int num [] = int [11]
sc 循环5次
记录输入的数字 与 num下标去比较 == 内容+1
打印非0的num下标

import java.util.Scanner;

public class Tong {
    public static void main(String[] args) {
        int [] nums = new int [11];
        Scanner scanner = new Scanner(System.in);
        int i1 = scanner.nextInt();
        int i2 = scanner.nextInt();
        int i3 = scanner.nextInt();
        int i4 = scanner.nextInt();
        int i5 = scanner.nextInt();


        for (int i = 0; i < nums.length; i++) {
            if (i1 == i){
                nums[i]++;
            }
            if (i2 == i){
                nums[i]++;
            }
            if (i3 == i){
                nums[i]++;
            }
            if (i4 == i){
                nums[i]++;
            }
            if (i5 == i){
                nums[i]++;
            }
        }

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0 && nums[i] <= 1){
                System.out.print(i + " ");
            }
            if (nums[i] > 1 && nums[i] <= 2){
                System.out.print(i + " ");
                System.out.print(i + " ");
            }
        }


    }
}

ps:注意我们是拿空间去换时间的时间复杂度是O(n)

冒泡排序

上面的桶排序太浪费空间了
核心：互相比较，交换位置
第1次循环[8 5 5 3 2]
5 8 5 3 2
5 5 8 3 2
5 5 3 8 2
5 5 3 2 8
第2次循环
5 5 3 2 8
5 3 5 2 8
5 3 2 5 8
第3次循环
3 5 2 5 8
3 2 5 5 8
第3次循环
2 3 5 5 8

int [] arr = new int[]{8,5,5,3,2};
for(int i = 0;i < 4;i++){
    if(arr[i] > arr[i+1]){
        int temp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temp;
    }
}

for(int i = 0;i < 3;i++){
    if(arr[i] > arr[i+1]){
        int temp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temp;
    }
}

for(int i = 0;i < 2;i++){
    if(arr[i] > arr[i+1]){
        int temp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temp;
    }
}
这里改变的就是 i < 2 的值 4 3 2 用外层循环去控制
就是这里的j 一开始是 4 然后 3 然后 2 停下来
for(int j = 4; j > 0; j--){
    for(int i = 0;i < j;i++){
    if(arr[i] > arr[i+1]){
        int temp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temp;
    }
}
}
nice 这个时候 把死的数字变活的，动外层即可
for(int j = arr.length-1; j > 0; j--){
    for(int i = 0;i < j;i++){
    if(arr[i] > arr[i+1]){
        int temp = arr[i];
        arr[i] = arr[i+1];
        arr[i+1] = temp;
    }
}
}
nice 弄好了

ps：冒泡排序解决了空间的冗余，但是时间复杂度就不太好是On2

快排

用两个指针，头部一个，尾部一个
[6 1 2 7 9 3 4 5 10 8]
在这里找一个基数，一般都是arr0.
我们要坐到的事情就是，基数左边都是小于他的，右边都是大于他的
例如：[3 1 2 5 4 6 9 7 10 8] 这样我们的基数就满足上面的条件。
我们是怎么做到的？
基数是6！以一开始基数的对面那个部开始移动指针，遇见比6小的数就停下来！然后另一个部分的指针开始移动，遇见比6大的数就停下来！[他们两个交换位置]！ 一直到两个指针相遇之后和基数交换位置。[3 1 2 5 4 6 9 7 10 8]