常数时间的操作,常用o(读作 big o)来表示,叫做常数操作。
评价一个算法流程的好坏,先看时间复杂度的指标,再分析不同数据样本下的实际运行时间,也就是“常数项时间”。
a=a^b;//
b=a^b;//b=a^b^b=a
a=a^b;//a=a^b^a=b
从第一个数开始依次与前面的数比较,如果比前面的数小就交换,
对n个元素的无序集合进行插入排序,需要进行n-1趟排序,每第i趟排序需要进行i次比较,其时间复杂度也是O(n*n)。
int temp = array[1];
for (int i = 1; i < array.Length; i++)
{
temp = array[i];//array[i]是从没排序的拿出来去做比较的元素
for (int j = i-1;j>=0; j--)
{
if (temp<array[j])//array[j]是已经排序的当前被比较的元素,从后往前进行比较和交换
{
array[j+1] = array[j];
array[j] = temp;
}
}
}
冒泡排序是一种简单直观的排序算法,可以对一组无序的数据进行指定规则的排序。
如果需要将一组数据进行从小到大的排序,可以对数组进行冒泡排序,每进行一趟排序,每两个相邻的数据就会进行大小比较,如果前面一个数大于后面一个数,那么便会交换这两个数据之间的位置,保证较大的数值一定在后面,那么每一趟排序,就能确定这趟排序的一个最大数值。
n个数据元素的反序集合,需要对其进行n-1趟排序,每第i趟排序所进行的比较次数是n-i次,n个数据元素的正序集合,值需要进行一趟排序,n-1次比较。其平均时间复杂度是O(n*n)。
class Program
{
static void Main(string[] args)
{
int[] array = new int[10];
Random rd = new Random();
Console.WriteLine("冒泡排序开始前的数据");
for (int i = 0; i < array.Length; i++)
{
array[i] = rd.Next(0,100);
Console.WriteLine(array[i]);
}
bool needToSort = false;
for (int i = 0; i < array.Length-1; i++)
{
needToSort = false;
for (int j = 0; j < array.Length - 1-i; j++)
{
if (array[j]> array[j+1])
{
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
needToSort = true;
}
}
if (needToSort == false)
{
break;
}
}
Console.WriteLine("冒泡排序开始后的数据");
foreach (var item in array)
{
Console.WriteLine(item);
}
Console.Read();
}
}
}
选择排序是在每一趟排序中选择一个最小的数与这趟排序的最前面的数据进行交换,上一趟排序选出的最小数不会参与下一趟排序。
因此,对n个数据的无序集合进行排序时,需要进行n-1趟排序,每第i趟排序都要进行n-i-1次比较,其时间复杂度也是O(n*n)。
int min=array[0];
int index=0;
for (int i = 0; i < array.Length-1; i++)
{
min = array[i];
for (int j = i+1; j < array.Length ; j++)
{
if (min>array[j])
{
min = array[j];
index = j;
}
}
array[index] = array[i];
array[i] = min;
}
本文章使用limfx的vscode插件快速发布