一个操作如果和样本的数据量没有关系,每次都是固定时间内完成的操作,就叫做常数操作
例如
因为数组是有序的,我们拿到数组上任意元素的时间都是固定的,这种就是常数操作
反例
因为链表是无序的,我们拿到某一个元素的时间可能是不一样的,这种操作就非常数操作了
算法时间复杂度时间复杂度为一个算法流程中,常数操作数量的一个指标。常用O(读作big O)来表述。具体来说,先要对一个算法流程非常熟悉,然后再去写出这个算法流程中,发生了多少常熟操作,进而总结出常数操作数量的表达式。
在表达式中,只要高阶项,不要低阶项,也不要高阶项的系数,剩余的部分如果为f(N)那么时间复杂度为O(f(N))。
选择排序现在我们已经初步认识了算法的时间复杂度,接下来我们就先了解排序算法
流程
每次遍历一个范围的数组,第一次遍历n次找出一个最小的数字和第0个做交换,第二次遍历n-1(排除第一个)次,找出剩下的元素最小的和第1个做交换……重复操作,这个每次都要循环一次数组某个范围的元素作比较,并作出交换操作,不难看出选择排序是O(N²)的时间复杂度
代码如下
package com.yuan.struck_data.sort;
public class SelectSortTest {
public static void selectSort(int[] arr) {
// 如果数组为空或者只有一个元素那么直接返回
if (arr == null || arr.length < 2) {
return;
}
// 先做一次 for遍历arr
for (int i = 0; i < arr.length; i++) {
// 假设每次第一个元素是最小的
int minIndex = i;
for (int j = i; j < arr.length; j++) {
// 如果遇到比当前下标小的数字就互换下标
minIndex = arr[j] < arr[minIndex] ? j : minIndex;
}
// 交换
swap(arr, i, minIndex);
}
}
public static void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
// 主方法
public static void main(String[] args) {
// 测试数组
int[] arr = {12, 123, 1, 12, 42, 543, 64, 3423, 24, 241, 123, 54, 47, 787};
// 调用排序
selectSort(arr);
for (int i : arr) {
System.out.println(i);
}
}
}
我是本篇的小编⚪⚪,大家工作或者开发中遇到Bug需要帮助,欢迎加wx:xmzl1988



