冒泡排序

发表于 | 分类于 | 阅读次数: |
字数统计: 617

一：冒泡的基本介绍

1574404458830

1574404494676

二：实际应用

1574404976105

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
static void Main(string[] args)
        {
            int[] arr = {3,9,-1,10,20 };
            for (int i = 0; i < arr.Length - 1; i++)
            {
                for (int j = 0; j < arr.Length - 1 - i; j++)
                {
                    if (arr[i] < arr[j])
                    {
                        int temp = arr[i];
                        arr[i] = arr[j];
                        arr[j] = temp;
                    }
                }
                Console.Write("第" + (i + 1) + "趟排序后的数组：");
                print(arr);
            }
            Console.WriteLine("最后的结果:");
            print(arr);

        }

        public static void print(int[] arr)
        {
            for (int i = 0; i < arr.Length; i++)
            {
                Console.Write(arr[i] + "\t");
            }
            Console.WriteLine("");
        }

1574405291917

三：优化冒泡排序

引入一个开关，如果此次遍历没有交换值，说明顺序是正确，后面没必要重新多次遍历。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
     static void Main(string[] args)
    {
        int[] arr = {3,9,-1,10,20 };
        bool flag = false;//标识变量，表示是否进行交换
   for (int i = 0; i < arr.Length - 1; i++)
    {
        for (int j = 0; j < arr.Length - 1 - i; j++)
        {
                if (arr[j] > arr[j+1])
                {
                    flag = true;
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
        }
        Console.Write("第" + (i + 1) + "趟排序后的数组：");
        print(arr);

        if (flag)//在一趟排序中，依次交换都没有发生过
        {
            flag = false;//重置flag，进行下次判断
        }
        else
        {
            break;
        }
    }
    Console.WriteLine("最后的结果:");
    print(arr);

}

public static void print(int[] arr)
{
    for (int i = 0; i < arr.Length; i++)
    {
        Console.Write(arr[i] + "\t");
    }
    Console.WriteLine("");
}

1574406293361

想比较上面的写法，减少了一次遍历。

四：比较排序的效率

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
         int len = 10;//修改数据量
         int[] arrs = new int[len];
         for (int i = 0; i < len; i++)
         {
             Random random = new Random();
             int a = (int)random.Next(0, len);
             arrs[i] = a;
             Thread.Sleep(1);
         }
         Console.WriteLine("排序前的时间是"+DateTime.Now.ToString("HH:mm:ss fff"));
         bubbleSort(arrs);
         Console.WriteLine("排序后的时间是" + DateTime.Now.ToString("HH:mm:ss fff"));
         
         
public static void bubbleSort(int[] arr)
       {
         bool flag = false;//标识变量，表示是否进行交换
         for (int i = 0; i < arr.Length - 1; i++)
         {
             for (int j = 0; j < arr.Length - 1 - i; j++)
             {
                 if (arr[j] > arr[j + 1])
                 {
                     flag = true;
                     int temp = arr[j];
                     arr[j] = arr[j + 1];
                     arr[j + 1] = temp;
                 }
             }
           //  Console.Write("第" + (i + 1) + "趟排序后的数组：");
           //  print(arr);

             if (flag)//在一趟排序中，依次交换都没有发生过
             {
                 flag = false;//重置flag，进行下次判断
             }
             else
             {
                 break;
             }
         }
     }

10个数据冒泡排序比骄1000个数据：

1574408097405

1574408162091

当数据量越大，所需要的时间越长！

五：源码地址

Github冒泡源码