CPP学习之——数字排序问题(14.10)

一 概述

下面有这样6个数，它们的顺序是打乱的：1、34、78、98、32、45

希望你编写一段程序将它们从小到大顺序排列起来

二 两个数比较分析

• 也许有读者看到这里会不屑一顾地说：我不用编写程序也能将它们顺序排列起来。我相信他肯定能做到，而且也不会花费许多时间，但是我要补充一点的是：假如不是6个数字，而是一百万个或者更多的话。这位读者是否还会这么自信呢？
• 那肯定没这么简单了，我相信只要不是天才，要手工顺序排列成上万打乱的数字，那还是相当吃力的。但是换句话说，假如是你家那台已经淘汰多年的电脑来做这个排序工作的话，你会发现那是一件相当轻松的事，因为它的运算速度毕竟要比人快多了。
• 虽然电脑做起来效率很高，但是假如你不懂它的语言和思维，那也无法命令它做事，因此我们要站在电脑的角度上考虑一下这个排序问题。
• 电脑不认识数字，它无法直观地发现哪个数字大，哪个数字小，它需要进行计算，因此我们要电脑进行排序的话，就要充分发挥它的计算能力。我们可以这么做：先让它比较前两个数的大小，假如第一个数比第二个数大，那么将大的数与小的数对调，然后用大的数继续比较后面的数，比如说3、2、1，我们先比较开头的3和2，由于3比2大，因此我们将2与3对调，变成2、3、1，然后继续比较后两个数3和1，3还比1大，再将两个数对调，变为2、1、3。到目前为止，第一轮比较结束，这一轮主要解决了一个问题，就是将最大数3排列到了最后。因此第二轮的时候只对开头的两个数2、1进行比较，由于2比1大，将两个数字对调，则为：1、2、3，完成了排序。

三 多个数比较分析比较回数

• 根据上面的思路，我们需要一个数组来保存所有的乱序数字，嘉定这个数组为a[3]，然后需要一个变量来保存比较的回数，假定为j，另外还需要一个用来交换两个数字的变量t和一个用来存放数组元素编号的变量i。
• 我们先来看总共比较的回数，由于只有三个数3、2、1，又是两两一组进行比较，因此第一回比较只进行了两次就结束了，由于我们第一次排序将最大数3排列到最后面，因此第二回就不再对3进行比较，只对2和1进行了一次比较就完成了整个排序。我们只计算比较的回事，不计算次数，那么完成3个数的排序则一共进行了两回比较
• 我们再来看6个数的比较回数，例如：1 、34、78、98、32、45，第一回两两比较后，将最大数98排列到结尾，第二回将78排列到倒数第二位，第三回是45，第四回34，第五回将32排在1后面，完成了整个排序
• 我们看到6个数的排序也是进行了6-1等于5回，也就是说我们要对N位数进行排序的话，那么总共要比较N-1回，这里我们的N是6，N-1等于5回，那么我们的第一个循环语句可以这么写：for(j=0;j<5;j++)；j是比较的回数，初始化为0，没回执行循环后自加1，一直到5的时候循环体结束，一共执行了5回。也就是N-1回

四 多个数比较分析

• 我们算出比较的回数，然后再看没回比较的次数，6个数：1、34、78、98、32、45
• 它们的第一回比较进行了5次，将98排列到了最后，第二回由于不再对98进行排序，因此只进行了4次，将78放到了倒数第二位，第三回不对78和98进行比较，共比较3次，第四回是2次，第五回是1次。
• 我们仔细观察没回的比较次数，发现了这么一个规律，没回的比较次数恰好等于所要比较的数字总数减去比较回数，也就是N-j，第一回比较要进行N-j次两两比较，也就是N-1次，第二回进行N-j次两两比较，也就是N-2次，相应的，在第j(5)次要进行N-j(5)次两两比较。
• 明白了这一点，那么每回合中数字的比较排序可以这么写：

五 示例演示及结果输出

5.1 代码

#include<iostream>
using namespace std;
int main() {

	int a[6] = { 1, 34, 78, 98, 32, 45 };
	int i, j, t;
	for (j = 0; j < 5; j++)
	{
		for (i = 0; i < 6 - j; i++)
		{
			if (a[i] > a[i + 1])
			{
				t = a[i];
				a[i] = a[i + 1];
				a[i + 1] = t;
			}
		}
	}
	cout<<"排序后的数字为：\n";
	for(i=0;i<6;i++)
	{
		cout<<a[i]<<"、";
	}
	return 0;
}

5.2 输出结果

排序后的数字为：
1、32、34、37、45、78、