AI 助理
备案控制台
开发者社区 人工智能 文章 正文

排序笔记分享

2022-05-10 101
版权
版权声明：
本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《 阿里云开发者社区用户服务协议》和 《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写 侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。
简介： 这是我学习排序算法时候的笔记记录。

排序视频

01.数组的介绍和定义

02.数组的常见操作

03.二维数据的介绍

04.二维数组的练习之数组元素求和打印杨辉三角

打印杨辉三角

public class ArrayDemo {
    /**
     * 打印杨辉三角
     * 1
     * 1    1
     * 1    2    1
     * 1    3    3    1
     * 1    4    6    4    1
     * 1    5    10    10    5    1
     * <p>
     * 规律：
     * 1. 每一行的第一列和最后一列都是1
     * 2. 从三行开始，每一行的其他列（除了一行和最后一行）=上一行的同一列+上一行的同一列的前一个
     *
     * @param args
     */
    public static void main(String[] args) {
        //输入行
        System.out.print("请输入行数：");
        Scanner scanner = new Scanner(System.in);
        int row = scanner.nextInt();

        //定义一个二维数组
        int[][] ints = new int[row][row];
        //每一行的第一列和最后一列都是1
        ints[0][0] = 1;
        for (int i = 1; i < ints.length; i++) {
            ints[i][0] = 1;
            ints[i][i] = 1;
            //从三行开始，每一行的其他列（除了一行和最后一行）=上一行的同一列+上一行的同一列的前一个
            if (i > 1) {
                for (int j = 1; j < ints[i].length - 1; j++) {
                    ints[i][j] = ints[i - 1][j] + ints[i - 1][j - 1];
                }
            }
        }

        //打印数组
        for (int i = 0; i < ints.length; i++) {
            for (int j = 0; j <= i; j++) {
                System.out.print(ints[i][j] + "\t");
            }
            System.out.println();
        }
        //关闭
        scanner.close();
    }
}

输出

1    
1    1    
1    2    1    
1    3    3    1    
1    4    6    4    1    
1    5    10    10    5    1    
1    6    15    20    15    6    1    
1    7    21    35    35    21    7    1    
1    8    28    56    70    56    28    8    1

05.数组练习之基本查找

public class ArrayDemo02 {
    public static void main(String[] args) {
        //定义一个数组
        int[] ints = {10, 20, 5, 80, 5, 18, 30, 90, 3};
        //根据元素查找出第一次出现的索引
        System.out.println(findIndexByEle(ints, 3));
    }

    private static int findIndexByEle(int[] arrays, int ele) {
        for (int i = 0; i < arrays.length; i++) {
            if (arrays[i] == ele) {
                return i;
            }
        }
        return -1;
    }
}

06.数组练习之二分查找

二分查找的前提：该数组的元素必须有序

二分查找的思想：每一次都查找中间的元素，比较大小就能减少一半的元素。

需求：使用二分查找出该元素在数组中第一次出现的索引

public class ArrayDemo03 {
    public static void main(String[] args) {
        //二分查找
        int[] ints = {3, 5, 5, 10, 18, 20, 30, 90};
        System.out.println(findIndexByEle(ints, 3));
    }

    private static int findIndexByEle(int[] arrays, int ele) {
        //初始值
        int minIndex = 0;
        int maxIndex = arrays.length - 1;
        int midIndex = (minIndex + maxIndex) / 2;

        while (minIndex <= maxIndex) {
            if (arrays[midIndex] == ele) {
                //正好相等，直接返回
                return midIndex;
            } else if (arrays[midIndex] < ele) {
                //往后找，移动最小索引，minIndex = midIndex + 1，重新计算中间索引midIndex
                minIndex = midIndex + 1;
                midIndex = (minIndex + maxIndex) / 2;
            } else {
                //往前找，移动最小索引，maxIndex= midIndex - 1，重新计算中间索引midIndex
                maxIndex = midIndex - 1;
                midIndex = (minIndex + maxIndex) / 2;
            }
        }
        //没有找到返回-1
        return -1;
    }
}

11.冒泡排序

排序原理：数组元素两两比较，交换位置，大元素往后放，那么经过一轮比较后，最大的元素，就会出现在最大的索引处。

图解：

img

public class BubbleSortDemo {
    public static void main(String[] args) {
        int[] arrays = {8, 60, 50, 3, 5, 10, 50};
        sort(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    private static void sort(int[] arrays) {
        //数组元素两两比较，交换位置，大元素往后放，那么经过一轮比较后，最大的元素，就会出现在最大的索引处
        for (int i = 0; i < arrays.length - 1; i++) {
            for (int j = 0; j < arrays.length - 1 - i; j++) {
                //> 升序  < 降序
                if (arrays[j] > arrays[j + 1]) {
                    //交换位置
                    int temp = arrays[j];
                    arrays[j] = arrays[j + 1];
                    arrays[j + 1] = temp;
                }
            }
        }
    }
}

12.选择排序

排序原理：从0索引处开始，依次和后面的元素进行比较，小的元素往前放，经过一轮比较后，最小的元素就会出现在最小的索引处

图解：

img

public class SelectionSortDemo {
    public static void main(String[] args) {
        int[] arrays = {8, 60, 50, 3, 5, 10, 50};
//        derivation(arrays);
        sort(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    private static void derivation(int[] arrays) {
        //第一轮
        int i = 0;
        for (int j = 1; j < arrays.length; j++) {
            if (arrays[i] > arrays[j]) {
                int temp = arrays[i];
                arrays[i] = arrays[j];
                arrays[j] = temp;
            }
        }
        //第二轮
        i = 1;
        for (int j = 2; j < arrays.length; j++) {
            if (arrays[i] > arrays[j]) {
                int temp = arrays[i];
                arrays[i] = arrays[j];
                arrays[j] = temp;
            }
        }

        //第三轮
        i = 2;
        for (int j = 3; j < arrays.length; j++) {
            if (arrays[i] > arrays[j]) {
                int temp = arrays[i];
                arrays[i] = arrays[j];
                arrays[j] = temp;
            }
        }
        //...
    }

    private static void sort(int[] arrays) {
        //从0索引处开始，依次和后面的元素进行比较，小的元素往前放，经过一轮比较后，最小的元素就会出现在最小的索引处
        for (int i = 0; i < arrays.length - 1; i++) {
            for (int j = i + 1; j < arrays.length; j++) {
                if (arrays[i] > arrays[j]) {
                    int temp = arrays[i];
                    arrays[i] = arrays[j];
                    arrays[j] = temp;
                }
            }
        }
    }
}

13.直接插入排序

排序原理：算法思路：直接插入排序是一种最简单的排序方法，他的基本操作是将一个记录插入到一个长度为m的有序表中，使之仍然有序。(从第二个元素开始，每次和前一个元素比较，小于就互换[升序]，再从第三个元素开始。。。)

图解：

img

public class DirectInsertionSortDemo {
    public static void main(String[] args) {
        /**
         * 8, 60, 50, 3
         * [8]
         * [8,60]
         * [8,50,60]
         * [3,8,50,60]
         */
        int[] arrays = {8, 60, 50, 3, 5, 10, 50};
        sort(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    private static void sort(int[] arrays) {
        //直接插入排序是一种最简单的排序方法，他的基本操作是将一个记录插入到一个长度为m的有序表中，使之仍然有序。
        for (int i = 1; i < arrays.length; i++) {
            for (int j = i; j > 0; j--) {
                //当前元素和前一个元素比较，小于，互换
                if (arrays[j] < arrays[j - 1]) {
                    int temp = arrays[j];
                    arrays[j] = arrays[j - 1];
                    arrays[j - 1] = temp;
                }
            }
        }
    }
}

14.希尔排序

希尔排序，又称缩小增量排序（对直接插入排序的优化）

  • 基本思想：先将原表按增量ht分组，每个子文件按照直接插入法排序。同样，用下一个增量ht/2将文件再分为子文件，再按照直接插入法排序。直到ht=1整个文件排好序
  • 关键：选择合适的增量（步长）
  • 希尔排序算法可以通过三种循环来实现。

图解：

image-20210318113229448

增量的选择

knuth序列

  • h=1
  • h=3*h + 1 (1,4,13,40,121,364,...)

减小间隔

  • 举例说明，含有1000个元素的数组，可能先以364为增量，然后逐次以121,40,13,4为增量，最后以1位增量进行希尔排序，用来形成间隔的数列被称为间隔数列。这里所表示的间隔序列有kunth提出。此序列很常见，数列以逆向形式从1开始，通过递归表达式h=3*h + 1来产生，初始值为1
  • 在排序算法中，首先在一个短小的循环中使用序列的生成公式来计算出最初的间隔，h值最初为1，然后应用公式h=h*3+1生成序列1,4,13,40,121,364等等。当间隔大于数组大小的时候，这个过程停止，对于一个含有 1000个元素的数组，序列的第七个数字1093就太大了，因此使用序列的第六个数字来开始这个排序过程。然后每完成一次排序全程的外部循环，用前面提供的此公式倒推来减小间隔：h=(h-1)/3 这个倒推的公式生成的逆向序列364,121,40,13,4,1 从364开始，以每一个数字作为增量进行排序，当数组用1增量排序后，算法结束
  • 希尔排序比插入排序快很多，它是基于什么原因呢？当h值很大的时候，数据项每一趟排序需要移动元素的个数很少，但是数据项移动的距离很长。这是非常有效率的。当h减小时，每一趟排序需要移动的元素的个数增多，但是此时数据项已经接近于他们排序后最终的位置，这对于插入排序可以更有效率。正式这两种情况的结合才能使希尔排序效率那么高。
public class ShellSortDemo {
    public static void main(String[] args) {
        int[] arrays = {46, 55, 13, 42, 17, 94, 5, 70};
        sort(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    private static void sort(int[] arrays) {
        //初版
        //第一轮
        /*int h = 4;
        for (int i = h; i < arrays.length; i++) {
            for (int j = i; j > h - 1; j-=h) {
                if (arrays[j] < arrays[j - h]) {
                    int temp = arrays[j];
                    arrays[j] = arrays[j - h];
                    arrays[j - h] = temp;
                }
            }
        }
        //第二轮
        h=2;
        for (int i = h; i < arrays.length; i++) {
            for (int j = i; j > h - 1; j-=h) {
                if (arrays[j] < arrays[j - h]) {
                    int temp = arrays[j];
                    arrays[j] = arrays[j - h];
                    arrays[j - h] = temp;
                }
            }
        }
        //第三轮
        h=1;
        for (int i = h; i < arrays.length; i++) {
            for (int j = i; j > h - 1; j-=h) {
                if (arrays[j] < arrays[j - h]) {
                    int temp = arrays[j];
                    arrays[j] = arrays[j - h];
                    arrays[j - h] = temp;
                }
            }
        }*/
        //优化第一版（改成循环，增量是写死的）
        /*for (int h = 4; h > 0; h /= 2) {
            for (int i = h; i < arrays.length; i++) {
                for (int j = i; j > h - 1; j-=h) {
                    if (arrays[j] < arrays[j - h]) {
                        int temp = arrays[j];
                        arrays[j] = arrays[j - h];
                        arrays[j - h] = temp;
                    }
                }
            }
        }*/
        //优化第二版：希尔排序的核心思想，合理的选择这个增量  新增选取数组长度的一半
        /*for (int h = arrays.length / 2; h > 0; h /= 2) {
            for (int i = h; i < arrays.length; i++) {
                for (int j = i; j > h - 1; j -= h) {
                    if (arrays[j] < arrays[j - h]) {
                        int temp = arrays[j];
                        arrays[j] = arrays[j - h];
                        arrays[j - h] = temp;
                    }
                }
            }
        }*/
        //优化第三版，增量选择数组的一半，效率还不是很高，可以使用一种序列，叫做克努特序列knuth
        int interval = 1;
        while (interval < arrays.length) {
            interval = interval * 3 + 1;
        }
        //取前一个
        interval = (interval - 1) / 3;
        System.out.println("选取的增量：" + interval);
        for (int h = interval; h > 0; h = (h - 1) / 3) {
            for (int i = h; i < arrays.length; i++) {
                for (int j = i; j > h - 1; j -= h) {
                    if (arrays[j] < arrays[j - h]) {
                        int temp = arrays[j];
                        arrays[j] = arrays[j - h];
                        arrays[j - h] = temp;
                    }
                }
            }
        }
    }
}

15.快速排序（重点）

排序思想

  • 分治法：比大小，再分区

    • 从数组中取出一个数，作为基准数
    • 分区，将比这个数大或者等于的数全部放到它的右边，小于它的数全部放到它的左边
    • 再对左右区间重复前两步，直到各个区间只有一个数

实现思路

  • 挖坑填数

    1. 将基准数挖出形成第一个坑（坑位1）
  1. 由后向前找比它小的数，找到后挖出此数（坑位2）填到前一个坑（坑位1）前
  2. 由前向后找比它大或等于的数，找到后挖出此数（坑位3）填到前一个坑（坑位2）中
  3. 再重复执行1,2,3两个步骤

image-20210323175119836

public class QuickSortDemo {
    public static void main(String[] args) {
        int[] arrays = {8, 60, 50, 3, 5, 10, 50};
        //快速排序，需用用到递归
        sort(arrays, 0, arrays.length - 1);
        System.out.println(Arrays.toString(arrays));
    }

    private static void sort(int[] arrays, int startIndex, int endIndex) {
        if (startIndex < endIndex) {
            //找到基准数所在位置的下标
            int baseIndex = getBaseIndex(arrays, startIndex, endIndex);
            //对基准数的左分区递归
            sort(arrays, startIndex, baseIndex - 1);
            //对基准数的右分区递归
            sort(arrays, baseIndex + 1, endIndex);
        }
    }

    private static int getBaseIndex(int[] arrays, int startIndex, int endIndex) {
        //l 左下标
        int l = startIndex;
        //r 右下标
        int r = endIndex;
        //baseNum 基准数
        int baseNum = arrays[l];
        while (l < r) {
            //由后向前找比它小的数，找到后挖出此数（坑位2）填到前一个坑前
            while (l < r && arrays[r] >= baseNum) {
                r--;
            }
            if (l < r) {
                arrays[l] = arrays[r];
                l++;
            }
            //由前向后找比它大或等于的数，找到后挖出此数（坑位3）填到前一个坑中
            while (l < r && arrays[l] < baseNum) {
                l++;
            }
            if (l < r) {
                arrays[r] = arrays[l];
                r--;
            }
        }
        //填基准数(当i和j重合时)
        /*arrays[r] = baseNum;
        return r;*/
        arrays[l] = baseNum;
        return l;
    }
}

16.归并排序

MergeSort就是利用归并的思想实现排序的方法。它的原理是假设初始序列有N个记录，则可以看成N个有序的子序列，每个子序列的长度为1，然后两两归并，得到一个N/2个长度为2或者1的有序子序列，再两两归并。。。如此重复，直到得到一个长度为N的有序序列为止，这种排序方法称为2路归并排序。（这里视频有点模糊）

image-20210321211316895

public class MergeSortDemo {
    public static void main(String[] args) {
        //先给一个左右两边是有序一个数组，先来进行归并操作
        int[] arrays = {4, 5, 7, 8, 1, 2, 3, 6, 0, -1, 50, -10, 80, 10};
        //拆分
        splits(arrays, 0, arrays.length - 1);
        //归并
//        merge(arrays, 0, 3, arrays.length - 1);
        System.out.println(Arrays.toString(arrays));
    }

    private static void splits(int[] arrays, int startIndex, int endIndex) {
        if (startIndex >= endIndex) {
            return;
        }
        //计算中间索引
        int centerIndex = startIndex + ((endIndex - startIndex) >> 1);
        //对左边的数组进行递归拆分
        splits(arrays, startIndex, centerIndex);
        //对右边的数据进行递归拆分
        splits(arrays, centerIndex + 1, endIndex);
        //合并
        merge(arrays, startIndex, centerIndex, endIndex);
    }

    private static void merge(int[] arrays, int startIndex, int centerIndex, int endIndex) {
        //定义一个临时数组
        int[] tempArrays = new int[endIndex - startIndex + 1];
        //定义左边数组的起始索引
        int i = startIndex;
        //定义左边数组的起始索引
        int j = centerIndex + 1;
        //定义临时数组的起始索引
        int index = 0;
        //比较左右两个数组的大小
        while (i <= centerIndex && j <= endIndex) {
            //从两个数组中取出最小的放入临时数组
            if (arrays[i] <= arrays[j]) {
                tempArrays[index] = arrays[i];
                i++;
            } else {
                tempArrays[index] = arrays[j];
                j++;
            }
            index++;
        }
        //处理左边剩余元素
        while (i <= centerIndex) {
            tempArrays[index] = arrays[i];
            i++;
            index++;
        }
        //处理右边剩余元素
        while (j <= endIndex) {
            tempArrays[index] = arrays[j];
            j++;
            index++;
        }
        //将临时数组的元素取到元素组中
        for (int k = 0; k < tempArrays.length; k++) {
            arrays[k + startIndex] = tempArrays[k];
        }
    }
}

17.基数排序

基数排序不同于之前所介绍的各类排序，前面介绍的排序方法或多或少的是通过比较和移动记录来实现排序，而基数排序的实现不需要进行对关键字的比较，只需要对关键字进行“分配”和“收集”两种操作即可完成

image-20210322231711081

public class RadixSortDemo {
    public static void main(String[] args) {
        int[] arrays = {2, 1, 5, 21, 31, 444, 23, 33, 47, 10, 903, 124, 987, 100};
        sort(arrays);
        System.out.println(Arrays.toString(arrays));
    }

    private static void sort(int[] arrays) {
        //定义二维数组，放10个桶
        int[][] tempArrays = new int[10][arrays.length];
        //定义一个统计数组
        int[] counts = new int[10];
        //确定排序轮次
        //获取数据中的最大值
        int max = getMax(arrays);
        System.out.println("数组中的最大值为:" + max);
        int len = String.valueOf(max).length();
        for (int i = 0, n = 1; i < len; i++, n *= 10) {
            for (int j = 0; j < arrays.length; j++) {
                //取出每个位上的数字
                int unit = arrays[j] / n % 10;
                tempArrays[unit][counts[unit]++] = arrays[j];
            }
            //取出桶中的元素
            int index = 0;
            for (int k = 0; k < counts.length; k++) {
                if (counts[k] == 0) {
                    continue;
                }
                for (int h = 0; h < counts[k]; h++) {
                    //从桶中取出元素放回原数组
                    arrays[index] = tempArrays[k][h];
                    index++;
                }
                //清除上一次统计的个数
                counts[k] = 0;
            }
        }
    }

    private static int getMax(int[] arrays) {
        int max = arrays[0];
        for (int i = 1; i < arrays.length; i++) {
            if (max < arrays[i]) {
                max = arrays[i];
            }
        }
        return max;
    }
}

18.堆排序

堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序

堆排序 基本思想：

  1. 将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点
  2. 将其于末尾元素进行交换，此时末尾为最大值
  3. 然后将剩余n-1元素重新构造成一个堆，这样会得到n个元素的次小值
  4. 如次反复执行，便能得到一个有序序列了

image-20210321222725945

image-20210322223942543

public class HeapSortDemo {
    public static void main(String[] args) {
        int[] arrays = {1, 0, 6, 7, 2, 3, 4, 3, 5, 8, 10, 4};
        //调整成大顶堆
        //定义开始调整的位置
        int startIndex = (arrays.length - 1) / 2;
        for (int i = startIndex; i >= 0; i--) {
            toMaxHeap(arrays, arrays.length, i);
        }
        //经过上面的操作，已经把数组变成一个大顶堆，把根元素和最后一个元素进行调换
        for (int i = arrays.length - 1; i > 0; i--) {
            //调换
            int temp = arrays[0];
            arrays[0] = arrays[i];
            arrays[i] = temp;
            //调换完之后，我们再把剩余元素调用大顶堆
            toMaxHeap(arrays, i, 0);
        }
        System.out.println(Arrays.toString(arrays));
    }

    /**
     * 调整成大顶堆
     *
     * @param arrays 要排序的数组
     * @param size   调整的元素的个数
     * @param index  从哪里开始调整
     */
    private static void toMaxHeap(int[] arrays, int size, int index) {
        //获取左右节点的索引
        int leftNodeIndex = index * 2 + 1;
        int rightNodeIndex = index * 2 + 2;
        //查找最大节点对应的索引
        int maxIndex = index;
        if (leftNodeIndex < size && arrays[leftNodeIndex] > arrays[maxIndex]) {
            maxIndex = leftNodeIndex;
        }
        if (rightNodeIndex < size && arrays[rightNodeIndex] > arrays[maxIndex]) {
            maxIndex = rightNodeIndex;
        }
        //调换位置
        if (index != maxIndex) {
            int temp = arrays[maxIndex];
            arrays[maxIndex] = arrays[index];
            arrays[index] = temp;
            //调换完之后，可能会影响到下面的子树不是大顶堆，我们还需要再次调换
            toMaxHeap(arrays, size, maxIndex);
        }
    }
}
文章标签：
搜索推荐
索引
算法
dsnimfifrfn22
目录
相关文章
jjczqyjxgdegi
|
5月前
|
存储 移动开发 算法
技术笔记：pintia_L1_20题目集合
技术笔记：pintia_L1_20题目集合
jjczqyjxgdegi
30 0
JYeontu
|
6月前
|
算法 前端开发 索引
2624. 蜗牛排序
2624. 蜗牛排序
JYeontu
33 0
小程序面包园
|
12月前
LeetCode刷题之 存在重复元素（题目分析➕源代码）
LeetCode刷题之 存在重复元素（题目分析➕源代码）
小程序面包园
38 0
小小何先生
|
搜索推荐 算法
LeetCode刷题系列(三)排序
LeetCode刷题系列(三)排序
小小何先生
46 0
渴望力量的土狗
|
搜索推荐
牛客刷题—排序
牛客刷题—排序
渴望力量的土狗
83 0
辰Chen
|
算法 搜索推荐 C语言
蓝桥杯第七讲--排序【例/习题】
蓝桥杯第七讲--排序【例/习题】
辰Chen
121 0
蓝桥杯第七讲--排序【例/习题】
凉云生烟
|
人工智能 算法
【0基础学算法】快速排序(超详细讲解+私人笔记+源码）下
笔记
凉云生烟
112 0
刘天棋
|
算法 搜索推荐
算法竞赛基础题做题记录：三位数排序
算法竞赛基础题做题记录：三位数排序
刘天棋
107 0
布小禅
|
算法 Java Python
LeetCode刷题1920-简单-给予排列构建数组
LeetCode刷题1920-简单-给予排列构建数组
布小禅
158 0
LeetCode刷题1920-简单-给予排列构建数组
游客kyclow5orjnii
|
算法 UED
【算法笔记题解】《算法笔记知识点记录》第四章——算法初步2——哈希
【算法笔记题解】《算法笔记知识点记录》第四章——算法初步2——哈希
游客kyclow5orjnii
142 0