​
​

活动地址：CSDN21天学习挑战赛

📡选择排序是什么

给定 一个的大小为N的数组和L=0，选择排序将：
在 [L … N-1] 范围内找出最小项目 X 的位置，
用第 L 项交换第 X 项，
进行下一步
在 [L++ … N-1] 范围内找出最小项目 X 的位置
用第 L 项交换第 X 项，
直到 L = N-2。

简单来说就是每次找到数组中的最小数,把最小数依次放在最前面

🎆选择排序代码

void selectionSort(int a[]) {
	for (int i = 0; i < arr.length - 1; i++) {
            int min = i;
            // 每轮需要比较的次数 N-i
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[min]) {
                    // 记录目前能找到的最小值元素的下标
                    min = j;
                }
            }

            // 将找到的最小值和i位置所在的值进行交换
            if (i != min) {
                int tmp = arr[i];
                arr[i] = arr[min];
                arr[min] = tmp;
            }
        }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

🏆时间复杂度分析

最坏情况为最小数都在最后,需要遍历数组n次，因此
时间复杂度为O(n²)

​

🥇堆排序

堆的定义

1.堆是一棵完全二叉树
小根堆：任何子树的最小值是它的头节点
大根堆：同理，任何子树的最大值是它的头节点。
我们可以使用一个数组表示堆
当头结点为i时,左节点为 2i+1,右节点 为2i+2,父节点 为(i-1)/2
我们可以使用系统的堆PriorityQueue(优先队列),没设置比较器的时候为小根堆
具体的可以看之前的文章
大根堆(堆排序)

定义比较器

public static class heapComparator implements Comparator<比较的类型> {
		@Override
		public int compare(Info o1, Info o2) {
			return o1-o2;//升序
			//o2-o1 降序
		}

	}
1
2
3
4
5
6
7
8

创建优先级队列

PriorityQueue<Integer> heap = new PriorityQueue<>(new heapComparator());
1