开篇：
以下这是一些个人观点：
现在前端工作不断的更新发展，改朝换代，人们往往一直追随着这个框架那个框架的学习，慢慢的被 facekbook 、google 等公司牵着鼻子走，总感觉是没有静下心来分析的时间了，但是对于程序员来说，什么才是根本呢？所谓程序员根本，首先你得让你自己成为一个程序员，而不是打上标签 xx程序员，因为这只会令你步伐停止不前，只能观其表面，然后给这些所谓的大公司新技术给慢慢玩死。
慢慢地做开发也有些时候了，做得越久就是越有一种感觉，就是回归本质，但是我们常说的本质是什么呢？个人认为本质既为基础，而基础分为：数据库，算法，数据结构，编译原理，网络原理。所以作为一个有情怀的程序员，还是必须好好补一下这方面的知识。
那么，这个文集，我们就说一说数据结构和算法，究竟什么是数据结构呢？ 数据结构是算法的副产物，它只是让我们更好的明白算法的本质，和更好的够造出更高性能的算法，以下，我们就先来说一说三个基础算法。
1 、 选择排序算法
插入排序的理解： 首先,找到数组中最小的那个元素 ,其次,将它和数组的第一个元素位置 (如果第一个元 就是最小元 那么它就和自己 )。再次,在剩下的元素中找到最小的元素, 将它与数组的第二个元素交换位置。如此反复, 到将整个数组排序。这种方法叫做做选择排序,因为它在不断地选择剩余元素之中的最小者。
解析：对于长度为 N 的数组,选择排序需要大约 N^2/2 次比较和 N 次交换。
图解：
声明：
NSMutableArray *selectSort(NSMutableArray *array, int start)
实现：
NSMutableArray *selectSort(NSMutableArray *array, int start) {
if (start == array.count ) {
return array;
}
int minNum = [array[start] intValue];
int minIndex = start;
for (int i = start ; i < array.count; i ++) {
if (minNum > [array[i] intValue]) {
minNum = [array[i] intValue];
minIndex = i;
}
}
[array exchangeObjectAtIndex:start withObjectAtIndex:minIndex];
array = selectSort(array, start + 1);
return array;
}
调用：
NSArray *array = @[@(1), @(4), @(8), @(9), @(5), @(7), @(2)];
array = selectSort([array mutableCopy], 0);
输出过程：
第一次：1, 4, 8, 9, 5, 7, 2
第二次：1, 2, 8, 9, 5, 7, 4
第三次：1, 2, 4, 9, 5, 7, 8
第四次：1, 2, 4, 5, 9, 7, 8
第五次：1, 2, 4, 5, 7, 9, 8
最后输出： 1, 2, 4, 5, 7, 8, 9
选择排序优势：稳定，它的比较次数基本上不会改变，数据移动比较少。
选择排序劣势：操作级别了指数级，不会因是否有序数组而改变排序时间，时间只会与数组长度有关系。
2、插入排序
插入排序的理解：由数组的第2个位置开始比较，若果前方位置的元素比较大，则交换位置，若自己元素较大，而继续下一个元素，如此排列，那么被操作的那个元素前方位置的所有元素皆为有序。
解析：对于随机排列的长度为 N 且主键不重复的数组,平均情况下插入排序需要~ N^2/4 次比较以及~ N^2/4 次交换。最坏情况下需要~ N^2/2 次比较和~ N^2/2 次交换,最好情况下需要 N-1次比较和 0 次交换。
插入排序需要的交换操作和数组中倒置的数量相同,需要的比较次数大于等于倒置的数量,小于等于倒置的数量加上数组的大小再减一。
图解：
声明：
NSMutableArray *InsetSort(NSMutableArray *mArray, NSInteger start)
实现：
NSMutableArray *InsetSort(NSMutableArray *mArray, NSInteger start) {
if (start == mArray.count) {
return mArray;
}
for (NSInteger i = start; i > 0; i --) {
if (mArray[i] < mArray[i-1]) {
int temp = [mArray[i] intValue];
int k = (int)(i - 1);
while (k >= 0 && [mArray[k] intValue] > temp) {
mArray[k + 1] = mArray[k];
k -= 1;
}
mArray[k+1] = @(temp);
}
}
InsetSort(mArray, start + 1);
return mArray;
}
调用：
NSMutableArray *mArray = [@[@(49), @(38), @(65), @(97), @(26), @(13), @(27), @(49), @(55), @(4)] mutableCopy];
mArray = InsetSort(mArray, 1);
输出过程：
第一次：38，49，65，97，26，13，27，49，55，4
第二次：38，49，65，97，26，13，27，49，55，4
第三次：38，49，65，97，26，13，27，49，55，4
第四次：26，38，49，65，97，13，27，49，55，4
第五次：13，26，38，49，65，97，27，49，55，4
第六次：13，26，27，38，49，65，97，49，55，4
第七次：13，26，27，38，49，49，65，97，55，4
第八次：13，26，27，38，49，49，55，65，97，4
最后输出：4， 13， 26， 27， 38， 49，49， 55， 65， 97
插入排序优势：对于有序数组或部分有序数组，此排序方法是十分高效的，很适合小规模的数组，很多高级的排序算法都会利用到插入排序。
插入排序劣势：若果最少的元素都在最后部分的位置，那么该排序方法就会变得非常费劲了，最后的元素都要比较改元素位置减一次。
3、希尔排序
希尔排序为什么产生：希尔排序是以插入排序为基础的一种快速的排序算法。因为在大规模乱序数组中使用插入排序很慢，因为它只会交换相邻的两个元素，因此，如果越小的元素越是靠后，那么操作的复杂度将会大大提升，所以，人们把插入排序进行了改良，变成了希尔排序。
希尔排序的思想：希尔排序的思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组为 h 有序数组。换句话说,一个 h 有序数组就是 h 个互相独 的有序数组编织在一起 成的一个数组。在进行排序时,如果 h 很大,我们就能将元素动到很远的地方,为实现更小的 h 有序创造方便。用这种方式,对于任意以 1 结尾的 h 序列,我们都能够将数组排序。这就是希尔排序。
图解：
前方高能。。。最后一个算法，用的C语言。
声明：
void ShellSort(Array array)
void exchange(Array array, int N, int M) {
int temp = array->a[N];
array->a[N] = array->a[M];
array->a[M] = temp;
}
struct ArrayNode {
int a[kMaxLimit];
int count;
};
void pushNumInArray(Array array, int Num) {
if (array->count > 10) {
printf("数组越界了");
return;
}
array->a[array->count] = Num;
array->count += 1;
}
void ShellSort(Array array) {
for (int gap = array->count / 2; gap > 0; gap/=2) {
for (int i = 0; i < gap; i ++) {
if (array->a[i + gap] < array->a[i]) {
for (int j = i + gap; j < array->count; j += gap) {
if (array->a[j] < array->a[j - gap]) {
// 交换
exchange(array, j, j-gap);
}
}
}
}
}
}
调用:
Array array = malloc(sizeof(struct ArrayNode));
array->count = 0;
for (int i = 0; i < 10; i ++) {
pushNumInArray(array, arc4random() % 100);
}
// 希尔排序
ShellSort(array);
for (int i = 0; i < array->count; i ++) {
printf("%d\n",array->a[i]);
}
输出过程：
原数组: 49 38 65 97 26 13 27 49 55 4
第一次输出：gap = 5 / 2 = 2，数组为： 13 27 49 55 4 49 38 65 97 26
第二次输出：gap = 2 / 2 = 1，数组为：4 26 13 27 38 49 49 55 97 65
第三次输出：gap = 1 / 2 = 0，数组为：4 13 26 27 38 49 49 55 65 97
希尔排序优势：希尔排序优化了插入排序，在性能上比选择排序和插入排序快得多，而这种优势会随着数组越大变得越为明显。而且算法代码短简单，非常容易实现，所以我们基本上所有排序工作一开始都是用希尔排序，若在实际中不够快，我们再改成快速排序等更为高级的算法。
希尔排序劣势： 排序时间复杂度的下界是n*log2n。希尔排序没有快速排序算法快 O(n(logn))，因此中等大小规模表现良好，对规模非常大的数据排序不是最优选择。
好了，基础排序的三种算法就为以上三种了，希望大家都能看懂。
@end
