【Day 13】Array - Practice 1

题目
本题将给定一个正整数，请将其看作四位数字(亦即四位数以下则前面补 0)，并找出将数字重新排序後，能组成的最大整数。举例来说，若给定数字为1324，经过重新排列，能组成的最大数字为4321；若原先给定的数字非四位数，如：25，则需看成0025这四位数字去做排列，重组後最大数字为5200。
仔细看看6174这个数字。乍看之下没什麽特别之处，但是，自从 1949 年以来，它一直令数学家、数字控抓狂、痴迷。为什麽呢?因为人们发现,当我们任意选择一个四位数字後 (唯一条件为不可四位皆相同)，先将数字由大到小排序，得出大数，再由小到大排序，得出小数，并把所得出的大数减小数，不断重复这几个步骤，最终将会得到6174这个神秘的数字。姑且不论为什麽，本题我们将要实作这个过程，题目将给定一个整数，请重复以上所述步骤，将每次计算出的答案印出来，两两以一个逗号开，直到印出6174为止。

注意：本题给定的数字不会四位皆相同，例如：9999。

输入输出格式

Sol

1. 有可能碰到输入的数字不满四位数，此时我们需要将这个数补0至使其成为四位数。
2. 运用阵列的观念，看成有四个个位数字，分别存进之後要由大到小排列的阵列raisingArray与由小到大排的阵列descendingArray。
3. 运用泡沫演算法bubble sort，分别由大到小、由小到大排列。
4. 将两阵列的数字各自组合起来变两个四位数做相减并输出diff。
5. 只要输出的数字不等於6174，就重复上述步骤。

Bubble Sort 泡沫演算法
我们以3142为例：

i = 0：
从 j = 0 开始看，比较 num[0]、num[1]，由於 3 > 1，因此两数位置不动，
接下来看 num[1]、num[2]，1 < 4，因此 1、4 位置互换，
接着再比 num[2]、num[3]，1 < 2，两数位置互换，由此一来，我们可以确定最後一项一定是四个数中最小的。
i = 1：
一样从 j = 0 开始，比较 num[0]、num[1]，由於 3 < 4，因此两数位置互换，
此时我们可以看到这四个数都已经按照降幂排列排好了，不过电脑还是会继续将这个回圈跑完，我後面的部分就省略了，在这边给大家一个连结，我觉得他 bubble sort 讲的非常潜显易懂。

Bubble sort：[C++] 气泡排序法(Bubble sort)

Pseudocode：

// 先都将输入的整数换成四位数
if initNum 是三位数
	initNum *= 10
if initNum 是二位数
	initNum *= 100
if initNum 是个位数
	initNum *= 1000

int diff = initNum;

while (diff != 6174){
	// 把diff中每一位数都存进raisingArray、descendingArray
	raisingArray[0] = diff / 1000;
	diff -= raisingArray[0] * 1000;
	raisingArray[1] = diff / 100;
	diff -= raisingArray[1] * 100;
	raisingArray[2] = diff / 10;
	diff -= raisingArray[2] * 10;
	raisingArray[3] = diff;
	for i in range 0 ~ 4 
		raisingArray[i] = descendingArray[i];
}
	
	// 泡沫演算法，由小到大
	for i in range 0 ~ 4 
		for j in range 0 ~ 4 - i - 1
			if (raisingArray[j] > raisingArray[j + 1]) 
				tmp = raisingArray[j];
				raisingArray[j] = raisingArray[j + 1];
				raisingArray[j + 1] = tmp;
	raising = raisingArray[0] * 1000 + … + raisingArray[3]
	
    // 泡沫演算法，由大到小
	for i in range 0 ~ 4  
		for j in range 0 ~ 4 - i - 1
			if (descendingArray[j + 1] > descendingArray[j]) 
				tmp = descendingArray[j + 1];
				descendingArray[j + 1] = descendingArray[j];
				descendingArray[j] = tmp;
    descending = descendingArray[0] * 1000 + … + descendingArray[3]
	
	diff = descending – raising
	if (diff != 6174)
		cout << diff << ',';
	else
		cout << 6174;
}