小小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--;
            }
        }