【JAVA入门】Day24 - 排序算法

【JAVA入门】Day24 - 排序算法

---

---

        排序，是把混乱的数据排成从小到大或从大到小。
        排序一共有十种左右，它们是：冒泡排序、选择排序、插入排序、快速排序、希尔排序、归并排序、堆排序、计数排序、桶排序、基数排序。
        在这里，我们着重介绍前四种。

一、冒泡排序

        冒泡排序：相邻的数据两两比较，小的放前面，大的放后面。
        每经过一轮的两两比较，最大的数据一定会被放在最右边。此时只需要对除它之外的剩余元素继续做相同操作即可。第二轮可以比第一轮少循环一次，以此类推。
        如果数组中有 n 个数据，我们总共只需要执行 n-1 轮的代码就可以了。

package SortTest;

public class SortDemo1 {
    public static void main(String[] args) {
        //BubbleDemo

        //1.定义数组
        int[] arr = {2, 4, 5, 3, 1};

        //2.利用冒泡排序将数组中的数据变成 1 2 3 4 5
        //注意循环的截止要减一，防止越界
        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]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        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
19
20
21
22
23
24
25
26

二、选择排序

        选择排序：从0索引开始，拿着每一个索引上的元素，跟后面的元素依次比较，小的放前面，大的放后面，依此类推。
        每一轮循环结束后，最小的数据一定是跑到了左边，那么后面的下一轮循环就可以少循环一次。

package SortTest;

public class SortDemo2 {
    public static void main(String[] args) {
        //SelectionSort

        //1.定义数组
        int[] arr = {2, 4, 5, 3, 1};

        //2.利用选择排序让数组变成正序
        //从0索引开始，跟后面的元素一一比较
        for(int i = 0; i < arr.length - 1; i++) {
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[i] > arr[j]) {
                    int temp = arr[i];
                    arr[i] = arr[j];
                    arr[j] = temp;
                }
            }
        }
        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
19
20
21
22
23
24
25

三、插入排序

        插入排序：我们将0索引的元素到N索引的元素看作是有序的，把N+1开始的索引的元素到最后一个元素当成是无序的。遍历无序的元素，我们将遍历到的元素插入到有序序列中适当的位置，若遇到相同数据了，插在后面。N的取值范围：0~最大索引。
        每次插入时，我们是从后往前插，分别跟当前索引的数据比大小，比它小，往前继续走，直到找到比当前索引大的情况，插在后面。

package SortTest;

public class SortDemo3 {
    public static void main(String[] args) {
        //插入排序：我们将0索引的元素到N索引的元素看作是有序的，把N+1开始的索引的元素到最后一个元素当成是无序的。遍历无序的元素，我们将遍历到的元素插入到有序序列中适当的位置，若遇到相同数据了，插在后面。N的取值范围：0~最大索引。

        int[] arr = {3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48};

        //1.找到无序的哪一组数组是从哪个数组开始的
        int startIndex = -1;
        for(int i = 0; i < arr.length - 1; i++) {
            if(arr[i] > arr[i + 1]) {
                //System.out.println(i); //有序的那一组数据到i索引就结束了，再加一就是无序数据的第一个索引
                startIndex = i + 1;
                break;
            }
        }

        //2.遍历从startIndex开始到最后一个元素，得到无序的每一个元素
        for (int i = startIndex; i < arr.length; i++) {
            //问题：如何把遍历到的数据插入到前面有序的这一组当中

            //记录当前要插入数据的索引
            int j = i;

            //将每一个无序数据向左遍历，直到找到比它小的档口，插入
            while(j > 0 && arr[j] < arr[j - 1]) {
                int temp = arr[j];
                arr[j] = arr[j - 1];
                arr[j - 1] = temp;
                j--;
            }
        }

        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
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

四、快速排序

4.1 递归

        递归指的是方法中调用方法本身的现象。
        递归一定要有出口，否则就会出现内存溢出。
        递归算法可以把一个复杂的问题层层转化为一个与原问题相似的规模较小的问题来求解。
【练习1】利用递归求1~100之间的和。

package SortTest;

public class RecursionDemo {
    public static void main(String[] args) {
        //求1~100的和
        //1~100的和 = 100 + （1~99的和）
        //1~99的和 = 99 + （1~98的和）
        //...
        //1~2的和 = 2 + （1~1的和）
        //1~1的和 = 1 （递归的出口）
        System.out.println(getSum(100));
    }
    public static int getSum(int number){
        if(number == 1) {
            return 1;
        }
        return number + getSum(number - 1);
    }

}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

【练习2】用递归求5！。
5！ = 5 * 4 * 3 * 2 * 1

package SortTest;

public class RecursionDemo1 {
    public static void main(String[] args) {
        //5! = 5 * 4!
        //4! = 4 * 3!
        //3! = 3 * 2!
        //2! = 2 * 1!
        //1! = 1

        System.out.println(getFactorialRecursion(5));

    }

    public static int getFactorialRecursion(int number) {
        if(number == 1) {
            return 1;
        }

        return number * getFactorialRecursion(number - 1);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

4.2 快速排序

        第一轮：把0索引的数字作为基准数，确定基准数在数组中正确的位置。比基准数小的全部在左边，比基准数大的全部在右边。


        找到 start 和 end 的位置后，交换两个位置上的数据。

        直到 start 和 end 指向同一个位置时，这个位置就是基准数要存入的位置（基准数归位）。

        此时就需要把基准数和它们指向的位置交换。

        此时，6 左侧的数据都比 6 小，6 右侧的数据都比 6 大。

package SortTest;

public class SortDemo4 {
    public static void main(String[] args) {
        //QuickSort
        int[] arr = {6, 1, 2, 7, 9, 3, 4, 5, 10, 8};

        quickSort(arr, 0, arr.length - 1);

        for (int i = 0; i < arr.length; i++) {
            System.out.print(arr[i] + " ");
        }

    }

    /*
    参数一：要排序数组的起始数组
    参数二：要排序数组的起始索引
    参数三：要排序数组的结束索引
     */
    public static void quickSort(int[] arr, int i , int j) {
        //定义两个变量记录要查找的范围
        int start = i;
        int end = j;

        //递归出口
        //start > end
        if(start > end) {
            return;
        }

        //记录基准数
        int baseNumber = arr[i];

        //利用循环找到要交换的数字
        while(start != end) {
            //利用end，从后往前开始找，找比基准数小的数字
            while(true) {
                if(end <= start || arr[end] < baseNumber) {
                    break;
                }
                end--;
            }

            //利用start，从前往后找，找比基准数大的数字
            while(true) {
                if(end <= start || arr[start] > baseNumber) {
                    break;
                }
                start++;
            }

            //把end和start指向的元素进行交换
            int temp = arr[start];
            arr[start] = arr[end];
            arr[end] = temp;

            //直到start == end，循环结束
        }
        //表示已经找到了基准数在数组中应该存入的位置
        //基准数归位
        int temp = arr[i];
        arr[i] = arr[start];
        arr[start] = temp;

        //确定基准数左边的范围，重复刚刚所有的事情
        quickSort(arr, i, start - 1);
        //确定基准数右边的范围，重复刚刚所有的事情
        quickSort(arr, end + 1, j);

    }
}

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
72
73

        在所有排序算法中，快速排序的速度是最快的，被广泛使用。