---

选择排序

选择排序：每次从无序区间中选择一个最大或最小值，存放在无序区间的最前或最后的位置（此位置的元素已经有序），直到所有的数据都排序完成为止。

选择排序的时间复杂度为O(n^2)，空间复杂度为O(1)，并且它是不稳定的排序算法！

选择排序动图如下：

代码如下：

public static void selectionSort(int[] arr){
        //无序区间[i,arr.length)  有序区间[0,i)
        for (int i = 0; i < arr.length; i++) {
            int min=i;
            for (int j = i+1; j < arr.length; j++) {
                if (arr[j] < arr[min]){
                    min=j;
                }
            }
            //此时min代表无序区间中最小值的索引
            swap(arr,i,min);
        }
    }
    public static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

双向选择排序

双向选择排序：一次排序过程中同时选出最大和最小值，放在无序区间的最后和最前面。

代码如下：

public static void selectionSortOP(int[] arr){
        int left=0;
        int right= arr.length-1;
        while (left<=right){
            int min=left;
            int max=left;
            for (int i = left+1; i <=right ; i++) {
                if (arr[i]<arr[min]){
                    min=i;
                }
                if (arr[i]>arr[max]){
                    max=i;
                }
            }
            swap(arr,left,min);
            //如果此时max恰好等于left，最大值已经被换到min去了
            //例如：[5,4,3,2,1]
            if (max==left){
                max=min;
            }
            swap(arr,right,max);
            left++;
            right--;
        }
    }
    public static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
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
27
28
29
30

堆排序

堆排序：堆排序是指利用堆这种数据结构所设计的一种排序算法，它是选择排序的一种，它是通过堆来选择数据的。当要排升序的时候建立最大堆，排降序时建立最小堆。

堆排序的时间复杂度为O(nlogn)，空间复杂度为O(1)，是一个不稳定的排序算法！

以最大堆为例：

1. 将数组堆化，调整成最大堆，从最后一个非叶子节点开始进行siftDown操作；
2. 然后交换堆顶元素和最后一个元素，使末尾元素最大；
3. 继续调整堆，再将堆顶元素与堆最后一个元素进行交换，得到第二大元素；
4. 重复2和3，直到数组有序。

代码如下：

public static void heapSort(int[] arr){
        //1.先将arr调整为最大堆，从最后一个非叶子节点开始进行siftDown操作
        for (int i = (arr.length-1-1)/2; i >=0 ; i--) {
            siftDown(arr,i,arr.length);
        }
        //此时arr已经被调整为最大堆
        for (int i = arr.length-1; i > 0 ; i--) {
            //2.交换arr[0]和最后一个元素，此时最大值位于最后
            swap(arr,0,i);
            //3.然后继续调整堆
            siftDown(arr,0,i);
        }
    }
    public static void siftDown(int[] arr,int i,int len){
        //判断当前节点是否存在左子树
        while (2*i+1 < len){
            //定义k为当前节点的左子树
            int k=2*i+1;
            //如果此时当前节点右子树也存在，并且右子树的值大于左子树的值，更新k
            if (k+1<len && arr[k+1]>arr[k]){
                k=k+1;
            }
            //然后将当前节点和其左右子树的最大值进行比较
            if (arr[i]>arr[k]){
                break;
            }else {
                swap(arr,i,k);
                i=k;
            }
        }
    }
    public static void swap(int[] arr,int i,int j){
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
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
27
28
29
30
31
32
33
34
35
36

---

总结

以上就是今天要讲的内容，本文介绍了选择排序中的选择排序和堆排序。