算法刷题记二（排序）

傷城~ 2022-09-01 13:51 149阅读 0赞

### 文章目录 ###

*   *  1、数组中的第K个最大元素（7/28-215）
     *  2、冒泡排序
     *  3、选择排序
     *  4、插入排序
     *  5、希尔排序
     *  6、快速排序
     *  7、归并排序
     *  8、基数排序
     *  9、堆排序

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70]

## 1、数组中的第K个最大元素（7/28-215） ##

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 1]

--------------------

解析：

排序 ：时间复杂度 O(NlogN)，空间复杂度 O(1)

class Solution { 
        public int findKthLargest(int[] nums, int k) { 
            Arrays.sort(nums);
            return nums[nums.length - k];
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 2]

--------------------

堆 ：时间复杂度 O(NlogK)，空间复杂度 O(K)。

class Solution { 
        public int findKthLargest(int[] nums, int k) { 
            PriorityQueue<Integer> pq = new PriorityQueue<>(); //小顶堆
            for(int val : nums) { 
                pq.add(val);  //添加元素
                if(pq.size() > k)  //维护堆的大小为k
                    pq.poll(); //删除队首元素
            }
            return pq.peek();  //获取队列队头元素并返回
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 3]

## 2、冒泡排序 ##

冒泡排序（Bubble Sort），是一种较简单的排序算法。

它重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换，也就是说该元素列已经排序完成。

这个算法的名字由来是因为越大的元素会经由交换慢慢“浮”到数列的顶端（升序或降序排列），就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样，故名“冒泡排序”。

![在这里插入图片描述][f6b450e063f249bc95c15df33bd84fdc.gif]

--------------------

解析：

首先在开始循环时定义了一个boolean变量为true，然后如果元素之间进行了交换，就将值置为false。所以，我们就可以通过这个boolean变量来判断是否有元素进行了交换。如果boolean变量为true，则证明没有元素进行交换，那么久说明此时的数组元素已经完成排序，那么跳出外层循环即可，否则就继续排序。

--------------------

Java实现：

@Test
        public void Test(){ 
            int[] arr = {  3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
            int count = 0;
            //第一轮比较
            for (int i = 0; i < arr.length - 1; i++) { 
                //第二轮比较
                boolean flag = true;
                for (int j = 0; j < arr.length - 1 - i; j++) { 
                    //判断
                    if (arr[j] > arr[j+1]){ 
                        //交换位置
                        int temp = arr[j];
                        arr[j] = arr[j+1];
                        arr[j+1] = temp;
                        count++;
                        flag = false;
                    }
                }
                if (flag){ 
                    break;
                }
            }
            System.out.println(Arrays.toString(arr));
            System.out.println("共比较了" + count + "次");
        }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 4]

## 3、选择排序 ##

选择排序（Selection sort）是一种简单直观的排序算法。它的工作原理是：第一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后再从剩余的未排序元素中寻找到最小（大）元素，然后放到已排序的序列的末尾。以此类推，直到全部待排序的数据元素的个数为零。选择排序是不稳定的排序方法。

![在这里插入图片描述][e3276ef34c154ae4a19c284d09c6a191.gif]

--------------------

解析：

首先在外循环里定义了一个index变量存储i的值，这是为了避免重复地比较，因为在每一轮的比较结束后，前i个元素是已经排好序的，所以无需再次比较，只需从i开始即可。后面的比较都是基于index位置的元素进行比较，倘若比较完后index位置的元素是最小值，那就无需交换，不动即可。而如果找到了比index位置的元素更小的元素，那就将该元素的索引赋值给index，然后继续比较，直到比较完成，比较完成之后得到的index即为数组中的最小值，那此时只需要将index位置的元素和i位置的元素交换即可。

--------------------

Java实现：

@Test
        public void Test(){ 
            int[] arr = {  3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
            //第一轮比较
            for (int i = 0; i < arr.length - 1; i++) { 
                int index = i; //下标
                for (int j = i + 1; j < arr.length; j++) { 
                    if (arr[j] < arr[index]){ 
                        index = j;  // 保存最小元素的下标
                    }
                }
                //交换
                int temp = arr[index];
                arr[index] = arr[i];
                arr[i] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }

![在这里插入图片描述][5a45527c45f4411cbc6a844b3a94fccb.png]

## 4、插入排序 ##

插入排序（Insertion sort）是一种简单直观且稳定的排序算法。如果有一个已经有序的数据序列，要求在这个已经排好的数据序列中插入一个数，但要求插入后此数据序列仍然有序，这个时候就要用到一种新的排序方法——插入排序法,插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中，从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序，时间复杂度为O(n^2)。是稳定的排序方法。插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。  
插入排序的基本思想是：每步将一个待排序的记录，按其关键码值的大小插入到前面已经排序的数组中的适当位置上，直到全部插入完为止。  
![在这里插入图片描述][ddce4349f54e40da8b712a27a9add3ec.gif]

--------------------

解析：

那么在这里，因为数组元素我们并不确定，所以只能将数组的第一个元素看成是一个有序的序列，所以从数组的第二个元素开始才是我们需要去寻找插入位置的元素。所以外层循环从1开始，然后将arr\[i\]，也就是当前的第二个元素先保存起来，然后找到待插入元素的前一个元素下标，也就是i-1，此时通过一个while循环去比较。  
当insertIndex小于0时应该退出循环，因为此时已经与前面的所有元素比较完毕。在比较的过程中，如果待插入元素小于前一个元素，就将前一个元素后移，也就是将前一个元素的值直接赋值给待插入元素位置。因为在最开始已经将待插入元素进行了保存，所以只需将待插入元素的值赋值给它的前一个元素即可。因为在while循环中insertIndex执行了自减操作，所以它的前一个元素下标应为insertIndex + 1。而如果待插入的元素值大于前一个元素，那么就不会进入while循环，这样insertIndex + 1之后的位置仍然是自己所在的位置，所以赋值后值不改变，后面的操作以此类推。

--------------------

Java实现：

@Test
        public void Test(){ 
            int[] arr = {  3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
            for (int i = 1; i < arr.length ; i++) { 
                //定义要插入的数
                int insertValue = arr[i];
                //找到待插入数的前一个数的下标
                int insertIndex = i - 1;
                // 如果还有前一个数 并且 待插入元素小于前一个元素，就将前一个元素后移，
                // 也就是将前一个元素的值直接赋值给待插入元素位置。
                while(insertIndex >= 0 && insertValue < arr[insertIndex]){ 
                    arr[insertIndex + 1] = arr[insertIndex];
                    insertIndex--;
                }
                //找到了待插入的位置，赋值
                arr[insertIndex + 1] = insertValue;
            }
            System.out.println(Arrays.toString(arr));
        }

![在这里插入图片描述][d6a9702a20904edb82809a7593541535.png]

## 5、希尔排序 ##

希尔排序(Shell’s Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。  
![在这里插入图片描述][c0632571dedb4543a97902ab1bcb5065.gif]

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 5]

--------------------

解析：

那么在上面的程序段中，数组长度为15，所以在第一轮，数组被分为了15 / 2 = 7个小组，然后分别对每个小组的元素进行遍历。在第一轮中小组之间的元素间隔都为7，所以分成的小组数其实也就是元素之间的间隔。接着就可以对每个小组的元素进行比较，然后进行交换，接下来以此类推。

--------------------

Java实现：

@Test
        public void Test(){ 
            int[] arr = {  3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
            for (int gap = arr.length / 2; gap > 0; gap /= 2) { 
                // 对数组元素进行分组
                for (int i = gap; i < arr.length; i++) { 
                    // 遍历各组中的元素
                    for (int j = i - gap; j >= 0; j -= gap) { 
                        // 交换元素
                        if (arr[j] > arr[j + gap]) { 
                            int temp = arr[j];
                            arr[j] = arr[j + gap];
                            arr[j + gap] = temp;
                        }
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }

![在这里插入图片描述][c65b46f0ecc44bf9a3c02cbdb258f9c6.png]

## 6、快速排序 ##

快速排序（Quicksort）是对冒泡排序的一种改进。  
快速排序由C. A. R. Hoare在1960年提出。它的基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。  
![在这里插入图片描述][ce0964ecfdc145889bddec670900154b.gif]

--------------------

解析：

快速排序的实现原理很简单，就是将原数组分成两部分，然后以中间值为标准，比它小的就放其左边，比它大的就放其右边，然后在左右两边又以相同的方式继续排序。

所以在代码实现过程中，首先要创建两个移动的变量，一个从最左边开始往右移动，一个从最右边开始往左移动，通过这两个变量来遍历左右两部分的元素。当发现左边有大于中间数的元素，右边有小于中间数的元素，此时就进行交换。当两个变量重合也就是相等的时候遍历结束，然后左右两部分作递归处理。

--------------------

Java实现：

@Test
        public void Test(){ 
            int[] arr = {  3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
            quickSort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void quickSort(int[] arr, int left, int right) { 
            int l = left;// 左下标
            int r = right;// 右下标
            int pivot = arr[(left + right) / 2];// 找到中间的值
            // 将比pivot小的值放在其左边，比pivot大的值放在其右边
            while (l < r) { 
                // 在pivot左边寻找，直至找到大于等于pivot的值才退出
                while (arr[l] < pivot) { 
                    l += 1;// 将l右移一位
                }
                // 在pivot右边寻找，直至找到小于等于pivot的值才退出
                while (arr[r] > pivot) { 
                    r -= 1;// 将r左移一位
                }
                if (l >= r) { 
                    // 左右下标重合，寻找完毕，退出循环
                    break;
                }
                // 交换元素
                int temp = arr[l];
                arr[l] = arr[r];
                arr[r] = temp;
    
                //倘若发现值相等的情况，则没有比较的必要，直接移动下标即可
    
                // 如果交换完后，发现arr[l]==pivot，此时应将r左移一位
                if (arr[l] == pivot) { 
                    r -= 1;
                }
                // 如果交换完后，发现arr[r]==pivot，此时应将l右移一位
                if (arr[r] == pivot) { 
                    l += 1;
                }
            }
            // 如果l==r，要把这两个下标错开，否则会出现无限递归，导致栈溢出的情况
            if (l == r) { 
                l += 1;
                r -= 1;
            }
            // 向左递归
            if (left < r) { 
                quickSort(arr, left, r);
            }
            // 向右递归
            if (right > l) { 
                quickSort(arr, l, right);
            }
        }

![在这里插入图片描述][626527d6e15447e4bdca5ef851bacc36.png]

## 7、归并排序 ##

归并排序（MERGE-SORT）是建立在归并操作上的一种有效的排序算法,该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。

![在这里插入图片描述][a760477df29647f39efa43b50fa77a0f.gif]

归并排序使用了一种分治思想，分治思想的意思就是’分而治之"，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单地直接求解。

通过这个动图来看的话，相信很多人都一脸懵，没关系，我们通过静态图来分析一下：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 6]  
假设现在有一个待排序的序列，\[5，2，4，7，1，3，2，2\]，那么我们就需要将该序列进行分治，先将其分成两份：\[5，2，4，7\]和\[1，3，2，2\]，再将这两份分别分成两份：\[5，2\]和\[4，7\]；\[1，3\]和\[2，2\]，最后将这四部分再次分别分为两份，最后就将整个序列分为了八份。需要注意的是，在分的过程中，不需要遵循任何规则，关键在于归并，归并的过程中便实现了元素的排序。

--------------------

解析：

来分析一下吧，对于该排序算法，有两个部分组成，分解和合并。首先讲讲分解，在前面也说到了，我们需要将待排序的序列不停地进行分解，通过两个索引变量控制，一个初始索引，一个结尾索引。只有当两索引重合才结束分解。此时序列被分解成了十五个小份，这样分解工作就完成了。接下来是合并，合并操作也是最麻烦的，也是通过两个索引变量i，j。开始i在左边序列的第一个位置，j在右边序列的第一个位置，然后就是寻找左右两个序列中的最小值，放到新序列中，这时可能会出现一边的元素都放置完毕了，而另外一边还存在元素，此时只需将剩余的元素按顺序放进新序列即可，因为这时左右两边的序列已经是有序的了，最后将新序列复制到旧序列。这里也特别需要注意，因为合并的过程是分步的，而并非一次合并完成，所以数组的索引是在不断变化的。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 7]

--------------------

Java实现：

@Test
        public void Test(){ 
            int[] arr = {  3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };
            int[] temp = new int[arr.length];
            mergeSort(arr, 0, arr.length - 1, temp);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void mergeSort(int[] arr, int left, int right, int[] temp) { 
            // 分解
            if (left < right) { 
                int mid = (left + right) / 2;// 中间索引
                // 向左递归进行分解
                mergeSort(arr, left, mid, temp);
                // 向右递归进行分解
                mergeSort(arr, mid + 1, right, temp);// mid + 1，中间位置的后一个位置才是右边序列的开始位置
                // 每分解一轮便合并一轮
                merge(arr, left, right, mid, temp);
            }
        }
    
        /**
         * 合并的方法
         *
         * @param arr   待排序的数组
         * @param left  左边有序序列的初始索引
         * @param right 中间索引
         * @param mid   右边有序序列的初始索引
         * @param temp  做中转的数组
         */
        public static void merge(int[] arr, int left, int right, int mid, int[] temp) { 
            int i = left; // 初始化i，左边有序序列的初始索引
            int j = mid + 1;// 初始化j，右边有序序列的初始索引(右边有序序列的初始位置即为中间位置的后一个位置)
            int t = 0;// 指向temp数组的当前索引，初始为0
            // 先把左右两边的数据(已经有序)按规则填充到temp数组
            // 直到左右两边的有序序列，有一边处理完成为止
            while (i <= mid && j <= right) { 
                // 如果左边有序序列的当前元素小于或等于右边有序序列的当前元素，就将左边的元素填充到temp数组中
                if (arr[i] <= arr[j]) { 
                    temp[t] = arr[i];
                    t++;// 索引后移
                    i++;// i后移
                } else { 
                    // 反之，将右边有序序列的当前元素填充到temp数组中
                    temp[t] = arr[j];
                    t++;// 索引后移
                    j++;// j后移
                }
            }
            // 把有剩余数据的一边的元素填充到temp中
            while (i <= mid) { 
                // 此时说明左边序列还有剩余元素
                // 全部填充到temp数组
                temp[t] = arr[i];
                t++;
                i++;
            }
            while (j <= right) { 
                // 此时说明左边序列还有剩余元素
                // 全部填充到temp数组
                temp[t] = arr[j];
                t++;
                j++;
            }
            // 将temp数组的元素复制到原数组
            t = 0;
            int tempLeft = left;
            while (tempLeft <= right) { 
                arr[tempLeft] = temp[t];
                t++;
                tempLeft++;
            }
        }

![在这里插入图片描述][35e8b2e2755b41eb99b38457f3b133f2.png]

## 8、基数排序 ##

基数排序（radix sort）属于“分配式排序”（distribution sort），又称“桶子法”（bucket sort）或bin sort，顾名思义，它是透过键值的部份资讯，将要排序的元素分配至某些“桶”中，藉以达到排序的作用，基数排序法是属于稳定性的排序，其时间复杂度为O(nlog( r )m)，其中r为所采取的基数，而m为堆数，在某些时候，基数排序法的效率高于其它的稳定性排序法。基数排序是用空间换时间的经典算法。

![在这里插入图片描述][20190824161404812.png]

--------------------

解析：

将所有待比较的数值统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序，这样从最低位排序一直到最高位排序完成以后，数列就变为了一个有序序列。

--------------------

Java实现：

public static void raixSort(int[] arr) { 
    		// 第一轮(针对每个元素的个位进行排序处理)
    
    		// 定义一个二维数组，模拟桶，每个桶就是一个一维数组
    		// 为了防止放入数据的时候桶溢出，我们应该尽量将桶的容量设置得大一些
    		int[][] bucket = new int[10][arr.length];
    		// 记录每个桶中实际存放的元素个数
    		// 定义一个一维数组来记录每个桶中每次放入的元素个数
    		int[] bucketElementCounts = new int[10];
    
    		for (int j = 0; j < arr.length; j++) { 
    			// 取出每个元素的个位
    			int digitOfElement = arr[j] % 10;
    			// 将元素放入对应的桶中
    			// bucketElementCounts[digitOfElement]就是桶中的元素个数，初始为0，放在第一位
    			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    			// 将桶中的元素个数++
    			// 这样接下来的元素就可以排在前面的元素后面
    			bucketElementCounts[digitOfElement]++;
    		}
    		// 按照桶的顺序取出数据并放回原数组
    		int index = 0;
    		for (int k = 0; k < bucket.length; k++) { 
    			// 如果桶中有数据，才取出放回原数组
    			if (bucketElementCounts[k] != 0) { 
    				// 说明桶中有数据，对该桶进行遍历
    				for (int l = 0; l < bucketElementCounts[k]; l++) { 
    					// 取出元素放回原数组
    					arr[index++] = bucket[k][l];
    				}
    			}
    			// 第一轮处理后，需要将每个bucketElementCounts[k]置0
    			bucketElementCounts[k] = 0;
    		}
    		System.out.println("第一轮:" + Arrays.toString(arr));
    
    		// ----------------------------
    
    		// 第二轮(针对每个元素的十位进行排序处理)
    		for (int j = 0; j < arr.length; j++) { 
    			// 取出每个元素的十位
    			int digitOfElement = arr[j] / 10 % 10;
    			// 将元素放入对应的桶中
    			// bucketElementCounts[digitOfElement]就是桶中的元素个数，初始为0，放在第一位
    			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    			// 将桶中的元素个数++
    			// 这样接下来的元素就可以排在前面的元素后面
    			bucketElementCounts[digitOfElement]++;
    		}
    		// 按照桶的顺序取出数据并放回原数组
    		index = 0;
    		for (int k = 0; k < bucket.length; k++) { 
    			// 如果桶中有数据，才取出放回原数组
    			if (bucketElementCounts[k] != 0) { 
    				// 说明桶中有数据，对该桶进行遍历
    				for (int l = 0; l < bucketElementCounts[k]; l++) { 
    					// 取出元素放回原数组
    					arr[index++] = bucket[k][l];
    				}
    			}
    			// 第二轮处理后，需要将每个bucketElementCounts[k]置0
    			bucketElementCounts[k] = 0;
    		}
    		System.out.println("第二轮:" + Arrays.toString(arr));
    
    		// ----------------------------
    
    		// 第三轮(针对每个元素的百位进行排序处理)
    		for (int j = 0; j < arr.length; j++) { 
    			// 取出每个元素的百位
    			int digitOfElement = arr[j] / 100 % 10;
    			// 将元素放入对应的桶中
    			// bucketElementCounts[digitOfElement]就是桶中的元素个数，初始为0，放在第一位
    			bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];
    			// 将桶中的元素个数++
    			// 这样接下来的元素就可以排在前面的元素后面
    			bucketElementCounts[digitOfElement]++;
    		}
    		// 按照桶的顺序取出数据并放回原数组
    		index = 0;
    		for (int k = 0; k < bucket.length; k++) { 
    			// 如果桶中有数据，才取出放回原数组
    			if (bucketElementCounts[k] != 0) { 
    				// 说明桶中有数据，对该桶进行遍历
    				for (int l = 0; l < bucketElementCounts[k]; l++) { 
    					// 取出元素放回原数组
    					arr[index++] = bucket[k][l];
    				}
    			}
    			// 第三轮处理后，需要将每个bucketElementCounts[k]置0
    			bucketElementCounts[k] = 0;
    		}
    		System.out.println("第三轮:" + Arrays.toString(arr));
    	}

## 9、堆排序 ##

[https://blog.csdn.net/qq\_45173404/article/details/116090861][https_blog.csdn.net_qq_45173404_article_details_116090861]

--------------------

堆是具有以下性质的完全二叉树：  
每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆（没有要求结点的左孩子的值和右孩子的值的大小关系）

arr[i] >= arr[2*i+1] && arr[i] >= arr[2*i+2]  //i对应第几个节点，i从0开始编号

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 8]  
我们对堆中的结点按层进行编号，映射到数组中就是下面这个样子：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 9]  
堆排序基本思想：

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

一般升序采用大顶堆，降序采用小顶堆。

--------------------

> 步骤一：构造初始堆，将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)

原始的数组 \[4, 6, 8, 5, 9\]

1、假设给定无序序列结构如下  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 10]  
2、此时我们从最后一个非叶子结点开始（叶结点不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 11]  
3、找到第二个非叶节点 4，由于\[4,9,8\]中 9 元素最大，4 和 9 交换

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 12]  
4、这时，交换导致了子根\[4,5,6\]结构混乱，继续调整，\[4,5,6\]中 6 最大，交换 4 和 6

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 13]  
此时，我们就将一个无序序列构造成了一个大顶堆。

> **步骤二：将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换**

1、将堆顶元素 9 和末尾元素 4 进行交换  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 14]

2、重新调整结构，使其继续满足堆定义  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 15]  
3、再将堆顶元素 8 与末尾元素 5 进行交换，得到第二大元素 8  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 16]  
4、后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 17][]

--------------------

Java实现：

import java.util.Arrays;
    
    public class HeapSort { 
        public static void main(String[] args) { 
            int[] arr = { 3, 5, 2, 7, 8, 0, -1, 99};
            heapSort(arr);
            System.out.println(Arrays.toString(arr));
        }
    
        //堆排序
        public static void heapSort(int[] arr) { 
            //将无序序列构建成一个堆
            for (int i = arr.length / 2 - 1; i >= 0; i--) { 
                adjustHeap(arr, i, arr.length);
            }
            //将堆顶元素和末尾元素交换,将最大元素放置数组末端
            //重新调整至堆结构,然后继续将堆顶元素和当前末尾元素交换,以此往复
            for (int i = arr.length - 1; i > 0; i--) { 
                int temp = arr[i];
                arr[i] = arr[0];
                arr[0] = temp;
                adjustHeap(arr, 0, i);
            }
        }
    
        /**
         * 将二叉树调整为堆
         *
         * @param arr    待调整的数组
         * @param i      表示非叶子结点在数组中索引
         * @param length 表示对多少个元素继续调整,length逐渐减少
         */
        public static void adjustHeap(int[] arr, int i, int length) { 
            int temp = arr[i];
            //k=2i+1是i的左子节点
            for (int k = i * 2 + 1; k < length; k = k * 2 + 1) { 
                if (k + 1 < length && arr[k] < arr[k + 1])//左子节点的值<右子节点的值
                    k++;//指向右节点
                if (arr[k] > temp) { //如果子结点的值>父节点的值
                    arr[i] = arr[k];//将较大的值赋给当前节点
                    i = k;//i指向k,继续循环比较
                } else
                    break;
            }
            //for循环后,已经将以i为父结点的树的最大值,放在了顶部
            arr[i] = temp;//将temp值放到调整后的位置
        }
    }

--------------------

参考

> [程序员那些必须掌握的排序算法上][Link 1]  
> [程序员那些必须掌握的排序算法下][Link 2]  
> [数据结构——八大排序算法][https_blog.csdn.net_qq_45173404_article_details_116090861]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70]: /images/20220829/1999076c419441f08458cc1430aa78cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 1]: /images/20220829/0e86ace3f0fc4e2b8151b0548274633b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 2]: /images/20220829/6d57d679320044248393d63c0d7706d6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 3]: /images/20220829/61afce1467ba40ac9607b853fafd6675.png
[f6b450e063f249bc95c15df33bd84fdc.gif]: /images/20220829/c83635b9ac6b46349f1199a19c23543a.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 4]: /images/20220829/b174fe0a77674838b1d2953fcb4c935d.png
[e3276ef34c154ae4a19c284d09c6a191.gif]: /images/20220829/4c3df116df9547fdbca754a817a591f8.png
[5a45527c45f4411cbc6a844b3a94fccb.png]: /images/20220829/1d5512e7b98c46a3958449da541335f9.png
[ddce4349f54e40da8b712a27a9add3ec.gif]: /images/20220829/c94d6b041b334a1f9ad30486df243c92.png
[d6a9702a20904edb82809a7593541535.png]: /images/20220829/d17cf31f1a304c4da22fad52088a371e.png
[c0632571dedb4543a97902ab1bcb5065.gif]: /images/20220829/8647f931141a4b43a0f2aa96cbf45b29.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 5]: /images/20220829/43ecb18e5b174b578283720d9f970c9d.png
[c65b46f0ecc44bf9a3c02cbdb258f9c6.png]: /images/20220829/6c2e775471d2475393a987987a28cb37.png
[ce0964ecfdc145889bddec670900154b.gif]: /images/20220829/5648014657fc4a7684fbc84f338ab86c.png
[626527d6e15447e4bdca5ef851bacc36.png]: /images/20220829/6566c073ea8a46e59c892b75ae6576b4.png
[a760477df29647f39efa43b50fa77a0f.gif]: /images/20220829/5481da6bf1ba4fa49518a8888216e577.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 6]: /images/20220829/c3087c2765c0457ab709b4675fb6b9b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 7]: /images/20220829/a3b2a89a82b540fd926f695aff8696ac.png
[35e8b2e2755b41eb99b38457f3b133f2.png]: /images/20220829/a9c1a423a95e4d82ad6ba9882f84fa5c.png
[20190824161404812.png]: /images/20220829/16997412449b4abcacadc75833b9fe25.png
[https_blog.csdn.net_qq_45173404_article_details_116090861]: https://blog.csdn.net/qq_45173404/article/details/116090861
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 8]: /images/20220829/93468ced128e49a69d98337ec1a54083.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 9]: /images/20220829/af20d9f030b0427480e1d912a6265214.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 10]: /images/20220829/9858affea5424ef4a34d41a1294fed6d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 11]: /images/20220829/9bfed7616cf644abab70d2d54c5c5f70.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 12]: /images/20220829/9b44372728f1440d9fc9a35c0cf64b1b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 13]: /images/20220829/fa6dd0c763bc4bd39abb5b500f18b908.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 14]: /images/20220829/56c25e6e9b574514b38f54c9166434cf.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 15]: /images/20220829/d6207c5fe309450f8b03ba15e4006bc6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 16]: /images/20220829/0c0d73fc335b4439a5f19160fefc57d7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzQ1MjM0NTEw_size_16_color_FFFFFF_t_70 17]: /images/20220829/a638f854892b4b5d954b2016a62a73fe.png
[Link 1]: https://blog.csdn.net/qq_42453117/article/details/99680831
[Link 2]: https://blizzawang.blog.csdn.net/article/details/100036347