首页 > 代码库 > 冒泡排序法2014-6-9 20:08:41

冒泡排序法2014-6-9 20:08:41

2024-07-07 17:56:50   224人阅读

 1 using System;
 2 using System.Collections.Generic;
 3 using System.Linq;
 4 using System.Text;
 5 using System.Threading.Tasks;
 6 
 7 namespace 冒泡排序法
 8 {
 9     class Program
10     {
11         static void Main(string[] args)
12         {
13             int[] nums = {23, 23, 44, 66, 76, 98, 11, 3, 9, 7};
14             for (int j = 0; j < nums.Length - 1; j++)//最多做n-1趟排序
15             {
16                 //23要和9个数进行比较，所以循环次数为nums.Length -1- j
17                 for (int i = 0; i < nums.Length - 1 - j; i++)
18                 {
19                     if (nums[i] < nums[i + 1])//降序排列//如果两个元素相等是不会进入循环，所以先后顺序不会改变----稳定排序算法
20                     {
21                         int temp = nums[i];
22                         nums[i] = nums[i+1];
23                         nums[i+1] = temp;
24                     }
25                 }
26             }
27             for (int i = 0; i < nums.Length; i++)
28             {
29                 Console.Write(nums[i]+",");
30             }
31             Console.ReadKey();
32         }
33     }
34 }

冒泡排序就是把小的元素往前调或者把大的元素往后调。比较是相邻的两个元素比较，交换也发生在这两个元素之间。所以，如果两个元素相等，我想你是不会再无聊地把他们俩交换一下的；

如果两个相等的元素没有相邻，那么即使通过前面的两两交换把两个相邻起来，这时候也不会交换，所以相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

稳定排序：待排序的记录序列中可能存在两个或两个以上关键字相等的记录。排序前的序列中Ri领先于Rj（即i<j）.若在排序后的序列中Ri仍然领先于Rj，则称所用的方法是稳定的。

冒泡排序基本原理：大泡在上，小泡在下(按需求，不定)

时间复杂度:O（n^2），记录移动次数=3n(n-1)/2。不及堆排序、快速排序的O（nlogn，底数为2）。一路、二路归并排序、不平衡二叉树排序的速度均比冒泡排序快，且具有稳定性。

冒泡排序是经过n-1趟子排序完成的，第i趟子排序从第1个数至第n-i个数，若第i个数比后一个数大（则升序，小则降序）则交换两数。

冒泡排序（BubbleSort）的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。

即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟

结束，将最大的数放到了最后。------------------比较n-1次

在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最

大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。-------------------------比较n-2次

如此下去，重复以上过程，直至最终完成排序。最后比较1次，确定最后两个数的大小---------------------------比较1次

故共比次数：1+2+...+n-1=(1+n-1)(n-1)/2=n(n-1)/2。

用二重循环实现，外循环变量设为i，内循环变量设为j。外循环重复9次，内循环依次重复9，8，...，1次。

每次进行比较的两个元素都是与内循环j有关的，它们可以分别用a[j]和a[j+1]标识，i的值依次为1,2,...,9，对于每一个i, j的值依次为1,2,...10-i.

 


联系
我们