排序算法¶

二分查找¶

①编写二分查找代码¶

1．前提:有已排序数组A（假设已经做好)¶

2．定义左边界L、右边界R，确定搜索范围，循环执行二分查找（3、4两步)¶

3．获取中间索M=Floor((L+R)/2)¶

4．中间索引的值A[M]与待搜索的值Ⅰ进行比较¶

A[M]==T 表示找到，返回中间索引 A[M]>T，中间值右侧的其它元素都大于T，无需比较，中间索引左边去找，M-1设置为右边界,重新查找 A[MN]<T，中间值左侧的其它元素都小于T，无需比较，中间索引右边去找，M＋1设置为左边界,重新查找

5.当L>R时，表示没有找到，应结束循环¶

②代码¶

public class BinarySearch {
    public static void main(String[] args) {
        int[] array = {1, 5, 8, 11, 19, 22, 31, 35, 40, 45, 48, 49, 50, 59, 65, 77, 89, 95};
        int target = 77;
        int idx = binarySearch2(array, target);
        // 10
        System.out.println(idx);
    }

    /**
     * 二分查找
     */
    private static int binarySearch(int[] a, int target) {
        int l = 0, r = a.length - 1, m;
        while (l <= r) {
            m = (l + r) / 2;
            if (a[m] == target) {
                return m;
            } else if (a[m] > target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }

    /**
     * 可以解决整数溢出
     */
    private static int binarySearch1(int[] a, int target) {
        int l = 0, r = a.length - 1, m;
        while (l <= r) {
            m = l + (r - l) / 2;
            if (a[m] == target) {
                return m;
            } else if (a[m] > target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }

    /**
     * 可以解决整数溢出,且更快
     */
    private static int binarySearch2(int[] a, int target) {
        int l = 0, r = a.length - 1, m;
        while (l <= r) {
            m = (l + r) >>> 1;
            if (a[m] == target) {
                return m;
            } else if (a[m] > target) {
                r = m - 1;
            } else {
                l = m + 1;
            }
        }
        return -1;
    }
}

总的来说就是：奇数二分取中间；偶数二分取中间靠左¶

\[ 排序次数 = log_2元素个数 \]

是整数，则该整数为最终结果
是小数，则则舍去小数部分，整数结果加1为做种结果

可以参考JDK中 Arrays.binarySearch(array, target); 的实现方法

冒泡排序¶

①思路¶

一.何为冒泡排序-效果演示

二.文字描述（以升序为例)

依次比较数组中相邻两个元素大小，若 a[i]>a[i+1]，则交换两个元素，两两都比较一遍称为一轮冒泡，结果是让最大的元素排至最后

重复以上步骤，直到整个数组有序

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

②代码¶

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

    private static void bubble(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            boolean isSwapped = false;
            // 一轮冒泡
            for (int j = 0; j < array.length - 1 - i; j++) {
                if (array[j] > array[j + 1]) {
                    swap(array, j, j + 1);
                    isSwapped = true;
                }
                System.out.println("此轮比较次数：" + (j + 1));
            }
            System.out.println("第" + (i + 1) + "轮冒泡" + Arrays.toString(array));
            //数组已经有序了，则退出循环
            if (!isSwapped) {
                break;
            }
        }
    }

    /**
     * 优化
     */
    private static void bubble2(int[] array) {
        int count = array.length - 1;
        while (true) {
            //表示最后一次交换的索引位置
            int last = 0;
            for (int i = 0; i < count; i++) {
                System.out.println("此轮比较次数：" + (i + 1));
                if (array[i] > array[i + 1]) {
                    swap(array, i, i + 1);
                    last = i;
                }
            }
            //无需比较后面已经排完序的元素
            count = last;
            System.out.println("第" + count + "轮冒泡" + Arrays.toString(array));
            if (count == 0) {
                break;
            }
        }
    }

    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

选择排序¶

①思路¶

一.何为选择排序―效果演示

二.文字描述（以升序为例)

将数组分为两个子集，排序的和未排序的，每一轮从未排序的子集中选出最小的元素，放入排序子集

重复以上步骤，直到整个数组有序

三.优化方式

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

四.与冒泡排序比较

二者平均时间复杂度都是O(n^2)

选择排序一般要快于冒泡，因为其交换次数少

但如果集合有序度高，冒泡优于选择

冒泡属于稳定排序算法，而选择属于不稳定排序

②代码¶

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

    private static void selection(int[] array) {
        //i表示每轮选择，最小元素要交换到的目标索引
        for (int i = 0; i < array.length - 1; i++) {
            //最小元素的索引值
            int s = i;
            for (int j = s + 1; j < array.length; j++) {
                if (array[s] > array[j]) {
                    s = j;
                }
            }
            if (s != i) {
                swap(array, s, i);
            }
            System.out.println(Arrays.toString(array));
        }
    }

    public static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

插入排序¶

①思路¶

一.何为插入排序–效果演示

二．文字描述（以升序为例)

将数组分为两个区域，排序区域和未排序区域，每一轮从未排序区域中取出第一个元素，插入到排序区域（需保证顺序)

重复以上步骤，直到整个数组有序

三.优化方式

待插入元素进行比较时，遇到比自己小的元素，就代表找到了插入位置，无需进行后续比较

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

四.与选择排序比较

1.二者平均时间复杂度都是O(n2)

2．大部分情况下，插入都略优于选择

3．有序集合插入的时间复杂度为O(n)

4．插入属于稳定排序算法，而选择属于不稳定排序

缺点:有很多的较大元素处于比较前面的位置时，需要多次移动元素(希尔排序是对这种情况的优化)

希尔排序可以理解为指定间隙的序列中进行插入排序

②代码¶

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

    private static void insert(int[] array) {
        //i表示待插入元素的索引
        for (int i = 1; i < array.length; i++) {
            //待插入的元素值
            int temp = array[i];
            //已排序区域的元素索引
            int j = i - 1;
            while (j >= 0) {
                if (temp < array[j]) {
                    //交换位置
                    array[j + 1] = array[j];
                } else {
                    //退出循环减少比较次数
                    break;
                }
                j--;
            }
            //插入元素
            array[j + 1] = temp;
            System.out.println(Arrays.toString(array));
        }
    }
}

快速排序¶

一、描述¶

1.每一轮排序选择一个基准点(pivot)进行分区¶

让小于基准点的元素的进入一个分区，大于基准点的元素的进入另一个分区
当分区完成时，基准点元素的位置就是其最终位置

2.在子分区内重复以上过程，直至子分区元素个数少于等于1，这体现的是分而治之的思想(divide-and-conquer)¶

二、实现方式¶

1.单边循环快排(lomuto洛穆托分区方案)¶

①选择最右元素作为基准点元素

②j指针负责找到比基准点小的元素，一旦找到则与i进行交换

③i指针维护小于基准点元素的边界，也是每次交换的目标索引

④最后基准点与i交换，i即为分区位置

public class QuickSortOneSide {
    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
        quick(a, 0, a.length - 1);
    }

    private static void quick(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(a, l, h);
        //确定左边分区范围
        quick(a, l, p - 1);
        //确定右边分区范围
        quick(a, p + 1, h);
    }

    /**
     * 单边循环
     *
     * @return int 返回值表示基准点元素所在的正确索引
     */
    private static int partition(int[] a, int l, int h) {
        //基准点元素
        int pivot = a[h];
        //带交换元素的目标索引
        int i = l;
        for (int j = l; j < h; j++) {
            //比较元素大小
            if (a[j] < pivot) {
                if (i != j) {
                    swap(a, i, j);
                }
                i++;
            }
        }
        //不是同一个元素时交换才有意义
        if (i != h) {
            //基准点元素与带交换元素交换
            swap(a, h, i);
        }
        System.out.println(Arrays.toString(a) + "| i: " + i);
        return i;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

2.双边循环快排(并不完全等价于hoare霍尔分区方案)¶

①选择最左元素作为基准点元素

②j指针负责从右向左找比基准点小的元素，i指针负责从左向右找比基准点大的元素，一旦找到二者交换，直至i，j相交

③最后基准点与i(此时i与j相等）交换，i即为分区位置

public class QuickSortTwoSide {
    public static void main(String[] args) {
        int[] a = {5, 3, 7, 2, 9, 8, 1, 4};
        quick(a, 0, a.length - 1);
    }

    private static void quick(int[] a, int l, int h) {
        if (l >= h) {
            return;
        }
        int p = partition(a, l, h);
        //确定左边分区范围
        quick(a, l, p - 1);
        //确定右边分区范围
        quick(a, p + 1, h);
    }

    /**
     * 双边循环
     *
     * @return int 返回值表示基准点元素所在的正确索引
     */
    private static int partition(int[] a, int l, int h) {
        //基准点
        int pivot = a[l];
        int i = l;
        int j = h;
        while (i < j) {
            // j 从右找小的
            // i < j  防止多一次交换
            while (i < j && a[j] > pivot) {
                j--;
            }
            // i 从左找大的
            // 加=为了避免基准点元素被错误交换
            while (i < j && a[i] <= pivot) {
                i++;
            }
            swap(a, i, j);
        }
        swap(a, l, j);
        System.out.println(Arrays.toString(a) + "| j: " + j);
        return i;
    }

    private static void swap(int[] a, int i, int j) {
        int t = a[i];
        a[i] = a[j];
        a[j] = t;
    }
}

3.双边循环的几个要点¶

①.基准点在左边，并且要先j后i

②.while (i < j && a[j] > pivot) {j--;}

③.while (i < j && a[i] <= pivot) {i++;}

参考:

1.快速排序两种方案: https://qastack.cn/cs/11458/quicksort-partitioning-hoare-vs-lomuto

2.维基百科排序算法: https://en.wikipedia.org/wiki/Sorting_algorithm

排序算法¶

二分查找¶

①编写二分查找代码¶

1．前提:有已排序数组A（假设已经做好)¶

2．定义左边界L、右边界R，确定搜索范围，循环执行二分查找（3、4两步)¶

3．获取中间索M=Floor((L+R)/2)¶

4．中间索引的值A[M]与待搜索的值Ⅰ进行比较¶

5.当L>R时，表示没有找到，应结束循环¶

②代码¶

总的来说就是： 奇数二分取中间；偶数二分取中间靠左¶

冒泡排序¶

①思路¶

②代码¶

选择排序¶

①思路¶

②代码¶

插入排序¶

①思路¶

②代码¶

快速排序¶

一、描述¶

1.每一轮排序选择一个基准点(pivot)进行分区¶

2.在子分区内重复以上过程，直至子分区元素个数少于等于1，这体现的是分而治之的思想(divide-and-conquer)¶

二、实现方式¶

1.单边循环快排(lomuto洛穆托分区方案)¶

2.双边循环快排(并不完全等价于hoare霍尔分区方案)¶

3.双边循环的几个要点¶

总的来说就是：奇数二分取中间；偶数二分取中间靠左¶