原创 算法

排序算法之冒泡排序、选择排序

Posted by Leon on 2015-10-18

冒泡排序已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[2]与a[3]的值，若a[2]大于a[3]则交换两者的值，否则不变。再比较a[3]与a[4]，依此类推，最后比较a[n-1]与a[n]的值。这样处理一轮后，a[n]的值一定是这组数据中最大的。再对a[1]a[n-1]以相同方法处理一轮，则a[n-1]的值一定是a[1]a[n-1]中最大的。再对a[1]~a[n-2]以相同方法处理一轮，依此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。优点：稳定，比较次数已知；缺点：慢，每次只能移动相邻两个数据，移动数据的次数多。

选择排序已知一组无序数据a[1]、a[2]、……a[n]，需将其按升序排列。首先比较a[1]与a[2]的值，若a[1]大于a[2]则交换两者的值，否则不变。再比较a[1]与a[3]的值，若a[1]大于a[3]则交换两者的值，否则不变。再比较a[1]与a[4]，依此类推，最后比较a[1]与a[n]的值。这样处理一轮后，a[1]的值一定是这组数据中最小的。再将a[2]与a[3]a[n]以相同方法比较一轮，则a[2]的值一定是a[2]a[n]中最小的。再将a[3]与a[4]~a[n]以相同方法比较一轮，依此类推。共处理n-1轮后a[1]、a[2]、……a[n]就以升序排列了。

下面贴出代码： 

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
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
代码

using System;
using System.Text;

namespace SortArithmetic
{
    public class MyClass
    {
        public static void Main()
        {
            int[] Nums = RandomNums(3, 27);
            ShowNums("原数组是： ", Nums);
            //ShowNums("排序后是：", BubbleSort(Nums));
            ShowNums("排序后是：", SelectSort(Nums));
            Console.ReadLine();
        }

        #region 生成随机int数组
        private static int[] RandomNums(int Length, int Count)
        {
            Random Rand = new Random(7);
            int[] Nums = new int[Count];
            for (int c = 0; c < Count; c++)
            {
                string Result = string.Empty;
                for (int i = 0; i < Length; i++)
                {
                    Result += Rand.Next(10).ToString();
                }
                Nums[c] = Convert.ToInt32(Result);
            }
            return Nums;
        }
        #endregion


        #region 排序算法：冒泡排序（升序）  排序次数可计算：int[n],n为5那么  6*(6-1)/2
        private static int[] BubbleSort(int[] Nums)
        {
            for (int c = 0; c < Nums.Length-1; c++)
            {
                for (int i = 0; i < Nums.Length - c - 1; i++)
                {
                    int Temp = Nums[i + 1];
                    if (Nums[i] > Nums[i + 1])
                    {
                        Nums[i + 1] = Nums[i];
                        Nums[i] = Temp;
                    }
                }
            }
            return Nums;
        }
        #endregion

        #region 排序算法：选择排序（升序）
        private static int[] SelectSort(int[] Nums)
        {
            for (int c = 0; c < Nums.Length-1; c++)
            {
                for (int i = c; i < Nums.Length - 1; i++)
                {
                    int Temp = Nums[i+1];
                    if (Nums[c] > Nums[i + 1])
                    {
                        Nums[i + 1] = Nums[c];
                        Nums[c] = Temp;
                    }
                }
            }
            return Nums;
        }
        #endregion

        private static void ShowNums(string Msgs, int[] Nums)
        {
            Console.Write(Msgs);
            foreach (int n in Nums)
            {
                Console.Write(n.ToString() + "  ");
            }
            Console.WriteLine();
        }


    }
}