chapter_sorting/selection_sort/

[giscus[bot]]

chapter_sorting/selection_sort/

一本动画图解、能运行、可提问的数据结构与算法入门书

https://www.hello-algo.com/chapter_sorting/selection_sort/

[limuzi9806]

k神好，分别包含n,n-1,...,2,2轮内循环，是不是多了一个2呀

[limuzi9806]

k神，n-1轮外循环，分别包含的内循环不是n-1到1吗？i= 0时，j=1,j<n,循环n-1次？求和n(n-1)/2?

[krahets]

Hi @limuzi9806，第一轮未排序区间长度为 $n$ ，最后一轮未排序区间长度为 $2$ 因此内循环是从 $n$ 减小到 $2$ 。不过这里有些歧义，因为代码中看上去是从 $n - 1$ 减小到 $1$ ，这是因为没有计入初始化 $k$ 的那一轮。两种统计都可以，不影响结果～

[limuzi9806]

懂了，谢谢解答

[Tomatos03]

作者你好，我想问一下时间复杂度那里的计算，第一轮外循环对应的内循环执行次数不应该是n - 1吗?为什么是n呢？我不是很理解，能否帮我解答，十分感谢

[krahets]

@Tomatos03 Hi，两种都可以的，这个取决于是否计入初始化 k 的那一轮。

[HenryWD]

第三个特性 -- “非稳定排序”，在图例中显示了两个元素4的相对位置发生了改变。请问现实中什么时候会需要规避这种情况呢？

[krahets]

很好的问题！在现实中，我们有可能是在对象的某个属性上进行排序。例如，学生有姓名和身高两个属性，我们希望实现一个多级排序：

先按照姓名进行排序：

(A, 180) (B, 185) (C, 170) (D, 170)

接下来对身高进行排序：

(D, 170) (C, 170) (A, 180) (B, 185)

由于排序算法不稳定，学生 D 和 C 的位置发生了交换，姓名的有序性被破坏了，而这是我们不希望看到的。

[cylovecode]

俺也看过一个发挥稳定性用途的例子：假设有一批二手房供挑选，可以先对这批二手房按总价由低到高排序，排完序后发现有一些总价相同的房子，但是面积不同。如果需要再按面积由小到大排序排序，此时若采用稳定性的排序算法，就可以使得面积相同的房子中，总价最低的房子排在前面。

[amlei]

Excel 的排序功能便是如此！相对于 Excel 来说它的排序功能则是稳定性的

姓名	身高
C	170
D	170
A	180
B	185

[neil4dong]

如果排序的时候判断是更小才交换，那么是不是就可以实现为稳定排序呢

[amlei]

如果排序的时候判断是更小才交换，那么是不是就可以实现为稳定排序呢

我认为判断更小无法解决其非稳定性排序。

上面一位举的例能很好理解如何解决非稳定性排序的算法思路

俺也看过一个发挥稳定性用途的例子：假设有一批二手房供挑选，可以先对这批二手房按总价由低到高排序，排完序后发现有一些总价相同的房子，但是面积不同。如果需要再按面积由小到大排序排序，此时若采用稳定性的排序算法，就可以使得面积相同的房子中，总价最低的房子排在前面。

[cylovecode]

k神，我觉得最后一步交换元素可以有个小优化，在交换前判断 $k$ 是否有变化，无变化则无需交换。这样的话当数组大致有序时，能够减少无效交换带来的开销。

[krahets]

这种优化，前后差别不大哈。在数组倒序时，会增加 $n-1$ 次判断操作。

[cylovecode]

哈哈有道理

[DXShelley]

// 将该最小元素与未排序区间的首个元素交换
int temp = nums[i];
nums[i] = nums[k];
nums[k] = temp;

如果未排序区间第一个值就是最小的，即最小元素与未排序区间首个元素是同一个，是不是就不用swap了？

[krahets]

是的，不过区别不大

[liweijian199011]

代码里的注释感觉不是太准确。外层循环说是未排序区间内的，内层循环已经是从j=i+1开始了，前面这个i就不是未排序的区间吗？

[krahets]

未排序区间是 [i, n-1]（双闭区间），因此 i 也在未排序区间内。因为在找最小值，所以从从 i+1 开始和 i 比大小就足够了。

[liweijian199011]

多谢，理解了，思维一开始有点钻牛角尖了，只考虑排序区间的问题了。

[liweijian199011]

这个非自适应排序要怎么理解？为什么是非自适应排序？

[krahets]

根据“排序效率与数据分布是否相关”来区分

[liweijian199011]

字面意思是懂了，能举个具体的例子吗？

[krahets]

例如，归并排序在任何数据下的时间复杂度都是 $O(n \log n)$ ；快速排序平均时间复杂度是 $O(n \log n)$ ，在某些特殊的输入数据下（例如完全倒序）时间复杂度为 $O(n^2)$ 。这个你看完后面的各个具体排序算法，就会理解啦

[winCookie]

最后一个例子，是否可以更换一下呢？4 4 3 1 5 2，完整的排序后，4 4的相对位置没有发生改变。可以改为3 4 4 3 2例子。

[krahets]

很细心噢！

[xiaolongtang]

你好，关于java的例子，外层的循环，应该是 i<n，这样循环的区间就已经是[0, n-1]，或者是 i<=n-1

[krahets]

Hi，i = n-1 是不需要的，因为只剩下一个元素了，天然有序。外循环只需要 $i \in [0, n-2]$ 即可。

[xiaolongtang]

明白了，谢谢解答，十分感谢

[CCCCCC777]

到这里我已经看得很吃力了，不是说看不懂就是感觉有一个屏障突破不了可能之前的一些代码没看，落下的债，先去写写题，看看视频，积累一些零碎的东西，过几天再来看，写blog的时候网站崩了，写的都清0我的心态也崩了，ok就这样，作者加油

[travonf]

多练几遍熟悉就好了，主要是理解思想，代码都很短，记不住也没关系。

[2419174660]

选择排序的不稳定性，这张示例图体现不出来，不稳定性应该是左边的数导致的，而不是因为后面的两个数。

[2419174660]

也不是说体现不出来，只是不太直观，需要多次变换才能看出来。如果换成 23 2 145或许能一眼看出不稳定性

[zzj46]

代码理解上看：复杂度求和应该是是,n(n-1)/2, 原句应改为：”即各轮外循环分别包含 n-1,n-2...........1轮内循环，求和为 n(n-1)/2

[xiaotuanyu120]

python中，[0, n-1]不应该是range(n)吗？

[Milesatgl]

i是从0变到n-2（倒数第二个元素），j是从i+1变到n-1（最后一个元素）

[zhangxp93]

感觉这个手动选择排序太麻烦，了解就够了

[checkma-xh]

def sort(nums):
    for i in range(len(nums) - 1):
        min_idx = i
        
        for j in range(i + 1, len(nums)):
            if nums[j] < nums[min_idx]:
                min_idx = j

        nums[i], nums[min_idx] = nums[min_idx], nums[i]
    
    return nums


sort([1,3,32,4,1,-100,23,17,23,6,-7,2,9,-1000])

[dusk406]

// 选择排序
// 思想：每次循环记录最小值的下标，然后把它交换到前面去

void select_sort(int *arr, int length) {
	int min, t;
	for (int i = 0; i < length; i++) {
		min = i;
		for (int j = i + 1; j < length; j++) {
			// 如果找到比 min 还小的数就交换
			if (arr[j] < arr[min]) {
				min = j;
			}
		}
		t = arr[min], arr[min] = arr[i], arr[i] = t;
	}
}

[Jcl-Jay]

稍微提升了一点性能的选择排序

def optimized_selection_sort(array: list[int]):
n = len(array)
for i in range(n // 2):
min_idx = i
max_idx = i
for j in range(i + 1, n - i):
if array[j] < array[min_idx]:
min_idx = j
elif array[j] > array[max_idx]:
max_idx = j
# 交换最小值到前面
if min_idx != i:
array[i], array[min_idx] = array[min_idx], array[i]
# 如果最大值索引是 i，需更新为 min_idx 的位置，因为前一步交换了最小值和i
if max_idx == i:
max_idx = min_idx
# 交换最大值到后面倒数第(i+1)位
if max_idx != n - i - 1:
array[n - i - 1], array[max_idx] = array[max_idx], array[n - i - 1]