数据结构(C#)_排序算法(插入排序)

这两周也比较忙一些，今天继续我们的系列，将排序算法中的插入排序（包括了直接插入排序和希尔排序），我发现这本电子版的数据结构问题不少，很多代码都是有错误的，不能运行，不知道作者是怎么运行出结果的。而且还配有插图，同时在校对的时候也不是很严格，相同的一个函数，在不同的页中出现，会有变量名不相同的情况。下面我们介绍一下基本的概念：
插入排序：该排序是一种简单的排序方法，基本操作就是将一个记录插入已经排好序的有序表中，从而得到一个新的，记录数增加一的有序表。
希尔排序：又称缩小增量排序(Diminishing Increment Sort),属于插入排序类的一种排序，在时间复杂度上有较大的改进。基本思想是先将整个待排序记录序列分成若干个子序列分别进行直接插入排序，当整个序列基本有序，再对全部记录进行一次直接插入排序。

1namespaceSorting
2{
3classSortingAlgorithms
4{
5privateint[]arr;
6privateintupper;
7privateintnumElement;
8
9//初始化数组
10publicSortingAlgorithms(intsize)
11{
12arr=newint[size];
13upper=size-1;
14numElement=0;
15}
16
17//给数组插入元素
18publicvoidInsert(intitem)
19{
20arr[numElement]=item;
21numElement++;
22}
23
24//打印数组元素
25publicvoidDisplayElement()
26{
27for(inti=0;i<=upper;i++)
28{
29Console.Write(arr[i]+"");
30}
31Console.ReadLine();
32}
33
34publicvoidCleaArry()
35{
36for(inti=0;i<=upper;i++)
37{
38arr[i]=0;
39numElement=0;
40}
41}
42
43//选择排序，数据量大的时候效率较高
44publicvoidSelectionSort()
45{
46intMin,Temp;
47for(intOuter=0;Outer<=upper;Outer++)
48{
49Min=Outer;
50for(intInner=Outer+1;Inner<=upper;Inner++)
51{
52if(arr[Inner]<arr[Min])
53{
54Min=Inner;
55
56}
57Temp=arr[Outer];
58arr[Outer]=arr[Min];
59arr[Min]=Temp;
60
61}
62}
63}
64
65
66//插入排序(版本一)
67//插入排序当数据量较大的时候效率不高
68publicvoidInsertionSort()
69{
70intInner,Temp;
71for(intOuter=1;Outer<=upper;Outer++)
72{
73Temp=arr[Outer];
74Inner=Outer;
75while(Inner>0&&(arr[Inner-1]>=Temp))
76{
77arr[Inner]=arr[Inner-1];//向后移动二者较大的元素
78Inner-=1;
79
80}
81arr[Inner]=Temp;
82}
83}
84
85//这个版本是和我们的C语言版的数据结构课本上的的类似
86//插入排序(版本二)
87publicvoidInserSort()
88{
89intInner,Temp;
90for(intOuter=1;Outer<=upper;Outer++)
91{
92//将每一趟比较的哨兵元素复制给Temp
93Temp=arr[Outer];
94for(Inner=Outer;(Inner>0&&arr[Inner-1]>Temp);Inner--)
95{
96//向后移动大的元素
97arr[Inner]=arr[Inner-1];
98}
99//将哨兵赋值
100arr[Inner]=Temp;
101}
102}
103
104
105//希尔排序(原书代码，有问题)
106/**//*publicvoidShellSorts()
107{
108intInner,Temp;
109inth=1;
110while(h<=(numElement/3))
111{
112h=h*3+1;
113while(h>0)
114{
115for(intOuter=h;Outer<=numElement-1;h++)
116{
117Temp=arr[Outer];
118Inner=Outer;
119
120while((Inner>h-1)&&arr[Inner-h]>=Temp)
121{
122arr[Inner]=arr[Inner-h];
123Inner-=h;
124}
125arr[Inner]=Temp;
126
127}
128h=(h-1)/3;
129}
130}
131
132}
133*/
134
135
136//希尔排序
137publicvoidShellSortingAlgorithms()
138{
139intTemp;
140//初始增量序列
141intIncrement=upper/2;
142while(Increment!=0)
143{
144for(inti=Increment;i<=upper;i++)
145{
146intj;
147Temp=arr[i];
148for(j=i;j>=Increment;j=j-Increment)//同子序列的插入排序
149{
150if(Temp<arr[j-Increment])
151arr[j]=arr[j-Increment];//如果后面的小于前面的,交换位置
152else
153break;
154}
155arr[j]=Temp;//插入
156}
157//减小增量序列
158Increment/=2;
159}
160
161}
162
163
164}

调用算法的过程：

1staticvoidMain(string[]args)
2{
3SortingAlgorithmsMyArray=newSortingAlgorithms(10);
4Randomrnd=newRandom(100);
5
6longTicks=DateTime.Now.Ticks;
7for(inti=0;i<10;i++)
8{
9MyArray.Insert((int)(rnd.NextDouble()*100));
10}
11color:

分享到：

数据结构(C#)--单链表 | C#中如何处理快捷键

• 2008-03-19 16:47
• 浏览 986
• 评论(0)
• 查看更多