复习八大排序

左手的ㄟ右手 2023-07-17 11:27 6阅读 0赞

这篇文章用来复习一下数据结构中常提到的八大排序和三大查找算法

## 八大排序 ##

八大排序都有哪些？  
八大排序按照种类可以分为以下几种：

1.  交换排序：冒泡，快排
2.  插入排序：直接插入，希尔排序
3.  选择排序：直接选择，堆排
4.  归并排序
5.  基数排序

下面就按照顺序对八大排序进行复习

### 交换类排序 ###

#### 冒泡 ####

// 最简化版的
        public static void myBubbleSort(int[] arr) {
    
            int realCount = 0;
    
            // 外层循环控制冒出泡的个数，每循环一次就会冒出一个
            for (int i = 0; i < arr.length; i++) {
                // 内层循环进行相邻冒泡操作  将最大的值冒泡到最右边
                for (int i1 = 0; i1 < arr.length - i - 1; i1++) {
                    realCount++;
                    if (arr[i1] > arr[i1 + 1]) {
                        swap(arr, i1, i1 + 1);
                    }    
                }
            }
            System.out.println(realCount);
            for (int i : arr) {
                System.out.print(i + "  ");
            }
    
        }
    
        public static void swap(int[] arr, int index1, int index2) {
            int temp;
            temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = temp;
        }

打印结果如下  
![在这里插入图片描述][20200321100724316.png]  
使用Flag进行冒泡排序优化

// 思路：相邻交换
        // 优化：可采用flag进行循环优化,开始每次开始就设置为false，如果有修改记录就设置为true，然后加入判断条件
        public static void myBubbleSort(int[] arr) {
    
            boolean flag = true;
            int realCount = 0;
    
            // 外层循环控制冒出泡的个数，每循环一次就会冒出一个
            for (int i = 0; i < arr.length; i++) {
                int count = 0;
                // 内层循环进行相邻冒泡操作  将最大的值冒泡到最右边
                for (int i1 = 0; i1 < arr.length - i - 1 && flag; i1++) {
                    realCount++;
                    if (arr[i1] > arr[i1 + 1]) {
                        swap(arr, i1, i1 + 1);
                        flag = true;
                        count++;
                    }
                    if (count == 0) {
                        flag = false;
                    }
                }
            }
            System.out.println(realCount);
            for (int i : arr) {
                System.out.print(i + "  ");
            }
    
        }
    
        public static void swap(int[] arr, int index1, int index2) {
            int temp;
            temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = temp;
        }

打印结果如下：可以看到比上一个少了五次交换  
![在这里插入图片描述][20200321100850327.png]

#### 快排 ####

快排就是快速排序，它的核心思想就是规定一个值为基准值（需要注意的是不是基准指针），比基准值大的值交换到左边，比基准值小的交换到右边，如此往复递归就逐步确定顺序了

public static void myQuickSort(int[] arr, int left, int right) {
            int index = (left + right) / 2;
            // 基准值
            int pivot = arr[index];
            int pl = left;
            int pr = right;
    
            // 满足的条件是左指针小于右指针
            while (pl < pr) {
                // 找到左边第一个比pivot大的值
                while (arr[pl] < pivot) {
                    pl++;
                }
                // 从右边找第一个比pivot小的值
                while (arr[pr] > pivot) {
                    pr--;
                }
    
                // 判断是否指针交叉
                if (pl > pr) {
                    break;
                }
                // 那就swap
                swap(arr,pl,pr);
    
                // 如果是基准值位置改变
                // 基准值跑到了右边
                if (arr[pr]==pivot){
                    pr--;
                }
                // 如果基准值跑到了左边
                if (arr[pl] == pivot){
                    pl++;
                }
                // 无误就进行下一次循环，直到出现了指针交叉
            }
    
            // 递归调用  如果错位了的话才会到这里，错位时就相当于把pivot的值空了出来，也不用再次参加排序
            if (pr>left){
                myQuickSort(arr,left,pr);
            }
            if (pl<right){
                myQuickSort(arr,pl,right);
            }
        }
    
     public static void swap(int[] arr, int index1, int index2) {
            int temp;
            temp = arr[index1];
            arr[index1] = arr[index2];
            arr[index2] = temp;
        }

运行结果：  
![20200321114152819.png][]  
可以看到快速排序的效率和基准点的选取有关  
常见的快排的几种方式（最坏情况）

1.  固定点
2.  随机取点
3.  三数取中（left，mid，right）选择次大的一个值，可以扩展为多点取中，如五点取中

优化思路：可以将数组小于某个范围后将它改为插入排序，因为此时数据都很几乎很集中（但是这种优化思路对于本身有序的并没有太大效果提升，适合随机的，一般采用的是三数取中+插排）

if (right - left+1 <10){
    // 插入排序
    }else{
    // 快排
    }

## 插入类排序 ##

### 直接插入 ###

插入排序的核心思想就是在给定的数组内划分出一个有序的区域和无序的区域，然后每一轮从无序的区域中取一个元素插入到有序区域  
虽然这个排序很easy，但是编译器完全不给我面子，把测试的旧的数组缓存给我存了好长时间，还以为代码写错了，改了好长时间都发现不了。

public static void myInsertSort(int[] arr) {
       
            for (int i = 1; i < arr.length; i++) {
                int temp = arr[i];
                int j;
                // 如果碰到一个比temp大的就往后移动，最后只需要记住temp需要插入的地方就行了
                for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                    arr[j + 1] = arr[j];
                }
                arr[j+1] = temp;
    
            }
        }

下图是我手写的。当i指向的值是2的执行过程，也就是最外层循环执行的一次流程![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70]

### 希尔排序 ###

希尔排序也叫缩小增量法，是加强版的插入排序，因为希尔排序到增量为1的时候就是插入排序

// 缩小增量  代码上就是讲插入排序的gap动态改变
        public static void  myShellSort(int[] arr) {
    
    
            for (int gap = arr.length / 2; gap >= 1; gap /= 2) {
                
                //下面就是变形的插入排序（只是插入排序的gap恒等于1）
                for (int i = gap; i < arr.length; i++) {
                    int temp = arr[i];
                    int j;
                    // 容易出现错误的点就是此处的条件是j>=0，而不是j>=gap
                    for (j = i - gap; j >= 0 && temp<arr[j]; j-=gap) {
                        arr[j + gap] = arr[j];
                    }
                    arr[j + gap] = temp;
                }
    
            }
        }

结果如下  
![在这里插入图片描述][20200321163541220.png]

## 选择类排序 ##

### 直接选择排序 ###

直接选择排序就和它的名字一样，它每一轮会选择出一个最大的值/最小的值，如此往复循环就可以完成排序,代码实现也是很简单

public static void mySelectSort(int[] arr) {
    
            // 外层控制的是进行的进度 每次找出一个最小值放在前面
            for (int i = 0; i < arr.length; i++) {
                int min = arr[i];
                int index = i;
                // 内存控制的是需要进行比较的轮次
                    for (int j = i + 1; j < arr.length; j++) {
                        // 需要记录最小值的index就ok  默认i指的就是最小值
                        if (arr[j] < min) {
                            min = arr[j];
                            index = j;
                        }
                    }
                    arr[index] = arr[i];
                    arr[i] = min;
                }
        
        
            }

运行结果如下  
![在这里插入图片描述][20200321203746659.png]

### 堆排序 ###

了解堆排序之前，先说说什么是堆？  
简单来说

1.  堆的首要条件就是要是一颗完全二叉树，从数组层面来看就是数组的数据要是连续的
2.  它的某个父节点对应的子节点总能小于或者是大于它的父节点。

因此，从堆的定义来看，堆可以分为两种类型，一种是大顶堆，另外一种就是小顶堆。所谓大顶堆就是最顶的节点它是最大的，所谓小顶堆就是最顶的节点它是最小的。  
正是因为堆必须是一个完全二叉树，所有它对应到数组就会有如下两个公式，这也是在构建堆时必不可少的已知条件。  
公式如下：  
对于任何一个下标为n并且有子节点的节点都有如下公式：

*  左子节点下标 = 2n+1
 *  右子节点下标 = 2n+2

由此也可以从子节点得到父节点的下标，这样的关系就可以保证给出的数组就一定是一个堆，并且这个堆也是逻辑可控的。

在下面我就以我的测试用例逐步进行推导 —————— 用例：1,16,7,3,20,17,8

首先，根据这个数组，可以构建出一个逻辑上的不完全的堆，如下图（画的有点难看）  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 1]  
为什么说它是一个不完全的堆呢？因为，它并完全不满足堆的定义（不满足第二条），因此就有了adjust方法来保证它是一个完整的堆。

adjust简而言之就是调整，假如我们是大顶堆，对应下图中下标为0，1，2的一个树该怎么去调整，原理很简单就是去比较，把最大的拿到根上就ok了。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 2]  
因此，可以知道adjust方法就是一个三个数见比大小并交换位置。接着我们继续往下，如果不断扩大规模，如最开始那张不完整堆的图，其实可以想到，都有一样的道理，我们**只需要去找到最后一个节点的父节点**，然后一直倒序变量并调用adjust方法就可以完成对堆的维护。  
如下图  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 3]  
可以发现只需要对以下标2位根对应的子树和以下标1位根保持大顶堆， 然后最后对以下标为1的堆进行调整，这样就可以保证大顶堆的构建了。根据调整就可以构建出如下的一个大顶堆结构了  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 4]

package sort;
    /*
     * @Author  Wrial
     * @Date Created in 15:51 2020/3/21
     * @Description 堆排序 堆排序分为大顶堆和小顶堆，大顶堆一般对应的降序排列，小顶堆一般是用于升序排列
     */
    
    public class HeapSort {
    
        public static void main(String[] args) {
            int[] nums = {16, 1, 7, 3, 20, 17, 8};
            headSort(nums);
            for (int num : nums) {
                System.out.print(num + " ");
            }
        }
    
        /**
         * 堆排序
         */
        public static void headSort(int[] list) {
            //构造初始堆,从第一个非叶子节点开始调整,左右孩子节点中较大的交换到父节点中
            for (int i = (list.length) / 2 - 1; i >= 0; i--) {
                headAdjust(list, list.length, i);
            }
            //排序，将最大的节点放在堆尾，然后从根节点重新调整
            for (int i = list.length - 1; i >= 1; i--) {
                int temp = list[0];
                list[0] = list[i];
                list[i] = temp;
                headAdjust(list, i, 0);
            }
        }
    
        /**
         * @param list arr
         * @param len  当前这个堆的大小，因为在后面进行堆调整的时候会变
         * @param i    需要调整的下标
         */
        private static void headAdjust(int[] list, int len, int i) {
            int k = i, temp = list[i], index = 2 * k + 1;
            // 当子节点下标<len 也就是说它要是还有左子节点的话
            while (index < len) {
                // 如果有右子节点
                if (index + 1 <= len - 1) {
                    // 如果左子节点小于右子节点
                    if (list[index] < list[index + 1]) {
                        // 就讲指针指向右子节点
                        index = index + 1;
                    }
                }
                // 如果当前的子节点中最大的值大于父节点的值，就进行替换
                if (list[index] > temp) {
                    list[k] = list[index];
                    // 并且将index更新到被修改的子节点上进行调整，直到break
                    k = index;
                    index = 2 * k + 1;
                } else {
                    break;
                }
            }
            // 要清楚的是引起堆变化的节点就说明它是相对小的节点，空出的位置必然是它，因此在上面只需要往上填，下面的值一定是这个temp 
            list[k] = temp;
        }
    
    }

结果演示：  
![在这里插入图片描述][20200321223258166.png]

## 归并排序 ##

归并排序的算法思想其实就是分治算法，什么是分治算法呢？简单的来说就是先分后治，大而化小，最后合并。具体流程根据这组测试用例来完成------100,-5,8,1,9

分解过程，需要注意的是，这个分解过程并不是真实存在的，只是通过递归进行的逻辑分解  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 5]  
合并过程，合并过程是根据递归的逻辑分解，创建临时数组完成合并后再拷贝到原数组  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 6]

// 先分再合
    
        /**
         * @param arr   待排序数组
         * @param left  左指针
         * @param right 右指针
         */
        public static void myMergeSort(int[] arr, int left, int right) {
            // 首先要确定不能再分的条件right==left情况是本来有下标0和1，现在分了就剩下一个元素了，也不可分
            // 剩下了一个元素，length/2=0，左指针下标为0，右指针需要是length-1=-1（不满足）
            if (right > left) {
                int mid = (left + right) / 2;
                myMergeSort(arr, left, mid);
                myMergeSort(arr, mid + 1, right);
                myMerge(arr, mid, left, right);
            }
    
    
        }
    
        /**
         * @param arr 原数组
         * @param mid 中间分割点
         * @param left 左指针
         * @param right 右指针
         */
        public static void myMerge(int[] arr, int mid, int left, int right) {
    
            // 建立临时数组，将值拷贝过来
            int[] temp1 = new int[mid - left + 1];
            int[] temp2 = new int[right - mid];
    
            for (int i = left; i <= mid; i++) {
                temp1[i-left] = arr[i];
            }
            for (int i = mid + 1; i <= right; i++) {
                temp2[i - mid - 1] = arr[i];
            }
    
    
            // 对有序结构进行插入排序，将每个数组最小的值放在最前面
            int tempLeft = 0;
            int tempRight = 0;
            int arrayIndex = left;
            while (tempLeft < temp1.length && tempRight < temp2.length) {
    
                if (temp1[tempLeft]<= temp2[tempRight]){
                    arr[arrayIndex] = temp1[tempLeft];
                    arrayIndex++;
                    tempLeft++;
                }else {
                    arr[arrayIndex] = temp2[tempRight];
                    arrayIndex++;
                    tempRight++;
                }
    
            }
            while (tempLeft<temp1.length){
                arr[arrayIndex] = temp1[tempLeft];
                arrayIndex++;
                tempLeft++;
            }
            while (tempRight<temp2.length){
                arr[arrayIndex] = temp1[tempRight];
                arrayIndex++;
                tempRight++;
            }
    
    
        public static void main(String[] args) {
            int[] arr1 = {100, -5, 8, 1, 9};
            System.out.println(Arrays.toString(arr1));
            myMergeSort(arr1, 0, arr1.length - 1);
            System.out.println(Arrays.toString(arr1));
        }
    
        }

结果如下：  
![在这里插入图片描述][20200322102712756.png]

## 基数排序 ##

基数排序的核心思想感觉有点像堆排序的从小到大建堆（自我感觉），先保持局部有序，再保证全体有序。思想就是从最小位数开始比较，然后放到指定的桶里，接着比较高一位如此往复  
以以下数据为例——5, 2, 33, 0, 9, 562, 4,

第一轮：比较个位并入桶 取出的结果为0 2 562 33 4 5 9  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 7]  
第二轮：比较百位，取出的结果0 2 4 5 9 33 562  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 8]  
第三轮:：比较百位并入桶，由于最高只有百位所以结束，结果为0 2 4 5 9 33 562  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 9]  
这样就完成了桶排序也就是基数排序  
因此桶排序需要的空间是一个二维数组，而不是一维数组  
代码如下

public static void main(String[] args) {
     
            int[] arr = {5, 2, 33, 0, 9, 562, 4, 6, 213, 1, 111};
            sort(arr);
            System.out.println(Arrays.toString(arr));
    
        }
    
        //根据个位十位和百位进行分桶排序（先个位，十位....）
        public static void sort(int[] arr) {
            //1.获取数组中最大数的位数
            int max = arr[0];
            int maxLength = 0;
            int index;
            for (int i = 1; i < arr.length; i++) {
                if (arr[i] > max) {
                    max = arr[i];
                }
            }
            String maxTemp = max + "";
            //间接求出最大数的长度
            maxLength = maxTemp.length();
            System.out.println(maxLength);
            //2.建立10个桶(十列)，桶的大小就是数组的长度
            int[][] barrels = new int[10][arr.length];
            //3.需要一个桶计数器，计数各个桶里有几个数字 并进行初始化
            int[] barrelCounter = new int[10];
            for (int i = barrelCounter.length - 1; i >= 0; i--) {
                barrelCounter[i] = 0;
            }
            System.out.println("桶计数器初始化"+Arrays.toString(barrelCounter));
            //4.将数放入桶，从低到高
            // 333/1%10  333/10%10 333/100%10
            for (int j = 0, n = 1; j < maxLength; j++, n *= n) {
                System.out.println("第"+(j+1)+"轮开始");
                //放数字到相应的桶
                for (int i = 0; i < arr.length; i++) {
                    int digital = arr[i] / n % 10;
                    barrels[digital][barrelCounter[digital]] = digital;
                    barrelCounter[digital]++;
                }
                index = 0;
                //5.每放完一轮将数字再拿出来
                for (int i = 0; i < 10; i++) {
                    if (barrelCounter[i] != 0) { //说明有数字
                        for (int k = 0; k < barrelCounter[i]; k++) {
                            arr[index] = barrels[i][k];
                            index++;
                        }
                    }
                }
                //6.计数清零
                for (int i = 0; i < barrelCounter.length; i++) {
                    barrelCounter[i] = 0;
                }
                System.out.println("第"+(j+1)+"轮结束");
            }
        }

结果如下：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 10]  
这就是八大排序的所有内容！

[20200321100724316.png]: /images/20230528/b7af8283d3034856b45ef975d972fe55.png
[20200321100850327.png]: /images/20230528/d95f7bcdf6e54aa797a6faa9ae3c60ec.png
[20200321114152819.png]: /images/20230528/2c402856eff140cca38e63ce11885b99.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70]: /images/20230528/317a544f80354ccd90a377a4d7bffdca.png
[20200321163541220.png]: /images/20230528/9656a57b496043fd8124b9b6a5940c28.png
[20200321203746659.png]: /images/20230528/da09564d03dc4c75a8c5dc24ecc660e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 1]: /images/20230528/2f398cab195e48e3ad0437188d6293e9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 2]: /images/20230528/d4bd651102c549b9915090a8c84eff8c.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 3]: /images/20230528/825ac71ad75149ba930a831bfa2d4ad9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 4]: /images/20230528/473ab8080339474baf37ea6a1a214770.png
[20200321223258166.png]: /images/20230528/1da52c7f1f7f48c7b5cd54b4ff77801b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 5]: /images/20230528/83db06316db04498a52319b18f506899.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 6]: /images/20230528/3e72ce6e86874edda131fb67e56a1ad8.png
[20200322102712756.png]: /images/20230528/3d04ca2c76394a839f27410eb7ef05d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 7]: /images/20230528/314907eea62342e6a09a6de4ed3eab2d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 8]: /images/20230528/c7c55b4261194264a6b43f0073a809cc.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 9]: /images/20230528/779cd0c6261841208c8784bf192756ee.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyNjA1OTY4_size_16_color_FFFFFF_t_70 10]: /images/20230528/1a426a1e22bd439b9d93987faaeb98e8.png