← 返回学习路线

SYSTEM

选择排序

Java基础选择排序system
src/content/notes/system/选择排序.md

选择排序

简单选择

选择排序(Selection-sort):一种简单直观的排序算法

算法描述:首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。以此类推,直到所有元素均排序完毕

实现思路:

  1. 控制选择几轮:数组的长度 - 1
  2. 控制每轮从当前位置开始比较几次
public class SelectSort {
    public static void main(String[] args) {
        int[] arr = {55, 22, 2, 5, 1, 3, 8, 5, 7, 4, 3, 99, 88};
        for (int i = 0; i < arr.length - 1; i++) {
            //获取最小索引位置
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[minIndex] > arr[j]) {
                    minIndex = j;
                }
            }
            //交换元素
            int temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
        System.out.println(Arrays.toString(arr));
    }
}

选择排序时间复杂度:

  • 数据比较次数:(N-1)+(N-2)+(N-3)+...+2+1=((N-1)+1)*(N-1)/2=N^2/2-N/2
  • 数据交换次数:N-1
  • 时间复杂度:N^2/2-N/2+(N-1)=N^2/2+N/2-1

根据大 O 推导法则,保留最高阶项,去除常数因子,时间复杂度为 O(N^2)


堆排序

堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法,堆结构是一个近似完全二叉树的结构,并同时满足子结点的键值或索引总是小于(或者大于)父节点

优先队列:堆排序每次上浮过程都会将最大或者最小值放在堆顶,应用于优先队列可以将优先级最高的元素浮到堆顶

实现思路:

  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,则整个排序过程完成

floor:向下取整

public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {55, 22, 2, 5, 1, 3, 8, 5, 7, 4, 3, 99, 88};
        heapSort(arr, arr.length - 1);
        System.out.println(Arrays.toString(arr));
    }

    //high为数组最大索引
    private static void heapSort(int[] arr, int high) {
        //建堆,逆排序,因为堆排序定义的交换顺序是从当前结点往下交换,逆序排可以避免多余的交换
        //i初始值是最后一个节点的父节点,如果参数是数组长度len,则 i = len / 2 -1
        for (int i = (high - 1) / 2; i >= 0; i--) {
            //调整函数
            sift(arr, i, high);
        }
        //从尾索引开始排序
        for (int i = high; i > 0; i--) {
            //将最大的节点放入末尾
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //继续寻找最大的节点
            sift(arr, 0, i - 1);
        }
    }

    //调整函数,调整arr[low]的元素,从索引low到high的范围调整
    private static void sift(int[] arr, int low, int high) {
        //暂存调整元素
        int temp = arr[low];
        int i = low, j = low * 2 + 1;//j是左节点
        while (j <= high) {
            //判断是否有右孩子,并且比较左右孩子中较大的节点
            if (j < high && arr[j] < arr[j + 1]) {
                j++;    //指向右孩子
            }
            if (temp < arr[j]) {
                arr[i] = arr[j];
                i = j;  //继续向下调整
                j = 2 * i + 1;
            } else {
                //temp > arr[j],说明也大于j的孩子,探测结束
                break;
            }
        }
        //将被调整的节点放入最终的位置
        arr[i] = temp;
    }
}

堆排序的时间复杂度是 O(nlogn)