面试题积累篇-简单算法（三）

Love The Way You Lie 2022-07-13 03:12 141阅读 0赞

**前面已经说完三种，下面接着说选择排序，在这里面包括两种：****选择排序、堆排序**

**选择排序：**

**这是一种比较简单的排序算法，工作原理是每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。**

**代码如下：**

package com.yang.algorithm.test;
    
    public class MergeSort {
        public static void main(String[] args) {
            int[] array = {1, 45, 20, 31, 78, 456, 123, 25, 32};
            System.out.println("排序之前：");
            for (int a : array) {
                System.out.print(a + " ");
            }
            selectSort(array);
            System.out.println("\n" + "排序之后：");
            for (int a : array) {
                System.out.print(a + " ");
            }
        }
    
        public static void selectSort(int[] array) {
            for (int i = 0; i < array.length; i++) {
                int min = array[i];
                int n = i;
                // 最小数的索引 
                for (int j = i + 1; j < array.length; j++) {
                    if (array[j] < min) {
                        // 找出最小的数 
                        min = array[j];
                        n = j;
                    }
                }
                /**
                 * 这个部分虽然放在if语句里也能得到正确的输出， 但是只要找到一个比最小数小的值就会执行一次 所以应该在最终确定后在执行该操作。
                 */
                array[n] = array[i];
                array[i] = min;
            }
        }
    }

**执行结果如下：**

**![Center][]**

**堆排序：**

**首先看一下堆的定义：**

**堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：  Key\[i\]<=key\[2i+1\]&&Key\[i\]<=key\[2i+2\]或者Key\[i\]>=Key\[2i+1\]&&key>=key\[2i+2\]  即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。  堆分为大顶堆和小顶堆，满足Key\[i\]>=Key\[2i+1\]&&key>=key\[2i+2\]称为大顶堆，满足 Key\[i\]<=key\[2i+1\]&&Key\[i\]<=key\[2i+2\]称为小顶堆。由上述性质可知大顶堆的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。**

**堆排序的思想：**

**利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。  
    其基本思想为(大顶堆)：  
    1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无序区；  
    2)将堆顶元素R\[1\]与最后一个元素R\[n\]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),且满足R\[1,2...n-1\]<=R\[n\];   
    3)由于交换后新的堆顶R\[1\]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，然后再次将R\[1\]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。  
    操作过程如下：  
     1)初始化堆：将R\[1..n\]构造为堆；  
     2)将当前无序区的堆顶元素R\[1\]同该区间的最后一个记录交换，然后将新的无序区调整为新的堆。**

**因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。**

**public class MergeSort \{ public static void main(String\[\] args) \{ int\[\] array = \{ 1, 45, 20, 31, 78, 456, 123, 25, 32 \}; System.out.println("排序之前："); for (int a : array) \{ System.out.print(a + " "); \} int arrayLength=array.length; //循环建堆 for(int i=0;i<arraylength-1 i="" buildmaxheap="" array="" arraylength-1-i="" swap="" array="" 0="" arraylength-1-i="" system="" out="" println="" n="" arrays="" tostring="" array="" system="" out="" println="" n="" for="" int="" a="" :="" array="" system="" out="" print="" a="" data="" 0="" lastindex="" public="" static="" void="" buildmaxheap="" int="" data="" int="" lastindex="" lastindex="" for="" int="" i="(lastIndex-1)/2;i">=0;i--)\{ //k保存正在判断的节点 int k=i; //如果当前k节点的子节点存在 while(k\*2+1<=lastIndex)\{ //k节点的左子节点的索引 int biggerIndex=2\*k+1; //如果biggerIndex小于lastIndex，即biggerIndex+1代表的k节点的右子节点存在 if(biggerIndex<lastIndex)\{ //若果右子节点的值较大 if(data\[biggerIndex\]<data\[biggerIndex+1\])\{ //biggerIndex总是记录较大子节点的索引 biggerIndex++; \} \} //如果k节点的值小于其较大的子节点的值 if(data\[k\]<data\[biggerIndex\])\{ //交换他们 swap(data,k,biggerIndex); //将biggerIndex赋予k，开始while循环的下一次循环，重新保证k节点的值大于其左右子节点的值 k=biggerIndex; \}else\{ break; \} \} \} \} //交换 private static void swap(int\[\] data, int i, int j) \{ int tmp=data\[i\]; data\[i\]=data\[j\]; data\[j\]=tmp; \} \}**

[Center]: /images/20220713/03d01527aed24ef4b54fcb0925cc3a81.png