选择排序（多方式）

目录

直接选择排序

时空复杂度?

简单选择排序的特性

堆排序

时空复杂度

堆排序的特性总结

---

直接选择排序

基本思想：给定一个待排序的数组或列表，简单选择排序通过不断选择最小（或最大）元素，并将其放置到已排好序部分的末尾，从而逐步构建有序序列

实现步骤：1、记录无序数组的首尾元素坐标begin和end，同时利用maxi和mini记录每次比较过程中最大数和最小数的下标（只是下标而不是具体的数字，在一轮比较完成后才会进行数字的交换，而且由于是要选出每次比较的最大/小值，所以当一个数字的大小在下标为maxi和mini的元素之间时，maxi或mini的值不会改变），二者的初始值都是数组首元素下标0（这样从第一次开始比较时就能将maxi或者mini分开便于后续的比较）

2、我们在这里规定比较是“新元素”（初始新元素为数组首元素的下一个元素，所以要begin+1）与元素下标为maxi和mini之间的关系，第一次比较是“新数字89”与元素下标为maxi和mini之间的关系，89大于5，所以此时mini不变，但是maxi发生改变，它此时记录新的最大值下标（0->1）?

3、第二次比较，“新数字3”与元素下标为maxi和mini之间的关系，3小于5，所以此时mini改变，记录新的最小值下标（0->2）

4、?第三次比较，“新数字6”与元素下标为maxi和mini之间的关系，6大于3小于89，不算最大也不算最小，所以此时mini和maxi均不发生改变

5、?第四次比较，“新数字0”与元素下标为maxi和mini之间的关系，0小于3，所以此时mini改变，记录新的最小值下标（2->4）

5、?第五次比较，“新数字48”与元素下标为maxi和mini之间的关系，48大于0小于89，不算最大也不算最小，所以此时mini和maxi均不发生改变

6、?第六比较，“新数字12”与元素下标为maxi和mini之间的关系，12大于0小于89，不算最大也不算最小，所以此时mini和maxi均不发生改变

7、?第七次比较，“新数字2”与元素下标为maxi和mini之间的关系，2大于0小于89，不算最大也不算最小，所以此时mini和maxi均不发生改变

8、至此第一轮比较结束，此时将下标为maxi和mini元素分别与数组首尾元素交换位置

9、此外，为了避免由于代表最大值下标的maxi与begin相等，即在交换完a[mini]与a[begin]之后，a[mini]的位置被最大值覆盖，所以我们要在交换完后更新maxi的位置，将此时mini赋值给maxi，然后再去交换a[maxi]与a[end]（不需要考虑mini与maxi重合的问题，因为每次每次循环开始是它们都会被重置）

10、最后外面再多套一层while循环，保证不断缩小比较的范围，当begin与end相等时，整个序列就会变为有序序列：

//简单选择排序
void SelectSort(int* a, int n)
{
	int begin = 0, end = n - 1;

	while (begin < end)
	{
		int mini = begin, maxi = begin;
		for (int i = begin + 1; i <= end; ++i)
		{
			if (a[i] < a[mini])
			{
				mini = i;
			}

			if (a[i] > a[maxi])
			{
				maxi = i;
			}
		}

		Swap(&a[begin], &a[mini]);

		if (maxi == begin)
		{
			maxi = mini;
		}

		Swap(&a[end], &a[maxi]);

		++begin;
		--end;
	}
}

11、如果你觉得这种方法很难理解，那还是用之前的常见的简单选择排序吧：

void selectionSort(int arr[], int n) {
    int i, j, minIndex, temp;
    
    for (i = 0; i < n-1; i++) {
        minIndex = i;
        
        // 在剩余未排序部分找到最小元素的索引
        for (j = i+1; j < n; j++) {
            if (arr[j] < arr[minIndex]) {
                minIndex = j;
            }
        }
        
        // 将找到的最小元素与当前位置交换
        temp = arr[i];
        arr[i] = arr[minIndex];
        arr[minIndex] = temp;
    }
}

关于它的解释等有空了我会补上😭?

时空复杂度?

最坏时间复杂度：O（N^2）（一共需要进行 n-1 轮比较和交换操作。每一轮中，需要在剩余未排序的元素中找到最小/大的元素，并将其与当前位置进行交换，(n-1) + (n-2) + ... + 1 = (n^2 - n)/2?）

最好时间复杂度：O（N^2）（无论输入数据的初始顺序如何，简单选择排序都需要进行 n-1 轮比较和交换操作。在每一轮中，需要找到剩余未排序部分中的最小（或最大）元素，并将其与当前位置进行交换）

空间复杂度：O（1）

简单选择排序的特性

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 稳定性：不稳定

堆排序

堆的相关内容放在这里了：http://t.csdnimg.cn/XO9Qh

时空复杂度

最坏时间复杂度：O(N*logN)（我们将它们放在了链接中）

最好时间复杂度：O(N*logN)（输入序列已经是一个完全有序的大顶堆或小顶堆时（即满足所有父节点都比子节点大或小），不需要进行任何交换操作。但仍然需要对每个非叶子节点执行一次向下调整操作以保持树形结构性质）

空间复杂度：O(1)

堆排序的特性总结

1. 堆排序使用堆来选数，效率就高了很多
2. 稳定性：不稳定

~over~