📄 chapter10.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=gb2312">
<title>无标题文档</title>
<style type="text/css">
<!--
.style1 {
font-size: 16px;
color: #FF0000;
}
.style2 {font-size: 14px}
-->
</style>
</head>
<body>
<p><span
class=style1><em><strong>第 十 章 群体数据的组织</strong></em></span></p>
<p><br>
<span class="style2"><strong>10-1 简单说明插入排序的算法思想</strong>。</span><br>
</span></p>
<p><span class="style2">解： <br>
插入排序的基本思想是：每一步将一个待排序元素按其关键字值的大小插入到已排序序列的适当位置上，直到待排序元素插入完为止。<br>
</span></p>
<p><span class="style2"><strong>10-2 初始化整型数组data1[]={1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20}，调用教材中的直接插入排序函数模板进行排序，对此函数模板稍做修改，加入输出语句，在每插入一个待排序元素后显示整个数组，观察排序过程中数据的变化，加深对插入排序算法的理解。</strong><br>
</span></p>
<p><span class="style2">解： <br>
#include <iostream.h> </span></p>
<p class="style2">template <class T><br>
void InsertionSort(T A[], int n)<br>
{<br>
int i, j;<br>
T temp;<br>
<br>
// 将下标为1～n-1的元素逐个插入到已排序序列中适当的位置<br>
for (i = 1; i < n; i++) <br>
{<br>
//从A[i-1]开始向A[0]方向扫描各元素,寻找适当位置插入A[i]<br>
j = i;<br>
temp = A[i];<br>
while (j > 0 && temp < A[j-1]) <br>
{ //逐个比较，直到temp>=A[j-1]时，j便是应插入的位置。<br>
//若达到j==0，则0是应插入的位置。<br>
A[j] = A[j-1];<br>
//将元素逐个后移，以便找到插入位置时可立即插入。<br>
j--;<br>
}<br>
// 插入位置已找到，立即插入。<br>
A[j] = temp;<br>
<br>
//输出数据<br>
for(int k=0;k<n;k++)<br>
cout << A[k] << " ";<br>
cout << endl;<br>
//结束输出 <br>
}<br>
}</p>
<p class="style2">void main()<br>
{<br>
int i;<br>
<br>
int data1[]={1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20};<br>
cout << "排序前的数据：" << endl;<br>
for(i=0;i<20;i++)<br>
cout << data1[i] << " ";<br>
cout << endl;<br>
cout << "开始排序..." << endl;<br>
InsertionSort(data1, 20);<br>
cout << "排序后的数据：" << endl;<br>
for(i=0;i<20;i++)<br>
cout << data1[i] << " ";<br>
cout << endl;<br>
}<br>
程序运行输出：<br>
排序前的数据：<br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
开始排序...<br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
1 2 3 5 7 9 11 13 15 17 19 4 6 8 10 12 14 16 18 20 <br>
1 2 3 4 5 7 9 11 13 15 17 19 6 8 10 12 14 16 18 20 <br>
1 2 3 4 5 6 7 9 11 13 15 17 19 8 10 12 14 16 18 20 <br>
1 2 3 4 5 6 7 8 9 11 13 15 17 19 10 12 14 16 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 13 15 17 19 12 14 16 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 15 17 19 14 16 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 19 16 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <br>
排序后的数据：<br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 </p>
<p class="style2"> </p>
<p class="style2"><strong>10-3 简单说明选择排序的算法思想。</strong><br>
</p>
<p class="style2">解： <br>
选择类排序的基本思想是：每次从待排序序列中选择一个关键字最小的元素，（当需要按关键字升序排列时），顺序排在已排序序列的最后，直至全部排完。<br>
</p>
<p class="style2"><strong>10-4 初始化整型数组data1[]={1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20}，调用教材中的直接选择排序函数模板进行排序，对此函数模板稍做修改，加入输出语句，每对一个待排序元素排序后显示整个数组，观察排序过程中数据的变化，加深对直接选择排序算法的理解。</strong><br>
</p>
<p class="style2">解： <br>
#include <iostream.h></p>
<p class="style2">// 辅助函数：交换x和y的值<br>
template <class T><br>
void Swap (T &x, T &y)<br>
{<br>
T temp;<br>
<br>
temp = x;<br>
x = y;<br>
y = temp;<br>
}</p>
<p class="style2">// 用选择法对数组A的n个元素进行排序<br>
template <class T><br>
void SelectionSort(T A[], int n)<br>
{<br>
int smallIndex; //每以趟中选出的最小元素之下标<br>
int i, j;<br>
<br>
// sort A[0]..A[n-2], and A[n-1] is in place<br>
for (i = 0; i < n-1; i++) <br>
{<br>
smallIndex = i; //最小元素之下标初值设为i<br>
// 在元素A[i+1]..A[n-1]中逐个比较显出最小值<br>
for (j = i+1; j < n; j++) <br>
// smallIndex始终记录当前找到的最小值的下标<br>
if (A[j] < A[smallIndex])<br>
smallIndex = j;<br>
// 将这一趟找到的最小元素与A[i]交换<br>
Swap(A[i], A[smallIndex]);<br>
//输出数据<br>
for(int k=0;k<n;k++)<br>
cout << A[k] << " ";<br>
cout << endl;<br>
//结束输出 <br>
<br>
}<br>
}</p>
<p class="style2">void main()<br>
{<br>
int i;<br>
<br>
int data1[]={1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20};<br>
cout << "排序前的数据：" << endl;<br>
for(i=0;i<20;i++)<br>
cout << data1[i] << " ";<br>
cout << endl;<br>
cout << "开始排序..." << endl;<br>
SelectionSort(data1, 20);<br>
cout << "排序后的数据：" << endl;<br>
for(i=0;i<20;i++)<br>
cout << data1[i] << " ";<br>
cout << endl;<br>
}<br>
程序运行输出：<br>
排序前的数据：<br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
1 3 5 7 9 11 13 15 17 19 2 4 6 8 10 12 14 16 18 20 <br>
1 2 5 7 9 11 13 15 17 19 3 4 6 8 10 12 14 16 18 20 <br>
1 2 3 7 9 11 13 15 17 19 5 4 6 8 10 12 14 16 18 20 <br>
1 2 3 4 9 11 13 15 17 19 5 7 6 8 10 12 14 16 18 20 <br>
1 2 3 4 5 11 13 15 17 19 9 7 6 8 10 12 14 16 18 20 <br>
1 2 3 4 5 6 13 15 17 19 9 7 11 8 10 12 14 16 18 20 <br>
1 2 3 4 5 6 7 15 17 19 9 13 11 8 10 12 14 16 18 20 <br>
1 2 3 4 5 6 7 8 17 19 9 13 11 15 10 12 14 16 18 20 <br>
1 2 3 4 5 6 7 8 9 19 17 13 11 15 10 12 14 16 18 20 <br>
1 2 3 4 5 6 7 8 9 10 17 13 11 15 19 12 14 16 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 13 17 15 19 12 14 16 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 17 15 19 13 14 16 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 15 19 17 14 16 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 19 17 15 16 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 17 19 16 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 19 17 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 19 18 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 <br>
排序后的数据：<br>
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 </p>
<p class="style2"> </p>
<p class="style2"><strong>10-5 简单说明交换排序的算法思想。</strong><br>
</p>
<p class="style2">解： <br>
交换排序的基本思想是：两两比较待排序序列中的元素，并交换不满足顺序要求的各对元素，直到全部满足顺序要求为止。<br>
</p>
<p class="style2"><strong>10-6 初始化整型数组data1[]={1,3,5,7,9,11,13,15,17,19,2,4,6,8,10,12,14,16,18,20}，调用教材中的起泡排序函数模板进行排序，对此函数模板稍做修改，加入输出语句，每完成一趟起泡排序后显示整个数组，观察排序过程中数据的变化，加深对起泡排序算法的理解。<br>
</strong></p>
<p class="style2">解：<strong> </strong><br>
#include <iostream.h></p>
<p class="style2">// 辅助函数：交换x和y的值<br>
template <class T><br>
void Swap (T &x, T &y)<br>
{<br>
T temp;<br>
<br>
temp = x;<br>
x = y;<br>
y = temp;<br>
}</p>
<p class="style2">// 用起泡法对数组A的n个元素进行排序<br>
template <class T><br>
void BubbleSort(T A[], int n)<br>
{<br>
int i,j; <br>
int lastExchangeIndex; <br>
//用于记录每趟被交换的最后一对元素中较小的下标<br>
i = n-1; // i是下一趟需参与排序交换的元素之最大下标<br>
<br>
while (i > 0)<br>
//持续排序过程，直到最后一趟排序没有交换发生，或已达n-1趟<br>
{<br>
lastExchangeIndex = 0; <br>
//每一趟开始时，设置交换标志为0（未交换）<br>
for (j = 0; j < i; j++) //每一趟对元素A[0]..A[i]进行比较和交换<br>
if (A[j+1] < A[j]) //如果元素A[j+1] < A[j]，交换之<br>
{ <br>
Swap(A[j],A[j+1]);<br>
lastExchangeIndex = j; <br>
//记录被交换的一对元素中较小的下标<br>
}<br>
<br>
// 将i设置为本趟被交换的最后一对元素中较小的下标<br>
i = lastExchangeIndex;<br>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -