[排序算法一]冒泡排序
冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。
它重复地走访过要排序的元素列,依次比较两个相邻的元素,如果顺序(如从大到小、首字母从Z到A)错误就把他们交换过来。走访元素的工作是重复地进行直到没有相邻元素需要交换,也就是说该元素列已经排序完成。
这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到顶端一样,故名“冒泡排序”。
冒泡排序的特点
- 时间复杂度:最坏情况O(n^2),最好情况O(n)
- 排序方式:In-place,不需要额外内存
基本做法(从小到大)
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素做同样的工作,从开始第一对到结尾的最后一对。在这一点,最后的元素应该会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
public void Sort1(int[] num)
{
Console.WriteLine("方法1:");
var count1 = 0;
var count2 = 0;
for (var i = 0; i < num.Length - 1; i++)
{
for (var j = i + 1; j < num.Length; j++)
{
count1++;
if (num[i] <= num[j]) continue;
count2++;
var temp = num[j];
num[j] = num[i];
num[i] = temp;
}
}
Console.WriteLine($"结果:{string.Join(",", num)};循环次数:{count1};数据交换次数:{count2}");
}
以上内容,除了代码全部来自网络,盗图请谅解,因为做这么个图是在太难了
通过代码,我们发现,冒泡算法的运行次数其实应该是 (n-1)+(n-2)+(n-3)+…,等于 n(n-1)/2 次,所以得出结论,冒泡算的时间复杂度是O(n^2)
但是,上面介绍不是说有最好的情况下(数据本身就是从小到大排列)时间复杂度是 O(n)吗?
其实,上面的图片介绍和实际算法都存在一些问题,是有可以优化的地方的。
从文字角度上说,既然叫冒泡算法,我们想想水里气泡的形态,一般都是从底部升起到水面,所以,为了更符合实际情况,我们的比较工作应该从数组的尾部开始,把最小(从小到大)的元素慢慢移动到数组的最前的位置。
所以这里先修改一版代码,把比较的顺序倒过来,不是把最大的往后移,而是把最小的往前移
public void Sort2(int[] numbers)
{
Console.WriteLine("方法2:标准冒泡算法排序");
var count1 = 0;
var count2 = 0;
for (var i = 0; i < numbers.Length; i++)
{
for (var j = numbers.Length - 1; j > i; j--)
{
count1++;
if (numbers[j] >= numbers[j - 1]) continue;
count2++;
var temp = numbers[j - 1];
numbers[j-1] = numbers[j];
numbers[j] = temp;
}
}
Console.WriteLine($"结果:{string.Join(",", numbers)};循环次数:{count1};数据交换次数:{count2}");
}
运行一下,我们会发现,调整后的代码循环的次数和效率跟第一版一模一样,肯定的啊,因为中心思路没变,只是把冒泡的方向倒换了一下而已。
下面,我们考虑这样一个数组:[1,0,2,3,5,4],使用第二版的代码:
第一次循环结束,数组结果为 [0,1,2,3,4,5],很神奇有没有,我们不仅把最小的0冒泡到第一位,顺带的最后两个元素也进行了排序。然后目测一下,数组已经是正序排列了,也就是说这是我们应该可以返回了有木有?
这也就是为什么要从尾部往前冒泡的原因。好了,可以优化的点出现了,接下来,请看第三版代码
public void Sort3(int[] numbers)
{
Console.WriteLine("方法2:优化版冒泡算法排序");
var count1 = 0;
var count2 = 0;
// 剩下的数据是否需要继续排序标志
// 因为冒泡排序是从后端两两交换,所以在某种时间点上,后端数据可能已经是排列好的数据
// 如1,0,2,3,4这种情况,第一次循环后,把0交换到最前,结果为0,1,2,3,4
// 继续循环1,2,3,4,如果没有进行数据交换操作,说明已经是排序好的,就没必要继续了,直接跳出即可
var continueFlag = true;
for (var i = 0; i < numbers.Length && continueFlag; i++)
{
for (var j = numbers.Length - 1; j > i; j--)
{
count1++;
if (numbers[j] < numbers[j - 1])
{
count2++;
var temp = numbers[j - 1];
numbers[j - 1] = numbers[j];
numbers[j] = temp;
// 一旦发生数据交换的操作,说明后面的数据并没有排列好,这时需要继续循环
continueFlag = true;
}
else
{
// 没有发生数据交换,说明数据已经是排列好的,这时可以跳出循环了
continueFlag = false;
}
}
}
Console.WriteLine($"结果:{string.Join(",", numbers)};循环次数:{count1};数据交换次数:{count2}");
}
下面,来进行一个测试:
var bubble = new BubbleSortSample();
var numbers = new int[] {3, 1, 2, 4, 6, 9, 5};
bubble.Sort1(numbers);
Console.WriteLine();
numbers = new int[] { 3, 1, 2, 4, 6, 9, 5 };
bubble.Sort2(numbers);
Console.WriteLine();
numbers = new int[] { 3, 1, 2, 4, 6, 9, 5 };
// 第一次 1,3,2,4,5,6,9,发生了交换,循环了6次
// 第二次 1,2,3,4,5,6,9,发生了交换,循环了5次
// 第三次 检查了一圈,循环了4次,没有发生交换,跳出
bubble.Sort3(numbers);
下面是运行结果:
冒泡排序是一种比较基础而且大家比较熟悉的算法,以前总是知其然而没有深究过,网上很多例子也是如第一版代码一样简单实现演示一下了事,却不知原来这么基础的算法也有这么多的门道在其中,所以说学海无涯…省略一万五千字鸡汤