算法开篇课
title: 算法开篇课
date: 2016-10-14 13:13:53
tags: 算法
thumbnail: http://img2.imgtn.bdimg.com/it/u=4054526222,762120886&fm=21&gp=0.jpg
算法开篇介绍：Algorithm，是指解题方案的准确而完整的描述，代表着用系统的方法描述解决问题的策略机制。
最快最简单的排序
首先看题：
班上有5位同学，分别考了5分，3分，5分，8分，2分，将分数从大到小排序是8，5，5，3，2。有什么好的办法可以编写一段程序，让计算机随机读入5个分数然后将这5个分数从大到小输出。老道的程序员可能各种冒泡，打擂台，这都比较深入了，先往下看：
我们借助一个一维数组就可以解决这个问题，创建一个a[11]的数组，这样下标分别为a[0]->a[10]，分别表示0分，1分...10分，每当有一个分数出现，就在对应的下标位置+1，最后打印即可满足我们现在的要求。
int main(int argc, const char * argv[]) {
int a[11];
int scannedNumber;
for (int i = 0; i < 11; i ++) {
a[i] = 0;
}
for (int j = 0; j < 5; j ++) {
scanf("%d", &scannedNumber);
a[scannedNumber] ++;
}
for (int k = 10; k >= 0; k --) {
for (int l = 0; l < a[k]; l ++) {
printf("%d", k);
}
}
return 0;
}
这种排序算法，我们称为桶排序，每个分数都好比一个桶，每出现一次，就在桶中加一点东西。接下来，我们尝试着对数据范围在0~100之间的任意数量数字进行从大到小的排序：
int main(int argc, const char * argv[]) {
int book[101], scannedNumber;
int inputCount;
for (int i = 0; i < 101; i ++) {
book[i] = 0;
}
printf("Enter numbers you want:");
scanf("%d", &inputCount);
for (int j = 0; j < inputCount; j ++) {
scanf("%d", &scannedNumber);
book[scannedNumber] ++;
}
for (int k = 100; k >= 0; k --) {
for (int l = 0; l < book[k]; l ++) {
printf("%d ", k);
}
}
return 0;
}
同样没有什么问题的，我们接下来考虑时间复杂度的问题：代码中第6行，循环了M次（M为桶的个数），第14行循环了N次（输入的数字个数），19行循环了M+N次，所以我们得到时间复杂度为O(2*(M+N))，在说时间复杂度的时候，可以忽略较小的常数，所以最终的时间复杂度为：
O(M+N)
这是一个非常快的排序算法，其实这还不是真正的桶排序，桶排序实际要更复杂，这个只能算简化版。基本上还不能算是一个真正意义的算法，上边的处理如果碰到输出得该分数的同学的信息就显得有点问题了，因为我们只是输出了分数。所以引出第二节：冒泡排序
冒泡排序
简化版的桶排序，不仅仅有使用范围的限制，更是浪费空间，如果我们需要排序的范围是0~2100000000，那就要申请2100000001个变量，我们要用这么多的桶来存储每一个数字出现的次数。即时，你只给3个数字（1， 19999， 1999999）排序，也需要2000001个桶，太浪费了。还不止，如果是浮点型呢？那我们接触一个新的算法，冒泡排序！它可以很好的解决这2个问题。冒泡排序的基本思想是，相邻的2个元素，如果顺序错误就把他们位置互换。如果我们要将
12, 35, 99, 18, 76
这几个数从大到小进行排序，越小的越靠后。
首先：比较第1位和第2位的大小，我们发现12要比35小，所以交换位置，交换后：
35, 12, 99, 18, 76
然后：按照上述的方法，继续往下比较，第2位与第3位....
35, 99, 12, 18, 76
继续：第3位和第4位：
35, 99, 18, 12, 76
继续：第4位和第5位：
35, 99, 18, 76, 12
经过4次比较之后，最小的数字已经到了最后一位，一位一位的比，大的就往前换，就像一个气泡，所以称为冒泡。到这里，我们只是将其中的一个数字归位了，继续重复上面的过程：继续比较第1位与第2位，第2位与第3位，第3位与第4位，你会发现，第5位不需要比较了，因为他已经是最小的了。第二次比较后：
99, 35, 76, 18, 12
接下来的几次都是这样，有几个数字，比较的次数是n-1趟。冒泡的原则是，每次比较只将1个数组归位。接下来我们代码实现：
int main(int argc, const char * argv[]) {
int a[20], scannedNumber, input;
scanf("%d", &input);
for (int i = 1; i <= input; i ++) {
scanf("%d", &scannedNumber);
a[i] = scannedNumber;
}
// 共有INPUT个数字，所以只需要排INPUT-1次即可
for (int i = 1; i <= input - 1; i ++) {
// INPUT-I 意味着，每一次外层循环后，都有一个数字归位
for (int j = 1; j <= input - i ; j ++) {
// 交换
if ( a[j] < a[j + 1] ) {
int temp = a[j];
a[j] = a[j + 1];
a[j + 1] = temp;
}
}
}
for (int i = 1; i <= input; i ++) {
printf("%d ", a[i]);
}
return 0;
}
将上边的代码稍稍修改，就可以解决前面桶排序无法做到的输出学生信息以及浮点数的问题：
struct Student {
char name[20];
float score;
};
int main(int argc, const char * argv[]) {
struct Student s[100];
int scannedNumber;
scanf("%d", &scannedNumber);
for (int i = 1; i <= scannedNumber; i ++) {
scanf("%s %f", s[i].name, &s[i].score);
}
// 控制排序次数
for (int j = 1; j <= scannedNumber - 1; j ++) {
for (int k = 1; k <= scannedNumber - j; k ++) {
if (s[k].score < s[k+1].score) {
struct Student temp = s[k];
s[k] = s[k + 1];
s[k + 1] = temp;
}
}
}
for (int l = 1; l <= scannedNumber; l ++) {
printf("%s, %.2f\n", s[l].name, s[l].score);
}
return 0;
}
完美搞定了。输入：
dylan 81.5
alice 64.6
peter 91.4
bobo 31.9
amy 67
输出：
peter, 91.40
dylan, 81.50
amy, 67.00
alice, 64.60
bobo, 31.90
冒泡排序的核心部分是嵌套循环，不难看出，冒泡循环的复杂度是：
O(N^2)
这是一个很高的时间复杂度，冒泡排序除了它迷人的名字，以时间复杂度来看，没什么好推荐的，想要更好的排序么？
快速排序
冒泡排序算是我们学习的第一个算法，但是时间浪费的极多。假定计算机运行10亿次/秒，桶排序需要10亿+1个位置，但只需要0.1s，冒泡排序则需要1千万秒。接下来我们了解快速排序。首先记住快速排序的核心方法：设，基准数为左边第一个数，保证基准数左边全部比它小，右边全部比它大；所以2个起点，最左边、最右边。共同向中间触发，右边先走（注意，左边为基准数，一定要先从右往左，先想想为什么，后面给出解释），先从右边向左边找一个比基准数小的数字，然后从左边向右边找一个比基准数大的数字，交换他们。当左右碰面的时候，交换当前数字与基准数的位置。当基准数确认位置之后，基准数左边、右边分为2个子列（有一点点2分味道，以后讲），在进行设置基准数，寻找。这里用到了递归，所以我们来模拟一下过程，假定有这样一个数列：
6, 1, 2, 7, 9, 3, 4, 5, 10, 8
我们以最左边的6为初始基准数，从左向右找一个大于6的数，从右向左找一个小于6的数字，并交换，我们发现，从右向左第一个小于6的数字是5，从左向右第一个大于6的数字是7，交换他们的位置
6, 1, 2, 5, 9, 3, 4, 7, 10, 8
接下来，继续向前寻找，左向右发现了9，右向左发现了4，所以交换他们：
6, 1, 2, 5, 4, 3, 9, 7, 10, 8
继续往前，糟了，2个人撞一起了，这个时候，把基准数与这个数字交换位置：
3, 1, 2, 5, 4, 6, 9, 7, 10, 8
这样，基准数字6已经归位，而且左边都是小于6的数字，右边都是大于6的数字。接下来，我们分别处理左边、右边两个数列：
3, 1, 2, 5, 4
9, 7, 10, 8
先处理第一个序列，3为基准数：
i→ ←j
3, 1, 2, 5, 4
得
2, 1, 3, 5, 4
得
子串1： 2, 1 -> 1, 2
子串2： 5, 4 -> 4, 5
因为是右边先开始，所以在2的位置，会碰撞，交换位置即得到了结果。子串9, 7, 10, 8大家自己去分析一下。最终排序结束了。然后我们按照上边的思想来写代码：
int a[11];
int count = 10;
void sort(int left, int right);
int main(int argc, const char * argv[]) {
for (int i = 1; i <= count; i ++) {
scanf("%d", &a[i]);
}
sort(1, count);
for (int j = 1; j <= count; j ++) {
printf("%d ", a[j]);
}
return 0;
}
void sort(int left, int right) {
if ( left > right ) {
return;
}
// 设置基准数
int refNum = a[left];
// 设置左右起点
int lPoint = left;
int rPoint = right;
// 当没有碰撞的时候，不停的交换
while (lPoint != rPoint) {
// 从右边开始找，比基准数小的数字, 然后停止，注意我的判断，如果比基准数大，rPoint向前移动一位，也就是说，如果比基准数字小，rPoint记录的就是这个数字的位置
while (a[rPoint] >= refNum && lPoint < rPoint) {
rPoint --;
}
// 左边找，比基准数大的数字，然后停止
while (a[lPoint] <= refNum && lPoint < rPoint ) {
lPoint ++;
}
// 交换位置
if ( lPoint < rPoint ) {
int temp = a[lPoint];
a[lPoint] = a[rPoint];
a[rPoint] = temp;
}
}
// 归位基准数字，这个时候，左右标记点处于同一个位置上，也就是基准点应该在的位置
a[left] = a[lPoint];
a[lPoint] = refNum;
// 交换之后，开始处理子串，基准数不需要动位置
sort(left, lPoint - 1);
sort(lPoint + 1, right);
return ;
}
现在我们来回顾上边的问题左边为基准数，为什么一定要先从右边开始?
基准数字在左边，假设，左边先开始，找的是比基准数字大的数字：
3, 1, 2, 6, 7
如上，找到数字6的时候，左边停下了，右边开始寻找，发现直接碰撞了，变成了：
6, 1, 2, 3, 7
但是如果从右边开始就会变成
2, 1, 3, 6, 7
总结
排序的算法还有很多，计数、基数、插入、归并、堆排序等，我们在后边会慢慢的涉及到。当然，快排的时间复杂度怎么算呢？我们想想，最差的情况，就是像冒泡一样，相邻的2个数字不停的交换，为：
O(N^2)
快排的最好时间复杂度为（为什么）：
O(NLogN)
由于关键字的比较和交换是跳跃进行的，因此，快速排序是一种不稳定的排序方法。
练习
要求对不定数量的数字进行排序，1秒之内完成。
拿到这道题，我们关注的应当是1s之内，数字是不定量的，我们需要按照上边提供的时间复杂度来讲。假如说现在范围超级大，使用桶排序基本不可能的，因为没法申请那么大的数组，如果数字超级多，使用冒泡排序的时间复杂度又是O(N^2)，但是使用快速排序却很好。代码省略了。
本文结束。
