真人做爰视频网站免费/seo搜索引擎优化包邮

选择排序

1 算法思想

选择排序是通过比较来决定元素间的相对次序，由于其时间复杂度不能突破O(nlogn)，因此属于非线性时间比较类排序中的交换排序。

• 首先在未排序序列中找到最小(大)值：初始假定第一位为最小(大)值，用一个指针min_index记录其下标，遍历第一位后面的所有元素，与第一位比较，如果有元素比temp所指元素小(大)，就更新min_index。
• 每次遍历完成都会找到一个最小(大)值，将这个最值与未排序列的第一位交换位置。
• 重复第这两步，直到所有元素均排序完毕。
• 最后一位没有其他元素可以与其交换，所以遍历到最后一位时自己就是最值，不需要再进行遍历。
• 和冒泡排序相比性能提升，因为冒泡排序在一次遍历中可能需要交换多次数据然后固定一位，选择排序一次遍历只需要交换一次就可以固定一位。

def selectionSort(nums):n = len(nums)# 寻找未排序列[i,n-1]里的最小值for i in range(n - 1):# 初始假定nums[i]为最小值min_index = i# [i, n-1]中的值和nums[min_index]比较，更新指针min_indexfor j in range(i, n):if nums[j] < nums[min_index]:min_index = j# 交换未排序序列的第一位和最值nums[min_index]if min_index != i:nums[i], nums[min_index] = nums[min_index], nums[i]return nums

2 复杂度

时间复杂度：O(n^2)

空间复杂度：O(1)，在原数组空间内操作，需要的额外空间是指针空间

3 稳定性

不稳定：

• 如果待排序列中有两个相同的数a、b，最右边的数b的右边所有的数都比ab大，则不会出现不稳定情况，如[3, 2-a, 2-b, 4, 5]，第一次交换后[2-a, 3, 2-b, 4, 5]，第二次交换后[2-a, 2-b, 3, 4, 5]，最终结果a和b保持原来的相对顺序。
• 如果待排序列中的两个相同数a、b，最右边的数b的右边的所有数中有比ab小的数，在一次交换中可能会将a交换到b的右边。比如[3, 5-a, 7, 5-b, 2]，第二次交换后[2, 3, 7, 5-b, 5-a]，最终结果[2, 3, 5-b, 5-a, 7]，a和b不能保持原来的相对顺序。

4 优化

上述方法在一次遍历后找到一个最值，既然这次遍历必不可少，我们希望在一次遍历中尽可能多的确定数字。所以我们可以使用二元选择排序，即在一次遍历中，找到最大值和最小值，将两个最值放到数组的两端，然后再递归处理夹在两个最值中间的待排数组。

• 因为我们每次可以确定两个位置的数字，所以我们只需要遍历数组的一半，即 (0, n//2)。
• 初始假定待排数组的正数第一位 i 为最小值，倒数第一位 n-i-1 为最大值，然后遍历整个数组(包括i和 n-i-1)，找到待排数组中的最大最小值，更新指针 min_index和 max_index。
• 如果待排序列中最大最小值相等nums[min_index] == nums[max_index]，证明这段序列所有元素都相等，不用继续比较，结束排序。
• 如果最大最小值不相等，判断最小值nums[min_index]是否和待排序列第一位 nums[i] 重合，如果是，不用交换，如果不是，则交换两个数字。
• 如果此时待排序列的第一位 nums[i] 刚好是最大值，在上一步第一位 nums[i]和最小值 nums[min_index] 交换后，这个第一位不再是最大值，最大值转移到了指针为min_index处，所以应该再次更新一下最大值指针 max_index = min_index。
• 如果待排序列的倒数第一位 nums[n-i-1]是最小值呢？如果先交换的是最小值，在交换 nums[i] 和 nums[n-i-1] 后，不影响最大值nums[max_index] 和 nums[n-i-1] 的交换。如果先交换的是最大值，那交换后 n-i-1 处就不再是最小值，就会影响最小值的交换。所以先进行交换的要处理这个特殊情况。

def selectionSort(nums):n = len(nums)for i in range(n//2):min_index = imax_index = n - i - 1for j in range(i, n-i):if nums[j] < nums[min_index]:min_index = jif nums[j] > nums[max_index]:max_index = jif nums[min_index] == nums[max_index]:breakif min_index != i:nums[i], nums[min_index] = nums[min_index], nums[i]if i == max_index:max_index = min_indexif max_index != n - i - 1:nums[n-i-1], nums[max_index] = nums[max_index], nums[n-i-1]return nums