时间空间复杂度分析--选择排序算法

时间空间复杂度分析–选择排序算法

大概说明

什么是选择排序算法？

选择排序算法是将每个数都和它后面的所有数进行比较，将最大或者最小的数放在当前位置的算法。

代码部分

public class select {
    public static void main(String[] args) {
       int[] arr = {79,3213,3,5,45,65};
       selectfFunction(arr);
       for (int i = 0; i < arr.length; i++) {
           System.out.println(arr[i]);
       }
    }

    public static void selectfFunction(int[] arr) {
       for (int i = 0; i < arr.length; i++) {
           for (int j = i + 1; j < arr.length; j++) {
               if (arr[j] < arr[i]) {
                   int temp = arr[j];
                   arr[j] = arr[i];
                   arr[i] = temp;
               }
           }
       }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

对它的时间复杂度分析&空间复杂度分析

先说时间复杂度：

影响它时间复杂度的就是这两个for循环

 for (int i = 0; i < arr.length; i++) {
           for (int j = i + 1; j < arr.length; j++) {
          
               }
           }
       }
1
2
3
4
5
6

第一个for循环执行了n次，而它内部嵌套了一个n-1次的循环，n(n-1),所以时间复杂度是 O($n^2$)

再来说说空间复杂度

空间复杂度因为创建的变量就是temp所以空间复杂度为O(1).