【数据结构】选择排序

今天药忘吃喽~ 2024-04-23 20:31 83阅读 0赞

> ⭐ 作者：小胡\_不糊涂  
> ? 作者主页：[小胡\_不糊涂的个人主页][Link 1]  
> ? 收录专栏：[浅谈数据结构][Link 2]  
> ? 持续更文，关注博主少走弯路，谢谢大家支持 ?

#### 直接选择、堆排序 ####

*  1. 直接选择排序
 *  2. 堆排序

![在这里插入图片描述][b33774e78b064b659d80b933aa59b1c2.gif_pic_center]

## 1. 直接选择排序 ##

> **基本思想：** 先在元素集合array\[0\]–array\[n\]中选择关键码最小(大)的数据元素，若它不是这组元素中的第一个(第一个)元素，则将它与这组元素中的第一个（第一个）元素交换，然后在剩余的array\[1\]–array\[n\]集合中，重复上述步骤，直到集合剩余1个元素。  
> ![在这里插入图片描述][4f35db816bd142dbb346238e2c0143cb.png]  
> 代码实现：

/**
         * 选择排序：
         * 时间复杂度：O(n^2)
         * 空间复杂度：O(1)
         * 稳定性：不稳定的排序
         * @param array
         */
        public static void selectSort(int[] array){
        
            for(int i=0;i<array.length;i++){
        
                int minindex=i;
                for(int j=i+1;j<array.length;j++){
        
                    if(array[j]<array[minindex]){
        
                        minindex=j;
                    }
                }
                //交换元素
                int k=array[minindex];
                array[minindex]=array[i];
                array[i]=k;
            }
        }

## 2. 堆排序 ##

> 堆排序(Heapsort)是指利用堆积树（堆）这种数据结构所设计的一种排序算法，它是选择排序的一种。它是通过堆来进行选择数据。需要注意的是排升序要建大堆，排降序建小堆。

第一步：采用向下调整方法建大根堆

public static void createHeap(int[] array){
        
            for(int parent=(array.length-1-1)/2;parent>=0;parent--){
        
                shiftDown(array,parent,array.length);
            }
        }
        public static void shiftDown(int[] array,int parent,int length){
        
            int child=parent*2+1;//左孩子节点
            while(child<length){
        
                // 如果右孩子存在，找到左右孩子中较大的孩子,用child进行标记
                if(child+1<length && array[child]<array[child+1]){
        
                    child=child+1;
                }
    
                if(array[child]>array[parent]){
        
                    // 将双亲与较大的孩子交换
                    int k=array[child];
                    array[child]=array[parent];
                    array[parent]=k;
                    // parent中小的元素往下移动，可能会造成子树不满足堆的性质，因此需要继续向下调整
                    parent=child;
                    child=2*parent+1;
                }else{
        
                    break;
                }
            }
        }

第二步：排序

/**
         * 时间复杂度：O(N*logN)
         * 空间复杂度：O(1)
         * 稳定性：不稳定的排序
         * @param array
         */
        public static void heapSort(int[] array){
        
            createHeap(array);
            int end=array.length-1;
            while(end>0){
        
                int k=array[0];
                array[0]=array[end];
                array[end]=k;
                
                shiftDown(array,0,end);
                end--;
            }
        }

[Link 1]: https://blog.csdn.net/iLoyo_
[Link 2]: http://t.csdnimg.cn/pu3jy
[b33774e78b064b659d80b933aa59b1c2.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/b308611ae17c4278826839ee4702d390.gif
[4f35db816bd142dbb346238e2c0143cb.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/a4f814adcf3a4c84b0fc634b3fc86f98.png