导
算法是很重要的，之前在看《算法导论》的时候，基本上是不知所错。后来买了《啊哈，算法》。补补简单的算法知识。
在这本书学习完成之后，想再去看《算法导论》可能会好一些。如果大家还有好的书推荐，请留言。十分感谢。
之前粗略的看过一遍，但是老话说的好：好记性，不如烂笔头。还是记下来，熟悉一遍。印象深刻。
这本书，作者很是用心，用了很多巧妙的比喻，而且配图也很好玩，很好理解。
这一章作者主要讲了三个算法：桶排序，冒泡排序，快速排序。
桶排序：
现在有一个数组a[5] = {6,4,6,3,8},5个元素不大于10。0~10是11个数，那么我们就拿11一个洗脚桶，分别是0号到10号，桶里面什么都没有。找来5根筷子，筷子分别标注a数组中的数字大小。然后按照筷子上的数字找到相同数字的桶的编号，放进去。之后，我们从0号桶顺序的取里面的筷子，进行一一排列，这样就排序完了，那肯定是3，4，6，6，8了，如果从大到小就从10号桶到0号桶挨个取，那就是8，6，6，4，3了。
如果你要尝试n个0到10的，从大到小或者从小到大排序呢。赶紧写个程序理解下。
// 定义一个数组（11个桶）
int a[11];
// 循环赋值都为0，其实是桶里面什么都没有
for (int z = 0; z < 11; z++)
{
a[z] = 0;
}
// 定义你要比较的元素数组，数组元素值是0~10
// 这个数组里面的值，比如数组中的`7`,其实是对应桶数组中的下标
int b[5] = {7,3,5,1,6};
// 定义筷子t，筷子一直加1，表示有几个相同的值
int t;
// 循环比较的元素数组
for (int z = 0; z < 5; z++)
{
// 对t进行赋值，列如：b[0]是7，那么t=7
t = b[z];
// 也就是a[7]原本是0，现在++，若有3个t=7，那么a[7]的值就是3了
// 如果你还想去重，那直接a[t] = 1；就可以了。
a[t]++;
}
// 进行双循环取值
// 下面是重小到大排序（for (int z = 10; z >= 0; z--) {} 从大到小排序）
for (int z = 0; z < 11; z++)
{
// 相对应的桶里面有几个值
for (int j = 0; j < a[z]; j++)
{
// 打印值
printf("%d\t",z);
}
}
打印的值如下：
1 3 5 6 7
啵~
冒泡排序：
冒泡排序的基本思想是：每次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来！
基本上我们在学习任何语言的时候都会学冒泡排序，直接上代码。
// 要进行排序的源数组
int a[12] = {89,99,23,44,21,43,55,21,1,56,77,98};
// 中间的接受者
int t;
// 冒泡排序的核心代码
for (int z = 0; z < 12 - 1; z++)
{
for (int p = 0; p < 12 - 1; p++)
{
// 进行比较(从打到小排序)
if (a[p] < a[p + 1])
{
// 进行交换
t = a[p];
a[p] = a[p + 1];
a[p + 1] = t;
}
}
}
for (int z = 0; z < 12; z++)
{
printf("%d \t",a[z]);
}
打印的值如下：
99 98 89 77 56 55 44 43 23 21 21 1
快速排序
为什么用
快速排序，作者说：桶排序其实浪费了很多的空间，而冒泡排序可以解决桶排序的浪费空间的问题，但是冒泡排序存在在运行比较很多值排序，则会花费比桶排序多的多的时间。
快速排序：设置基准数，进行
递归式快速归位。
强行理解一波：按照作者的理解我做了一个高低的图，帮助我理解。顺序看图。
以最开始的<6>作为基准数，从左边开始找到一个大的，从右边开始找到一个小的，进行交换。
上面第一次交换完毕。
进行下一次交换。
最终<6>和<3>进行交换。
下面的图，我们看到
6左边的都小于等于6，6最右边的都大于等于6。
然后我们
6左边的再次用上面同样的方法进行，以3为基准交换位置，右边的以9也进行交换位置。这样来回交换。我们就完成了排序了。
作者画了一个很长的图，建议大家可以买书，看看，很好理解。这里只是做笔记，进行自我理解。
就像作者所说我们写个程序来理解一下更好。
// 初始化内容
self.numberArray = [[NSMutableArray alloc] init];
for (int z = 0; z < 100; z++)
{
// 100个100以内
int number = arc4random()%100;
[self.numberArray addObject:[NSNumber numberWithInt:number]];
}
// 输出未排序的数组
for (NSNumber * number in self.numberArray)
{
printf("%d \t",number.intValue);
}
// 左边下表从0开始，右边99开始
[self quickSortWithLeftNumber:0 rightNumber:99];
NSLog(@"%@",self.numberArray);
// 输出结果
for (NSNumber * number in self.numberArray)
{
printf("%d \t",number.intValue);
}
/**
快速排序
*/
- (void)quickSortWithLeftNumber:(int)leftNumber rightNumber:(int)rightNumber
{
if (leftNumber > rightNumber)
{
return;
}
int left_i;
int right_j;
int temp;
int t;
// 基准出
temp = self.numberArray[leftNumber].intValue;
left_i = leftNumber;
right_j = rightNumber;
while (left_i != right_j)
{
// 找右边
while (self.numberArray[right_j].intValue >= temp && left_i < right_j)
{
right_j--;
}
// 找左边
while (self.numberArray[left_i].intValue <= temp && left_i < right_j)
{
left_i++;
}
// 如果达成，则进行数组位置交换
if (left_i < right_j)
{
t = self.numberArray[left_i].intValue;
self.numberArray[left_i] = self.numberArray[right_j];
self.numberArray[right_j] = [NSNumber numberWithInt:t];
}
}
// 进行基准归位
self.numberArray[leftNumber] = self.numberArray[left_i];
self.numberArray[left_i] = [NSNumber numberWithInt:temp];
// 如图，继续处理左边的，进行递归
[self quickSortWithLeftNumber:leftNumber rightNumber:left_i-1];
// 如图，继续处理右边的，进行递归
[self quickSortWithLeftNumber:left_i+1 rightNumber:rightNumber];
}
输出未排序的数组
89 67 10 77 10 55 10 96 9 85 45 45 6 54 31 12 15 67 27 60 38 68 36 3 69 63 26 28 32 7 23 40 50 47 62 55 43 65 33 99 84 24 54 84 79 93 23 30 57 77 62 21 99 14 99 61 93 98 70 73 95 62 47 50 94 42 91 74 49 53 38 73 9 14 50 95 23 95 26 80 84 71 36 1 4 20 41 27 75 45 77 3 99 10 43 93 28 2 15 94
输出排序的结果：
1 2 3 3 4 6 7 9 9 10 10 10 10 12 14 14 15 15 20 21 23 23 23 24 26 26 27 27 28 28 30 31 32 33 36 36 38 38 40 41 42 43 43 45 45 45 47 47 49 50 50 50 53 54 54 55 55 57 60 61 62 62 62 63 65 67 67 68 69 70 71 73 73 74 75 77 77 77 79 80 84 84 84 85 89 91 93 93 93 94 94 95 95 95 96 98 99 99 99 99
