本来一直想写这篇文章来着,但自己平时瞎忙,今天碰巧有人问了,于是就把它写出来。
一个循环并不是说时间复杂度就是O(n), 冒泡排序的时间复杂度只能是O(n*n). 所以说如果有这么一道题,它考的只是一个编程技巧,并不是说有什么更高效率的算法。
而且用一个循环写出来的算法没有用两个写出来的算法高效。因为要作一些额外的计算。
下面把传统两个循环嵌套的代码和只用一个循环的代码贴出来了。
代码只经过简单测试。不过基本思想是很清楚的了。
1. 原始的两个循环嵌套的冒泡排序
static void Sort(int[] array)
{
int length = array.Length;
for (int i = 0; i < length - 1; i++)
{
for (int j = 0; j < length - 1 - i; j++)
{
if (array[j] > array[j + 1])
{
int temp = array[j];
array[j] = array[j + 1];
array[j + 1] = temp;
}
}
}
}
2. 只用一个循环的冒泡排序
这里充分利用了除操作与取余操作的关系这一技巧。如果你理解了《编程之美》第二章 将帅问题的解决方案的精髓的话,那么下面的代码就很容易理解了。
static void SortOneLoop(int[] array)
{
int length = array.Length;
int total = length * length - 1;
while (total / length > 0)
{
if (total % length >= length - total / length && array[total % length] < array[total % length - 1])
{
int temp = array[total % length];
array[total % length] = array[total % length - 1];
array[total % length - 1] = temp;
}
total--;
}
}