排序算法题型

---

二分查找

二分查找算法，也称折半搜索算法，是一种在有序数组中查找某一特定元素的搜索算法

1. 图示

2. 思路

1. 前提：有已排序数组 A（假设已经做好）
2. 定义左边界 L、右边界 R，确定搜索范围，循环执行二分查找（3、4两步）
3. 获取中间索引 M = Floor((L+R) /2)
4. 中间索引的值 A[M] 与待搜索的值 T 进行比较
   ① A[M] == T 表示找到，返回中间索引
   ② A[M] > T，中间值右侧的其它元素都大于 T，无需比较，中间索引左边去找，M - 1 设置为右边界，重新查找
   ③ A[M] < T，中间值左侧的其它元素都小于 T，无需比较，中间索引右边去找， M + 1 设置为左边界，重新查找
5. 当 L > R 时，表示没有找到，应结束循环
   
   

3. 算法实现

public class BinarySearch {
    public static void main(String[] args) {
        // 数组
        int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50};
        // 待查找元素
        // int target = 48;
        int target = 47;
        int idx = binarySearch(array, target);
        System.out.println(idx);
    }

    // 二分查找, 找到返回元素索引, 找不到返回-1
    private static int binarySearch(int[] array, int target) {
        // 1. 前提：有已排序数组 A
        // 2. 定义左边界 L、右边界 R，确定搜索范围，循环执行二分查找（3、4两步）
        int l = 0, r = array.length - 1, m;
        while (l <= r) {

            // 3. 获取中间索引 M = Floor((L+R) /2)
            m = (l + r ) / 2;;

            // 4. 中间索引的值  A[M] 与待搜索的值 T 进行比较
            if(array[m] == target) {
                // ① A[M] == T 表示找到，返回中间索引
                return m;
            } else if(array[m] > target) {
                // ② A[M] > T，中间值右侧的其它元素都大于 T，无需比较，中间索引左边去找，M - 1 设置为右边界，重新查找
                r = m - 1;
            } else {
                // ③ A[M] < T，中间值左侧的其它元素都小于 T，无需比较，中间索引右边去找， M + 1 设置为左边界，重新查找
                l = m + 1;
            }
        }

        // 5. 当 L > R 时，表示没有找到，应结束循环
        return -1;
    }
}
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

4. 整数溢出问题

public class IntegerOverFlow {
    public static void main(String[] args) {
        int l = 0;
        int r = Integer.MAX_VALUE - 1;
        int m = (r - l) / 2;
        System.out.println(m); // 1073741823

        // 整数溢出
        int ovNum1 = overFlow1(l, r);
        System.out.println(ovNum1); // -536870913

        // 方法一
        int ovNum2 = overFlow2(l, r);
        System.out.println(ovNum2); // 536870911

        // 方法二
        int ovNum3 = overFlow3(l, r);
        System.out.println(ovNum3); // 1073741823
    }

    // 无符号移位运算 整体右移,负号位变成正号位,正常计算
    private static int overFlow3(int l, int r) {
        int m = (l + r) >>> 1;
        return (l + r) >>> 1;
    }

    // 避免超过 int值最大范围 2147483647
    private static int overFlow2(int l, int r) {
        int m = (r - l) / 2;
        l = m + 1;
        // (r + l) / 2 == l/2 + r/2 == l - l/2 + r/2 == l + (r - l) / 2
        return l + (r + l) / 2;
    }

    // 整数溢出
    private static int overFlow1(int l, int r) {
        int m = (r - l) / 2;
         l = m + 1;
         return (l + r) / 2;
         // 根据二进制,超过返回 int值最大范围 2147483647 时, 第一位是0, 即是负数
    }
}

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

5. 选择题

奇数二分取中间，偶数二分取中间靠左

1. 有一个有序表为 1,5,8,11,19,22,31,35,40,45,48,49,50 当二分查找值为 48 的结点时，查找成功需要比较的次数
答案：4

2. 使用二分法在序列 1,4,6,7,15,33,39,50,64,78,75,81,89,96 中查找元素 81 时，需要经过（ ）次比较
答案：4

$$n=lo{g}_{2}N=lo{g}_{10}N/lo{g}_{10}2$$
$a^x=N、x=lo{g}_{a}N$
其中 n 为查找次数，N 为元素个数

• 是整数，则该整数即为最终结果
• 是小数，则舍去小数部分，整数加一为最终结果

3. 在拥有128个元素的数组中二分查找一个数，需要比较的次数最多不超过多少次
答案：7

冒泡排序

冒泡排序的思想就是在每次遍历一遍未排序的数列之后，将一个数据元素浮上去（也就是排好了一个数据）

1. 图示

2. 思路

1. 循环数组
2. 依次比较相邻两个元素大小，若 左边元素 大于 右边元素，则交换两个元素（结果是让最大的元素排至最后）
3. 每经过一轮冒泡，内层循环就可以减少一次（最后一位元素/最大的元素）
4. 重复以上步骤，直到整个数组有序
5. 如果某一轮冒泡没有发生交换，则表示所有数据有序，可以结束外层循环

优化： 每轮冒泡时，最后一次交换索引可以作为下一轮冒泡的比较次数，如果这个值为零，表示整个数组有序，直接退出外层循环即可

3. 算法实现

public class BubbleSort {
    public static void main(String[] args) {
        int[] array = {3, 2, 8, 1, 9, 5, 7, 4, 6};

        // 1. 循环数组
        for (int i = 0; i < array.length - 1; i++) {
            // 判断循环是否发生了交换
            Boolean swapped = false;

            // 2. 对比相邻元素(每循环一次,减少最后一位元素的循环)
            for (int j = 0; j < array.length - 1 - i; j++) {

                // 3. 如果左侧元素大于右边元素,换位
                if(array[j] > array[j + 1]) {
                    int lim = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = lim;
                    swapped = true;
                }
            }
            System.out.println("第" + i + "轮冒泡: " + Arrays.toString(array));

            // 如果没发生交换,直接终止
            if(!swapped) break;
        }

        System.out.println("----");

        // 优化后
        int[] array2 = {3, 2, 8, 1, 9, 5, 7, 4, 6};
        while (true) {
            int n = array2.length - 1;
            int last = 0; // 最后一次交换的索引位置
            for (int i = 0; i < n; i++) {
                if (array2[i] > array2[i + 1]) {
                    int lim = array2[i];
                    array2[i] = array2[i + 1];
                    array2[i + 1] = lim;
                    last = i;
                }
            }
            System.out.println("冒泡排序: " + Arrays.toString(array2));
            n = last;
            if(n == 0) break;
        }
    }
}
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

选择排序

首先在未排序的数列中找到最小(or最大)元素，然后将其存放到数列的起始位置，然后再从剩余未排序的元素中继续寻找最小(or最大)元素，然后放到已排序序列的末尾，以此类推，直到所有元素均排序完毕

1. 图示

2. 思路

1. 将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放入排序子集
2. 重复以上步骤，直到整个数组有序

优化点： 为减少交换次数，每一轮可以先找最小的索引，在每轮最后再交换元素

3. 算法实现

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

        // 1. 循环数组
        for (int i = 0; i < arr.length - 1; i++) {
            // i 代表每轮选择的最小元素交换到的目标索引
            int s = i; // 代表最小元素的索引

            // 2. 循环数组的元素(每次循环过滤掉首位已排序的元素)
            for (int j = s + 1; j < arr.length; j++) {

                // 3. 如果 选择元素 大于 目标元素,则交换索引值
                if(arr[s] > arr[j]) {
                    s = j;
                }
            }

            // 4. 循环后,如果最小元素的索引值发生变化,则调换两个元素位置
            if(s != i) {
                int lim = arr[s];
                arr[s] = arr[i];
                arr[i] = lim;
            }
            System.out.println(Arrays.toString(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
27
28
29

4. 与冒泡排序比较

• 二者平均时间复杂度都是 $O(n^2)$
• 选择排序一般要快于冒泡，因为其交换次数少
• 但如果集合有序度高，冒泡优于选择
• 冒泡属于稳定排序算法，而选择属于不稳定排序
  • 稳定排序指，按对象中不同字段进行多次排序，不会打乱同值元素的顺序
  • 不稳定排序则反之

不稳定排序示例：

扑克牌先按照花色排序（♠♥♣♦），再按照数字排序（AKQJ…）

• 不稳定排序算法按数字排序时，会打乱原本同值的花色顺序

  [[♠7], [♠2], [♠4], [♠5], [♥2], [♥5]]
  [[♠7], [♠5], [♥5], [♠4], [♥2], [♠2]]
  1
  2

• 稳定排序算法按数字排序时，会保留原本同值的花色顺序，如下所示 ♠2 与 ♥2 的相对位置不变

  [[♠7], [♠2], [♠4], [♠5], [♥2], [♥5]]
  [[♠7], [♠5], [♥5], [♠4], [♠2], [♥2]]
  1
  2

  
  

插入排序

将数据按照一定的顺序一个一个的插入到有序的表中，最终得到的序列就是已经排序好的数据

1. 图示

2. 思路

1. 将数组分为两个区域，排序区域和未排序区域，每一轮从未排序区域中取出第一个元素，插入到排序区域（需保证顺序）
2. 重复以上步骤，直到整个数组有序

优化： 插入时可以直接移动元素，而不是交换元素

3. 算法实现

public class InsertSort {
    // 插入排序
    public static void main(String[] args) {
        int[] arr = {3, 2, 8, 1, 9, 5, 7, 4, 6};

        // 1. 循环数组
        for (int i = 1; i < arr.length; i++) {
            int lim = arr[i]; // 待插入元素的值
            int j = i - 1; // 已排序区域索引

            // 2. 循环未排序的数组
            while (j >= 0) {

                // 3. 相邻元素比较,如果右边元素小于左边,则交换位置
                if(lim < arr[j]) {
                    arr[j + 1] = arr[j];
                } else {
                    break;
                }
                j--;
            }

            // 4. 将元素插入排序区域
            arr[j + 1] = lim;
            System.out.println("插入排序" + Arrays.toString(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
27
28

4. 与选择排序比较

1. 二者平均时间复杂度都是 $O(n^2)$
2. 大部分情况下，插入都略优于选择
3. 有序集合插入的时间复杂度为 $O(n)$
4. 插入属于稳定排序算法，而选择属于不稳定排序

插入排序通常被同学们所轻视，其实它的地位非常重要。小数据量排序，都会优先选择插入排序

5. 选择题

1. 使用直接插入排序算法对序列 18, 23, 19, 9, 23, 15 进行排序, 第 3 趟排序后的结果为_____
   9, 18, 19, 23, 23,15
2. 使用直接选择排序算法对序列 18, 23, 19, 9, 23, 15 进行排序, 第 3 趟排序后的结果为____
   9, 15, 18, 23, 19, 23

希尔排序

1. 思路

1. 首先选取一个间隙序列，如 (n/2，n/4 … 1)，n 为数组长度
2. 每一轮将间隙相等的元素视为一组，对组内元素进行插入排序，目的有二
   ①. 少量元素插入排序速度很快
   ②. 让组内值较大的元素更快地移动到后方
3. 当间隙逐渐减少，直至为 1 时，即可完成排序
   
   

2. 算法实现

private static void shell(int[] a) {
    int n = a.length;
    for (int gap = n / 2; gap > 0; gap /= 2) {
        // i 代表待插入元素的索引
        for (int i = gap; i < n; i++) {
            int t = a[i]; // 代表待插入的元素值
            int j = i;
            while (j >= gap) {
                // 每次与上一个间隙为 gap 的元素进行插入排序
                if (t < a[j - gap]) { // j-gap 是上一个元素索引，如果 > t，后移
                    a[j] = a[j - gap];
                    j -= gap;
                } else { // 如果 j-1 已经 <= t, 则 j 就是插入位置
                    break;
                }
            }
            a[j] = t;
            System.out.println(Arrays.toString(a) + " gap:" + gap);
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

快速排序

1. 图示

2. 单边循环快排（lomuto 洛穆托分区方案）

⑴. 思路

1. 选择最右元素作为基准点元素
2. j 指针负责找到比基准点小的元素，一旦找到则与 i 进行交换
3. i 指针维护小于基准点元素的边界，也是每次交换的目标索引
4. 最后基准点与 i 交换，i 即为分区位置
   
   

⑵. 编码实现

public class QuickSort {
    // 快速排序 - 单边循环法
    public static void main(String[] args) {
        int[] arr = {5, 3, 7, 2, 9, 8, 1, 4};
        partition(arr, 0, arr.length - 1);
        quick(arr, 0, arr.length - 1);
    }

    // 递归
    public static void quick(int[] arr, int l, int h) {
        if(l >= h) return;
        int p = partition(arr, l, h); // p 为索引值
        quick(arr, l, p - 1); // 左边分区的范围确定
        quick(arr, p + 1, h); // 右边分区的范围确定
    }

    private static int partition(int[] arr, int l, int h) {
        int i = l; // 基准点索引

        // 1. 循环数组
        for (int j = l; j < h; j++) {

            // 2. 循环判断元素 是否小于 索引点元素, 如果小于, 交换元素位置
            if(arr[j] < arr[h]) {
                if(i != j) {
                    int lim = arr[i];
                    arr[i] = arr[j];
                    arr[j] = lim;
                }
                i++;
            }
        }

        // 3. 循环后, 将索引元素 和 基准点元素 交换位置
        if(h != i) {
            int pvValue = arr[h];
            arr[h] = arr[i];
            arr[i] = pvValue;
        }
        System.out.println(Arrays.toString(arr) + "i = " + i);

        // 4. 返回基准点元素所在的索引，确定下一轮分区的边界
        return 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
42
43
44
45

3. 双边循环快排（不完全等价于 hoare 霍尔分区方案）

⑴. 思路

1. 选择最左元素作为基准点元素
2. j 指针负责从右向左找比基准点小的元素，i 指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至 i，j 相交
3. 最后基准点与 i（此时 i 与 j 相等）交换，i 即为分区位置

注意：

• 基准点在左边，并且要先 j 后 i
• while( i < j && a[j] > pv ) j–
• while ( i < j && a[i] <= pv ) i++

⑵. 编码实现

public class QuickSort2 {
    // 快速排序 - 双边循环法
    public static void main(String[] args) {
        int[] arr = {5, 3, 7, 2, 9, 8, 1, 4};
        partition(arr, 0, arr.length - 1);
        quick(arr, 0, arr.length - 1);
    }

    private static int quick(int[] arr, int l, int h) {
        return 0;
    }

    private static int partition(int[] arr, int l, int h) {
        // 1. 选择最左边元素为基准点元素
        int i = l; // 左边索引
        int j = h; // 右边索引

        // 2. 双边循环, 直至i、j指针重叠
        while (i < j) {

            // 3. j 指针负责由右向左找比基准点小的元素
            while (i < j && arr[j] > arr[l]) j--;

            // 4. i 指针负责由左向右找比基准点大的元素
                // 4.1 <= 的目的是 避免和基准点元素交换
                // 4.2 i < j 的目的是 内存循环遇到 i指针 j指针 重叠时终止
            while (i < j && arr[i] <= arr[l]) i++;

            // 5. 一旦找到, 二者交换位置
            int lim = arr[i];
            arr[i] = arr[j];
            arr[j] = lim;
        }

        // 6. 将分区索引元素 和 基准点元素 交换位置
        int lim = arr[l];
        arr[l] = arr[j];
        arr[j] = lim;
        System.out.println(Arrays.toString(arr) + "j =" + j);

        // 7. 返回基准点元素所在的索引，确定下一轮分区的边界
        return 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

4. 特点

1. 平均时间复杂度是 $O(nlo{g}_{2}n)$，最坏时间复杂度 $O(n^2)$
2. 数据量较大时，优势非常明显
3. 属于不稳定排序

双边循环移动次数平均来讲比单边循环少3倍