21天经典算法之直接选择排序

​
​

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

专栏前言:

本专栏主要是算法训练，目的很简单。就是为了进厂
最近官方在组织 21 天挑战赛，趁此机会我也更新一下经典算法的文章
如果想一起“狂”或者交流，欢迎来私聊
还不快趁着这个机会来提升自己?

?排序算法介绍

排序算法是通过特定的算法因式将一组或多组数据按照既定模式进行重新排序。最终序列按照一定的规律进行呈现。

在排序算法中，稳定性和效率是我们经常要考虑的问题。

稳定性：稳定是指当两个相同的元素同时出现于某个序列之中，则经过一定的排序算法之后，两者在排序前后的相对位置不发生变化。

复杂度分析：
（1）时间复杂度：即从序列的初始状态到经过排序算法的变换移位等操作变到最终排序好的结果状态的过程所花费的时间度量。
（2）空间复杂度：就是从序列的初始状态经过排序移位变换的过程一直到最终的状态所花费的空间开销。

常见的排序算法分为以下几种：

?直接选择排序

原理

直接选择排序又称简单选择排序，是一种不稳定的排序方法。是选择排序中最简单一种。

基本思想是：第 i 趟排序再待排序序列 a[i]~a[n] 中选取关键码最小的记录，并和第 i 个记录交换作为有序序列的第 i 个记录。

代码实现

数组：nums[]
for(int i = 0; i < n - 1; ++i){ 
    int temp = i;
    for(int j = i + 1; j < n; ++j){
        if(nums[temp] > nums[j]){
            temp = j;
        }
    }
    if(temp != i){
        int swap = nums[i];
        nums[i] = nums[temp];
        nums[temp] = swap;
    }
}

复杂度分析

在直接选择排序中，共需要进行 n - 1 次选择和交换，每次选择需要进行 n - i 次比较 (1<=i<=n-1),而每次交换最多需要3次移动，因此，总的比较次数$C=(n\ast n-n)/2$。

时间复杂度：

不管待排序序列是按照所需规则还是反规则排列，元素都需要循环对比。所以它们的时间复杂度都相同。

• 最好的情况：$O(n^2)$。
• 最坏的情况：$O(n^2)$。
• 平均复杂度：$O(n^2)$。

空间复杂度：$O(1)$。仅需一个存储空间用于记录交换的临时存储单元，即空间复杂度为 $O(1)$。

由于在直接选择排序中存在着不相邻元素之间的互换，因此，直接选择排序是一种不稳定的排序方法。

?示例：

?算法实践

?
算法的整体思想已经在上面讲述了，下面直接使用一个例子来试试水。

直接选择排序

题目描述：

977.有序数组的平方

给你一个按 非递减顺序 排序的整数数组 nums，返回每个数字的平方组成的新数组，要求也按非递减顺序排序。

示例 1：

输入：nums = [-4,-1,0,3,10]
输出：[0,1,9,16,100]
解释：平方后，数组变为 [16,1,0,9,100]
排序后，数组变为 [0,1,9,16,100]

示例 2：

输入：nums = [-7,-3,2,3,11]
输出：[4,9,9,49,121]

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 已按 非递减顺序 排序

class Solution {
    public int[] sortedSquares(int[] nums) {
        for(int i = 0; i < nums.length; ++i){
            nums[i] = nums[i] * nums[i];
        }
        for(int i = 0; i < nums.length - 1; ++i){
            int temp = i;
            for(int j = i + 1; j < nums.length; ++i){
                if(nums[temp] > nums[j]){
                    temp = j;
                }
            }
            if(temp != i){
                int swap = nums[i];
                nums[i] = nums[temp];
                nums[temp] = swap;
            }
        }
        return nums;
    }
}

但是本题目中要求你用时间复杂度为 O(n) 的算法解决本问题，很显然我们的直接插入排序不符合要求。虽然可以做出来，但是会超时。所以如果你想提升，那么就赶快做做课后习题吧。

?课后习题

如果你觉得掌握了，那么赶快来实践一下吧

​