2011-11-26 12:47:33

1.直接选择排序：

，小孩子多聪明啊，这么小就知道了直接选择排序。羡慕中........

1 using System;

2 using System.Collections.Generic;

3 using System.Linq;

4 using System.Text;

5 using System.Threading;

6 using System.Diagnostics;

7

8 namespace SelectionSort

9 {

10     public class Program

11     {

12         static void Main(string[] args)

13         {

14             //5次比较

15             for (int i = 1; i <= 5; i++)

16             {

17                 List<int> list = new List<int>();

18

19                 //插入2w个随机数到数组中

20                 for (int j = 0; j < 20000; j++)

21                 {

22                     Thread.Sleep(1);

23                     list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 1000000));

24                 }

25

26                 Console.WriteLine("\n第" + i + "次比较：");

27

28                 Stopwatch watch = new Stopwatch();

29

30                 watch.Start();

31                 var result = list.OrderBy(single => single).ToList();

32                 watch.Stop();

33

34                 Console.WriteLine("\n快速排序耗费时间：" + watch.ElapsedMilliseconds);

35                 Console.WriteLine("输出前十个数:" + string.Join(",", result.Take(10).ToList()));

36

37                 watch.Start();

38                 result = SelectionSort(list);

39                 watch.Stop();

40

41                 Console.WriteLine("\n直接选择排序耗费时间：" + watch.ElapsedMilliseconds);

42                 Console.WriteLine("输出前十个数:" + string.Join(",", list.Take(10).ToList()));

43

44             }

45         }

46

47         //选择排序

48         static List<int> SelectionSort(List<int> list)

49         {

50             //要遍历的次数

51             for (int i = 0; i < list.Count - 1; i++)

52             {

53                 //假设tempIndex的下标的值最小

54                 int tempIndex = i;

55

56                 for (int j = i + 1; j < list.Count; j++)

57                 {

58                     //如果tempIndex下标的值大于j下标的值,则记录较小值下标j

59                     if (list[tempIndex] > list[j])

60                         tempIndex = j;

61                 }

62

63                 //最后将假想最小值跟真的最小值进行交换

64                 var tempData = list[tempIndex];

65                 list[tempIndex] = list[i];

66                 list[i] = tempData;

67             }

68             return list;

69         }

70     }

71 }

大根堆：  就是说父节点要比左右孩子都要大。

小根堆：  就是说父节点要比左右孩子都要小。

第一：构建大根堆。

首先上图：

第一步： 首先我们发现，这个堆中有2个父节点(2,,3);

第二步： 比较2这个父节点的两个孩子（4，5），发现5大。

第三步： 然后将较大的右孩子（5）跟父节点（2）进行交换，至此3的左孩子堆构建完毕，

如图：

第四步： 比较第二个父节点（3）下面的左右孩子（5，1），发现左孩子5大。

第五步： 然后父节点（3）与左孩子（5）进行交换，注意，交换后，堆可能会遭到破坏，

必须按照以上的步骤一，步骤二，步骤三进行重新构造堆。

第二：输出大根堆。

至此，我们把大根堆构造出来了，那怎么输出呢？我们做大根堆的目的就是要找出最大值，

那么我们将堆顶（5）与堆尾（2）进行交换，然后将（5）剔除根堆，由于堆顶现在是（2），

所以破坏了根堆，必须重新构造，构造完之后又会出现最大值，再次交换和剔除，最后也就是俺们

要的效果了，

1 using System;

2 using System.Collections.Generic;

3 using System.Linq;

4 using System.Text;

5 using System.Threading;

6 using System.Diagnostics;

7

8 namespace HeapSort

9 {

10     public class Program

11     {

12         static void Main(string[] args)

13         {

14             //5次比较

15             for (int j = 1; j <= 5; j++)

16             {

17                 List<int> list = new List<int>();

18

19                 //插入2w个数字

20                 for (int i = 0; i < 20000; i++)

21                 {

22                     Thread.Sleep(1);

23                     list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));

24                 }

25

26                 Console.WriteLine("\n第" + j + "次比较：");

27

28                 Stopwatch watch = new Stopwatch();

29                 watch.Start();

30                 var result = list.OrderBy(single => single).ToList();

31                 watch.Stop();

32                 Console.WriteLine("\n快速排序耗费时间:" + watch.ElapsedMilliseconds);

33                 Console.WriteLine("输出前十个数" + string.Join(",", result.Take(10).ToList()));

34

35                 watch = new Stopwatch();

36                 watch.Start();

37                 HeapSort(list);

38                 watch.Stop();

39                 Console.WriteLine("\n堆排序耗费时间:" + watch.ElapsedMilliseconds);

40                 Console.WriteLine("输出前十个数" + string.Join(",", list.Take(10).ToList()));

41             }

42

43         }

44

45         ///<summary>

46 /// 构建堆

47 ///</summary>

48 ///<param name="list">待排序的集合</param>

49 ///<param name="parent">父节点</param>

50 ///<param name="length">输出根堆时剔除最大值使用</param>

51         static void HeapAdjust(List<int> list, int parent, int length)

52         {

53             //temp保存当前父节点

54             int temp = list[parent];

55

56             //得到左孩子(这可是二叉树的定义，大家看图也可知道)

57             int child = 2 * parent + 1;

58

59             while (child < length)

60             {

61                 //如果parent有右孩子，则要判断左孩子是否小于右孩子

62                 if (child + 1 < length && list[child] < list[child + 1])

63                     child++;

64

65                 //父亲节点大于子节点，就不用做交换

66                 if (temp >= list[child])

67                     break;

68

69                 //将较大子节点的值赋给父亲节点

70                 list[parent] = list[child];

71

72                 //然后将子节点做为父亲节点，已防止是否破坏根堆时重新构造

73                 parent = child;

74

75                 //找到该父亲节点较小的左孩子节点

76                 child = 2 * parent + 1;

77             }

78             //最后将temp值赋给较大的子节点，以形成两值交换

79             list[parent] = temp;

80         }

81

82         ///<summary>

83 /// 堆排序

84 ///</summary>

85 ///<param name="list"></param>

86         public static void HeapSort(List<int> list)

87         {

88             //list.Count/2-1:就是堆中父节点的个数

89             for (int i = list.Count / 2 - 1; i >= 0; i--)

90             {

91                 HeapAdjust(list, i, list.Count);

92             }

93

94             //最后输出堆元素

95             for (int i = list.Count - 1; i > 0; i--)

96             {

97                 //堆顶与当前堆的第i个元素进行值对调

98                 int temp = list[0];

99                 list[0] = list[i];

100                 list[i] = temp;

101

102                 //因为两值交换，可能破坏根堆，所以必须重新构造

103                 HeapAdjust(list, 0, i);

104             }

105         }

106     }

107 }           www.2cto.com

1 using System;

2 using System.Collections.Generic;

3 using System.Linq;

4 using System.Text;

5 using System.Threading;

6 using System.Diagnostics;

7

8 namespace QuickSort

9 {

10     public class Program

11     {

12         static void Main(string[] args)

13         {

14             //5此比较

15             for (int j = 1; j <= 5; j++)

16             {

17                 List<int> list = new List<int>();

18

19                 for (int i = 0; i < 20000; i++)

20                 {

21                     Thread.Sleep(1);

22                     list.Add(new Random((int)DateTime.Now.Ticks).Next(1000, 100000));

23                 }

24

25                 Console.WriteLine("\n第" + j + "次比较：");

26

27                 Stopwatch watch = new Stopwatch();

28                 watch.Start();

29                 var result = list.OrderByDescending(single => single).Take(10).ToList();

30                 watch.Stop();

31                 Console.WriteLine("\n快速排序求前K大耗费时间:" + watch.ElapsedMilliseconds);

32                 Console.WriteLine("输出前十个数:" + string.Join(",", result.Take(10).ToList()));

33

34                 watch = new Stopwatch();

35                 watch.Start();

36                 result = HeapSort(list, 10);

37                 watch.Stop();

38                 Console.WriteLine("\n堆排序求前K大耗费时间：" + watch.ElapsedMilliseconds);

39                 Console.WriteLine("输出前十个数:" + string.Join(",", list.Take(10).ToList()));

40             }

41

42         }

43

44         ///<summary>

45 /// 构建堆

46 ///</summary>

47 ///<param name="list">待排序的集合</param>

48 ///<param name="parent">父节点</param>

49 ///<param name="length">输出根堆时剔除最大值使用</param>

50         static void HeapAdjust(List<int> list, int parent, int length)

51         {

52             //temp保存当前父节点

53             int temp = list[parent];

54

55             //得到左孩子(这可是二叉树的定义哇)

56             int child = 2 * parent + 1;

57

58             while (child < length)

59             {

60                 //如果parent有右孩子，则要判断左孩子是否小于右孩子

61                 if (child + 1 < length && list[child] < list[child + 1])

62                     child++;

63

64                 //父节点大于子节点，不用做交换

65                 if (temp >= list[child])

66                     break;

67

68                 //将较大子节点的值赋给父亲节点

69                 list[parent] = list[child];

70

71                 //然后将子节点做为父亲节点，已防止是否破坏根堆时重新构造

72                 parent = child;

73

74                 //找到该父节点左孩子节点

75                 child = 2 * parent + 1;

76             }

77             //最后将temp值赋给较大的子节点，以形成两值交换

78             list[parent] = temp;

79         }

80

81         ///<summary>

82 /// 堆排序

83 ///</summary>

84 ///<param name="list">待排序的集合</param>

85 ///<param name="top">前K大</param>

86 ///<returns></returns>

87         public static List<int> HeapSort(List<int> list, int top)

88         {

89             List<int> topNode = new List<int>();

90

91             //list.Count/2-1:就是堆中非叶子节点的个数

92             for (int i = list.Count / 2 - 1; i >= 0; i--)

93             {

94                 HeapAdjust(list, i, list.Count);

95             }

96

97             //最后输出堆元素（求前K大）

98             for (int i = list.Count - 1; i >= list.Count - top; i--)

99             {

100                 //堆顶与当前堆的第i个元素进行值对调

101                 int temp = list[0];

102                 list[0] = list[i];

103                 list[i] = temp;

104

105                 //最大值加入集合

106                 topNode.Add(temp);

107

108                 //因为顺序被打乱，必须重新构造堆

109                 HeapAdjust(list, 0, i);

110             }

111             return topNode;

112         }

113     }

114 }

ps： 直接选择排序的时间复杂度为：O(n^2)

堆排序的时间复杂度：O(NlogN)