【数据结构】选择排序

⭐ 作者：小胡_不糊涂
🌱 作者主页：小胡_不糊涂的个人主页
📀 收录专栏：浅谈数据结构
💖 持续更文，关注博主少走弯路，谢谢大家支持 💖

1. 直接选择排序

基本思想： 先在元素集合array[0]–array[n]中选择关键码最小(大)的数据元素，若它不是这组元素中的第一个(第一个)元素，则将它与这组元素中的第一个（第一个）元素交换，然后在剩余的array[1]–array[n]集合中，重复上述步骤，直到集合剩余1个元素。

代码实现：

/**
     * 选择排序：
     * 时间复杂度：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;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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;
            }
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

第二步：排序

/**
     * 时间复杂度：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--;
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18