强化历程7-排序算法(2023.9.12)

• 此笔记学习图片来自于如下网址

¹https://www.west999.com/info/html/chengxusheji/Javajishu/20190217/4612849.html

强化历程7-排序算法

1 冒泡排序(交换排序)

思想:每轮排序，相邻两个元素比较，如果后面元素小于前面元素，则位置颠倒；

• 每轮可以确定一个最大值，下轮比较只需比较剩下的n-1个元素，排序结束后，退出循环。

    static int[] maopao(int[] arr) {
        int temp = 0;//交换位
        boolean flag = false;//标志位，记录有无交换
        //外层遍历控制遍历轮数
        for (int i = 0; i < arr.length - 1; i++) {
            flag = false; // 每轮排序开始时，将标志位重置为false
            //内层进行交换，并且下轮比较只需比较剩下的n-1个元素
            for (int j = 0; j < arr.length - i - 1; j++) {
                if (arr[j] > arr[j + 1]) {//如果前面比后面大，交换位置
                    flag = true;
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            if (!flag){//如果没交换
                break;
            }
            System.out.print("第" + i + "轮交换结果为：");
            for (int k : arr) {
                System.out.print(k + " ");
            }
            System.out.println("");
        }
        return arr;
    }
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

• 时间复杂度：O(N^2)，在冒泡排序中，每个元素需要和其他元素进行比较，因此总共需要进行 N^2 次比较操作。
• 空间复杂度：O(1) ，在冒泡排序中，只需要使用一个临时变量进行数值交换，因此空间复杂度为 O(1)。

2 选择排序

思想：每轮对未排序元素选择一个最小(或最大的)的标记，放到未排序元素的最左边(或最右边)

       static int[] xuanze(int[] arr) {
        int temp; //交换位
        for (int i =0;i< arr.length-1;i++){
            int minIndex = i;//最小值下标
            //遍历未排序部分并最小的值
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            // 将找到的最小值与未排序部分的第一个元素交换位置
            temp = arr[minIndex];
            arr[minIndex] = arr[i];
            arr[i] = temp;
        }
        return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

改进思路：每轮找到未排序元素的最大值和最小值，将他们放到未排序元素两端

• 时间复杂度：O(N^2)

• 空间复杂度：O(1)

3 直接插入排序

思想:通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

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

    static int[] charu(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //取出当前元素
            int currentNum = arr[i];
            int j = i - 1;  //定位当前元素
            //对于当前元素，让其从后往前扫描，找出正确位置
            while (j >= 0 && arr[j] > currentNum) {
                //比当前元素大的后移一位
                arr[j + 1] = arr[j];
                j--;
            }
            arr[j+1] = currentNum; //将当前元素插入合适位置
        }
        return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 时间复杂度

  • 最坏情况：每次插入每个元素都要挪动一次：O(N^2)
  • 最好情况：O(N)

  越接近顺序时间复杂度越低，元素越少效率越高，因为交换少，因此Arrays.sort()底层length<47为插入排序

• 空间复杂度：O(1)

4 希尔排序

思想：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，然后依次缩减增量(gap)再进行排序，直到增量为1时，进行最后一次直接插入排序。

• 相当与改进的直接插入排序，只不过原来间隔为1，改为现在的gap了，减少比较和移动的次数，从而提高排序效率。

     static int[] xier(int[] arr) {
        //将元素分组
        //增量gap设置为n/2，这意味着我们将数组分成多个子序列，每个子序列包含相隔一个增量的元素。
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            //对分组进行插入排序
            for (int i = gap;i<arr.length;i++){
                int currentNum = arr[i];//当前元素
                int j =i; 
                while (j>=gap&&arr[j-gap]>currentNum){
                    // 将比当前元素大的元素向右移动一个增量
                    arr[j] = arr[j - gap];
                    j -= gap;
                }
                // 将当前元素插入到正确的位置
                arr[j] = currentNum;
            }
        }
        return arr;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

• 时间复杂度：O(NlogN)
• 空间复杂度：O(1)

5 归并排序

思想：归并排序的思想是将待排序序列分成若干个子序列，每个子序列都是有序的。然后，将这些有序的子序列合并成一个整体有序的序列。

• 思路: 不停递归分解数组，当分解到自己则退出

  然后开始合并排序

public class guibing {
    static void guibingGroup(int[] arr, int left, int right) {
        //递归，相遇时退出，也就是分解遇到自己
        if (left >= right) {
            return;
        }
        //获取中间元素
        int mid = (left + right)/2;
        guibingGroup(arr, left, mid); //左边序列
        guibingGroup(arr, mid + 1, right);//右边序列
        //合并
        guibingheBing(arr, left, mid, right);
    }
    private static void guibingheBing(int[] arr, int left, int mid, int right) {
        int s1 = left;//归并左边第一个数据
        int s2 = mid + 1;//归并右边第一个数据
        int temp[] = new int[right - left + 1];
        int index = 0;//表示temp数组下标
        while (s1 <= mid && s2 <= right) {//两边都不为空
            //比较s1和s2的值
            if (arr[s1] <= arr[s2]) {
                //放到数组后，下个数字
                temp[index++] = arr[s1++];
            } else {
                temp[index++] = arr[s2++];
            }
        }
        while (s1 <= mid) {
            temp[index++] = arr[s1++];
        }
        while (s2 <= right) {
            temp[index++] = arr[s2++];
        }
        for (int  i=0;i< temp.length;i++){
            //右边元素放到自己的位置
            arr[i+left] = temp[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

• 时间复杂度 Nlog(Nlog_N)
• 空间复杂度O(N)

6 快速排序

思想:从左边(或者右边)找一个基准数。

然后从两边开始检索，( 如果左边为基准数从右开始检索，如果右边为基准数从左边开始检索)，一边检索出比基准数小的，另一边检索比基准数大的。

如果检索到就停下，然后交换这两个元素，然后再继续检索。

这两个元素一旦相遇则停止检索，把基准数和相遇位置的元素交换。(第一轮结束):左边元素都比基准数小，右边元素都比基准数大。。。

    private static void kuaipai(int[] arr, int left, int right) {
        //左边索引大于右边，直接返回
        if (left >= right) {
            return;
        }
        int base = arr[left];//基准数
        int i = left;//指向左边元素
        int j = right;//指向右边元素
        //i和j不相遇
        while (i != j) {
            //先由j从右往左检索比基准数小的，如果检索到比基准数小停止
            while (arr[j] >= base && i < j) {
                j--;
            }
            //先由i从左往右检索比基准数大的，如果检索到比基准数大停止
            while (arr[i] <= base && i < j) {
                i++;
            }
            //找到了对于数组，交换i和j位置的元素
            int temp = arr[i];
            arr[i] = arr[j];
            arr[j] = temp;
        }
        //如果上述条件不成立，i和j相遇
        arr[left] = arr[i];
        arr[i] = base;
        //基准数在这里归位
        //排基准数左面
        kuaipai(arr,left,i-1);
        //排右边
        kuaipai(arr,j+1,right);
    }
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

7 堆排序

• 下标为i的节点的父节点下标: (i- 1)/2

• 下标为i的节点的左孩子下标:i*2+1

• 下标为i的节点的右孩子下标:i*2+2

思想:子节点要小于父节点

    private static void duipai(int[] tree, int current, int length) {
        int left = 2 * current + 1; //左节点索引
        int right = 2 * current + 2;//右节点索引
        int maxIndex = current; //最大节点索引
        // 左节点大于最大值
        if (left < length && tree[left] > tree[maxIndex]) {
            maxIndex = left;
        }
        // 右节点大于最大值
        if (right < length && tree[right] > tree[maxIndex]) {
            maxIndex = right;
        }
        // 如果当前索引和最大索引不相等
        if (current != maxIndex) {
            int temp = tree[current];
            tree[current] = tree[maxIndex];
            tree[maxIndex] = temp;
            duipai(tree,maxIndex,length);
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

将任意树调整为大顶堆

从倒数第一个非叶子结点开始，从后往前，按下标，依次作为根去向下调整即可。

  	//构建大顶堆
    private static void buildMaxHeap(int[] tree){
        int lastNode = tree.length-1;
        int parent = (lastNode-1)/2;
        for (int k= parent;k>=0;k--){
            duipai(tree,k);
        }
    }
1
2
3
4
5
6
7
8

排序

重新构建大顶堆

private static void duiSort(int[] arr){  
    //重新构建大顶堆  
    buildMaxHeap(arr);  
    for (int i=arr.length-1;i>=0;i--){  
        //最大值放到数组最后  
        int temp = arr[0];  
        arr[0] = arr[i];  
        arr[i] = temp;  
        //将最大值砍掉  
        duipai(arr,0,i);  
        // 重新调整堆  
        if (i != 0) {  
            duipai(arr, 0, i);  
        }  
    } 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

8 计数排序

思想:它的基本思想是通过计算各个数值出现的次数，然后根据这些次数重新组织待排序数组，从而实现排序。

   public static void jishu(int[] array) {
            //找出数组中的最大值
            int max = array[0];
            for (int i = 1; i < array.length; i++) {
                if (array[i] > max) {
                    max = array[i];
                }
            }
            //初始化计数数组
            int[] countArray = new int[max + 1];

            //统计每个元素的出现次数
            for (int i = 0; i < array.length; i++) {
                countArray[array[i]]++;
            }
            //重新生成排序后的数组
            int index = 0;
            for (int i = 0; i < countArray.length; i++) {
                while (countArray[i] > 0) {
                    array[index++] = i;
                    countArray[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

---

1. 1 ↩︎