03.选择排序

选择排序

  • 1.基本思想
  • 2.排序过程
  • 3.代码实现
  • 4.如何优化
  • 5.复杂度
  • 6.使用场景

0.选择排序种类

  • 选择排序分为三种，直接选择排序、树形选择排序（锦标赛排序）、堆排序（大根堆、小根堆）。
  • 直接选择排序和堆排序是不稳定排序，树形选择排序是稳定排序。

1.直接选择排序

1.1 基本思想

  • 在长度为N的无序数组中，第一次遍历n-1个数，找到最小的数值与第一个元素交换；
  • 第二次遍历n-2个数，找到最小的数值与第二个元素交换；
  • 依此类推……
  • 第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成。

1.2 排序过程

  • 通过设置哨位，将哨位位置的数与哨位之后（包括哨位）的序列中最小的数进行交换，然后哨位递增，直到哨位到达数组中最后一个数为止。
  • image
    image

1.3 代码实现

  • 如下所示
    /*
 * 直接选择排序
 */
public static void selectSort1(int[] data) {
    int pos ;
    for (int i = 0; i < data.length; i++) {
        pos = i;
        // 找出从i开始，到数组末尾这段数组中最小的数，pos标志的是这个最小的数在数组中的位置
        for (int j = i + 1; j < data.length; j++) {
            if (data[j] < data[pos]) {
                pos = j;
            }
        }
        // 交换两个数的位置
        if(pos != i){
            int temp = data[i];
            data[i] = data[pos];
            data[pos] = temp;
        }
    }
    for(int i=0;i<data.length;i++){
        System.out.println("yc1-----" +data[i]);
    }
}

1.4 如何优化

  • 直接选择排序的最好时间复杂度和最差时间复杂度都是O(n²)，因为即使数组一开始就是正序的，也需要将两重循环进行完，平均时间复杂度也是O(n²)。
  • 空间复杂度为O(1)，因为不占用多余的空间。直接选择排序是一种原地排序（In-place sort）并且稳定（stable sort）的排序算法，优点是实现简单，占用空间小，缺点是效率低，时间复杂度高，对于大规模的数据耗时长。

1.5复杂度

  • 最好时间复杂度和最差时间复杂度都是O(n²)

2.树形选择排序（锦标赛排序）

2.1 基本思想

  • 树形选择排序利用满二叉树的性质，将待排序的数放入叶子节点中，然后同属于一个根节点的两个叶子节点相互比较，较小的叶子节点复制到其根节点，然后根节点之间再相互比较，直到整棵树的根节点，此时整棵树的根节点为待排序数组中最小的一个数，在下一次循环中要将这个数置为最大值，然后再开始循环，直到全部的数都被取出，排序完成。因为这种排序类似于比赛中的淘汰赛，所以又称之为锦标赛排序。

2.2 排序过程

  • 构造一棵满二叉树，要求可以将待排序数组全部放入叶子节点中
  • 将两个叶子节点中较小的数挪入根节点中，全部挪完之后，再将两个根节点中较小的数挪入它们的根节点中，直到整棵树的根节点。
  • 取出根节点中的数，将叶子节点中的这个数置为max，重复第二步，直到每个数都被取出过一次。

2.3 代码实现

  • 代码如下所示
    public static void treeSelectSort(int[] a){
    int len = a.length;
    int treeSize = 2 * len - 1;  //完全二叉树的节点数
    int low = 0;
    int[] tree = new int[treeSize];    //临时的树存储空间
    //由后向前填充此树，索引从0开始
    for(int i = len-1,j=0 ;i >= 0; --i,j++){      //填充叶子节点
        tree[treeSize-1-j] = a[i];
    }

    for(int i = treeSize-1;i>0;i-=2){ //填充非终端节点
        //noinspection unchecked
        tree[(i-1)/2] = ((Comparable)tree[i-1]).compareTo(tree[i]) < 0 ? tree[i-1]:tree[i];
    }

    //不断移走最小节点
    int minIndex;
    while(low < len){
        int min = tree[0];    //最小值
        a[low++] = min;
        minIndex = treeSize-1;
        //找到最小值的索引
        //noinspection unchecked
        while(((Comparable)tree[minIndex]).compareTo(min)!=0){
            minIndex--;
        }
        tree[minIndex] = Integer.MAX_VALUE;  //设置一个最大值标志
        //找到其兄弟节点
        while(minIndex > 0){      //如果其还有父节点
            if(minIndex % 2 == 0){   //如果是右节点
                //noinspection unchecked
                tree[(minIndex-1)/2] = ((Comparable)tree[minIndex-1]).compareTo(tree[minIndex])
                        < 0 ? tree[minIndex-1]:tree[minIndex];
                minIndex = (minIndex-1)/2;
            }else{                   //如果是左节点
                //noinspection unchecked
                tree[minIndex/2] = ((Comparable)tree[minIndex]).compareTo(tree[minIndex+1])
                        < 0 ? tree[minIndex]:tree[minIndex+1];
                minIndex = minIndex/2;
            }
        }
    }


    for(int i=0;i<a.length;i++){
        System.out.println("yc1-----" +a[i]);
    }
}
贡献者: yangchong211