几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
2 using namespace std;
3
4 /*/////////////////////////////////////////////////////////////////////////
5 以下为快速排序
6 /////////////////////////////////////////////////////////////////////////*/
7 /*
8 冒泡排序
9 算法:
10 核心思想是扫描数据清单,寻找出现乱序的两个相邻的项目。当找到这两个项目后
11 交换项目的位置然后继续扫描。重复上面的操作直到所有的项目都按顺序排好
12 时间复杂度n*n (n-1)*n/2
13 */
14 void BubbleSortData(int SortData[], int Length)
15 {
16 int tmpData =0;
17 bool swapFlag =true;
18
19 for (int i=Length-1; i>0 && swapFlag; i--)
20 {
21 swapFlag =false;
22 for(int j=0; j<i; j++)
23 {
24 if ( SortData[j] > SortData[j+1])
25 {
26 tmpData =SortData[j];
27 SortData[j] =SortData[j+1];
28 SortData[j+1] =tmpData;
29 swapFlag =true;
30 }
31 }
32 }
33
34 return;
35 }
36 /*
37 快速排序是对起泡排序的一种改进,通过一趟排序将待排序记录分割成独立的两部分,其中一部分记录的关键字均比另一部分记录的关键
38 字小,则可分别对这两部分继续进行排序,以达到整个序列有序.
39 交换顺序表L中子表L.r[low..high]的记录,使枢轴记录到位,并返回其所在位置,此时在它之前(后)的记录均不大(小)于它
40 时间复杂度为 n*logn,其平均性能最好,若初始记录序列按关键字有序或基本有序,快速排序将锐化为起泡排序
41 */
42 int Partition(int SortData[], int low, int high)
43 {
44 int tmpData =SortData[low];//用于子表的第一个记录作枢轴记录
45 int temp=0;
46
47 while ( low<high )
48 {
49 //从表的两端交替的向中间扫描
50 while (low<high && SortData[high]>=tmpData)
51 {
52 high--;
53 }
54 //将比枢轴记录小的记录移到低端
55 SortData[low] =SortData[high];
56
57 while (low<high && SortData[low]<=tmpData)
58 {
59 low++;
60 }
61 //将比枢轴记录大的记录移到高端
62 SortData[high] =SortData[low];
63 }
64 //枢轴记录到位
65 SortData[low] =tmpData;
66
67 return low;//返回枢轴所在位置
68 }
69
70 void QuickSortData(int SortData[], int low, int high)
71 {
72 int offset;
73
74 if ( low<high )
75 {
76 offset =Partition(SortData, low, high);
77 QuickSortData(SortData, low, offset-1);
78 QuickSortData(SortData, offset+1, high);
79 }
80 }
81
82 /*/////////////////////////////////////////////////////////////////////////
83 以下为插入排序
84 /////////////////////////////////////////////////////////////////////////*/
85 /*
86 直接插入排序
87 算法:经过i-1遍处理后,L[1..i-1]己排好序。第i遍处理仅将L[i]插入L[1..i-1]的适当位置,
88 使得L[1..i]又是排好序的序列。要达到这个目的,我们可以用顺序比较的方法。
89 首先比较L[i]和L[i-1],如果L[i-1]<=L[i],则L[1..i]已排好序,第i遍处理就结束了;
90 否则交换L[i]与L[i-1]的位置,继续比较L[i-1]和L[i-2],直到找到某一个位置j(1≤j≤i-1),
91 使得L[j] ≤L[j+1]时为止
92 优点:移动元素次数少,只需要一个辅助空间
93 时间复杂度n*n
94 当待排序记录的数量n很小时,这是一种很好的排序方法。但是n很大时,则不适合
95 */
96 void InsertSortData(int SortData[], int Length)
97 {
98 int tmpData =0;
99 int i=0;
100 int j=0;
101
102 for(i=1; i<Length; i++)
103 {
104 if ( SortData[i] <SortData[i-1])
105 {
106 tmpData =SortData[i];
107 //数据往后移动
108 for (j=i-1; j>=0 && tmpData<SortData[j]; j--)
109 {
110 SortData[j+1] =SortData[j];
111 }
112 //将数据插入到j+1位置
113 SortData[j+1] =tmpData;
114 }
115 }
116
117 return;
118 }
119
120 /*
121 拆半插入排序所需要的辅助空间和直接插入排序相同,从时间上比较,折半插入排序仅减少了关键字间的比较次数,而记录的移动次数不变。
122 因为时间复杂度仍为n*n
123 */
124 void BInsertSortData(int SortData[], int Length)
125 {
126 int tmpData =0;
127 int i=0;
128 int j=0;
129 int low;
130 int high;
131 int middle;
132
133 for(i=1; i<Length; i++)
134 {
135 tmpData =SortData[i];
136 low =0;
137 high =i-1;
138 //在r[low..high]中折半查找有序插入的位置
139 while ( low<=high )
140 {
141 middle =(low+high)/2;
142 if ( tmpData <SortData[middle] )
143 {
144 high =middle-1;
145 }
146 else
147 {
148 low =middle+1;
149 }
150 }
151 //记录后移
152 for (j=i-1; j>=high+1; j--)
153 {
154 SortData[j+1] =SortData[j];
155 }
156 SortData[high+1] =tmpData;
157 }
158
159 return;
160 }
161
162
163 //////////////////////////////////////////////////////////////////////////
164
165 /*
166 简单选择排序
167 算法:首先找到数据清单中的最小的数据,然后将这个数据同第一个数据交换位置;接下来找第二小的数据,再将其同第二个数据交换位置,以此类推。
168 所需移动的操作次数最少为0,,最大为3(n-1)
169 然而无论记录的初始排列如何,需要比较的次数相同n(n-1)/2 复杂度为n*n
170 */
171 void SelectSortData(int SortData[], int Length)
172 {
173 int tmpData;
174 int offset =0;
175 int j=0;
176
177 for (int i=0; i<Length-1; i++)
178 {
179 offset =0;
180 tmpData =SortData[i];
181 for (j=i+1; j<Length; j++)
182 {
183 if ( tmpData>SortData[j] )
184 {
185 tmpData =SortData[j];
186 offset =j;
187 }
188 }
189
190 if( offset >i)
191 {
192 SortData[offset] =SortData[i];
193 SortData[i] =tmpData;
194 }
195 }
196
197 return;
198 }
199
200 int main()
201 {
202 //int Buffer[] ={1,2,3,4,5,6};
203 int Buffer[] ={6,5,4,3,2,1};
204
205 QuickSortData(Buffer,0, 5);
206
207 for (int i=0; i<6; i++)
208 {
209 cout<<Buffer[i]<<" ";
210 }
211 cout<<endl;
212
213 return 0line
发表评论
-
兼容模式设置
2011-09-13 09:28 928为了最好的视觉效果,可以进行兼容模式设置,如不设置也可正 ... -
google地图图标
2011-01-17 17:09 20641.在指定位置指定 ... -
iefav
2010-09-17 10:14 0反对伐发放 -
fsda
2010-09-16 16:20 0fadfa -
book
2010-09-16 16:16 0rwe -
SQLdll
2010-09-16 16:13 0gsf -
xml验证 转载
2010-05-14 10:04 1067开发环境:VS2008 在.NET中说到验证XML,估 ... -
tree
2009-01-20 09:51 594tree -
iframe 父子窗体调用
2008-11-20 16:03 1500iframe 父窗口和子窗口的调用方法 Posted on ... -
table行列固定
2008-11-04 13:27 2293<html> <head> <s ... -
DHtml
2008-09-26 10:21 587dhtml -
group box
2008-07-02 13:18 1139关于Silverlight Silverlight 是一个跨浏 ... -
vml 饼图
2008-07-01 16:59 1757<html xmlns:v="urn:sche ... -
vml 折线图
2008-07-01 16:57 1982<HTML xmlns:v="urn:sche ... -
vml资料
2008-06-18 16:45 1964http://hi.baidu.com/greatmast ... -
前台图片效果
2008-06-18 14:29 1317<SPAN class="bold" ... -
锚点是什么?
2008-05-05 15:10 14631:锚点是什么?锚点也可以理解成为一种超级链接,只不过它是网页 ... -
webchart作图
2008-05-05 12:57 2193<%@ Import Namespace="S ... -
vml圆角,箭头(IE)
2008-05-05 12:51 2733<HTML xmlns:v> <HEAD& ...
相关推荐
1、本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。 2、待排序表的表的元素的关键字为整数,表长不小于100;其中的数据要用伪随机数产生...
内部排序算法比较 【问题描述】 在教科书中,各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。 ...
数据结构课程设计(内部排序算法比较_C语言) 数据结构课程设计(内部排序算法比较_C语言)
数据结构 内部排序算法分析 c语言代码
《内部排序算法比较》 【问题描述】 在教科书中,各种内部排序算法的时间复杂度分析结果只给出算法的大致执行时间。试通过随机数据比较各算法的关键字比较次数和关键字移动次数,以获得直观感受 【基本要求】 (1)...
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。 二.基本要求 (1)对以下10种常用的内部排序...
实验7: 内部排序算法比较.doc 实验7: 内部排序算法比较.doc 实验7: 内部排序算法比较.doc
通过随机数据比较各内部排序算法的关键字比较次数和关键字移动的次数,以取得直观感受。待排序表的表长不小于100;至少要用5组不同的输入数据作比较;排序算法不少于5种; 待排序的元素的关键字为整数; 比较的指标...
数据结构课设中的内部排序算法的完整实验报告和可运行源代码 绝对可用 绝对原创 题目: 一.题目:内部排序算法研究 (1)设n个关键字均为整数(1≤n≤100000) (2)设计K个内部排序算法(K≥5), 每个算法记录执行所...
本演示程序对以下6种常用的内部排序算法进行实测比较:起泡排序,直接插入排序,简单选择排序,快速排序,希尔排序,堆排序。
各种内部排序算法的比较 各种内部排序算法的比较 各种内部排序算法的比较
要求对以下6种常用的内部排序算法进行比较:起泡排序、直接插入排序、简单选择排序、快速排序、希尔排序、堆排序。待排序表的表长不小于1000;其中的数据要用伪随机数产生程序产生,至少要用5组不同的输入数据作比较...
设计一个测试程序比较几种内部排序算法的关键字比较次数和移动次数以取得直观感受。
各种内部排序算法的时间复杂度分析结果只给出了算法执行时间的阶,或大概执行时间。试通过随机的数据比较各算法的关键字比较次数和关键字移动次数,以取得直观感受。
六种内部排序算法比较:直接插入排序、希尔排序、冒泡排序、快速排序、选择排序、堆排序。包含实验报告和源代码设计。
几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
对以下六种常用的内部排序算法进行比较:希尔排序、直接选择排序、快速排序、直接插入排序、堆排序、冒泡排序。
详细了介绍了内部排序的性能及一些缺陷,通过分析对一些内部排序算法做了一些改进!