小小c#算法题 - 0 - 单循环冒泡排序本来一直想写这篇文章来着,但自己平时瞎忙,今天碰巧有人问了,于是就把它写出来。 一个循环并不是说时间复杂度就是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--; } } |
|