開篇：
以下這是一些個(gè)人觀點(diǎn)：
現(xiàn)在前端工作不斷的更新發(fā)展疚膊，改朝換代忽舟，人們往往一直追隨著這個(gè)框架那個(gè)框架的學(xué)習(xí)随闺，慢慢的被 facekbook 日川、google 等公司牽著鼻子走，總感覺是沒有靜下心來分析的時(shí)間了板壮，但是對(duì)于程序員來說逗鸣，什么才是根本呢？所謂程序員根本绰精，首先你得讓你自己成為一個(gè)程序員撒璧，而不是打上標(biāo)簽 xx程序員，因?yàn)檫@只會(huì)令你步伐停止不前笨使，只能觀其表面卿樱，然后給這些所謂的大公司新技術(shù)給慢慢玩死。
慢慢地做開發(fā)也有些時(shí)候了硫椰，做得越久就是越有一種感覺繁调，就是回歸本質(zhì)萨蚕，但是我們常說的本質(zhì)是什么呢？個(gè)人認(rèn)為本質(zhì)既為基礎(chǔ)蹄胰，而基礎(chǔ)分為：數(shù)據(jù)庫(kù)岳遥，算法，數(shù)據(jù)結(jié)構(gòu)裕寨，編譯原理浩蓉，網(wǎng)絡(luò)原理。所以作為一個(gè)有情懷的程序員宾袜，還是必須好好補(bǔ)一下這方面的知識(shí)捻艳。
那么，這個(gè)文集庆猫，我們就說一說數(shù)據(jù)結(jié)構(gòu)和算法认轨，究竟什么是數(shù)據(jù)結(jié)構(gòu)呢？ 數(shù)據(jù)結(jié)構(gòu)是算法的副產(chǎn)物月培，它只是讓我們更好的明白算法的本質(zhì)嘁字，和更好的夠造出更高性能的算法，以下节视，我們就先來說一說三個(gè)基礎(chǔ)算法拳锚。
1 、 選擇排序算法
插入排序的理解： 首先,找到數(shù)組中最小的那個(gè)元素 ,其次,將它和數(shù)組的第一個(gè)元素位置 (如果第一個(gè)元 就是最小元 那么它就和自己 )寻行。再次,在剩下的元素中找到最小的元素, 將它與數(shù)組的第二個(gè)元素交換位置霍掺。如此反復(fù), 到將整個(gè)數(shù)組排序。這種方法叫做做選擇排序,因?yàn)樗诓粩嗟剡x擇剩余元素之中的最小者拌蜘。
解析：對(duì)于長(zhǎng)度為 N 的數(shù)組,選擇排序需要大約 N^2/2 次比較和 N 次交換杆烁。
圖解：
聲明：
NSMutableArray *selectSort(NSMutableArray *array, int start)
實(shí)現(xiàn)：
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;
}
調(diào)用：
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
選擇排序優(yōu)勢(shì)：穩(wěn)定，它的比較次數(shù)基本上不會(huì)改變简卧，數(shù)據(jù)移動(dòng)比較少兔魂。
選擇排序劣勢(shì)：操作級(jí)別了指數(shù)級(jí)，不會(huì)因是否有序數(shù)組而改變排序時(shí)間举娩，時(shí)間只會(huì)與數(shù)組長(zhǎng)度有關(guān)系析校。
2、插入排序
插入排序的理解：由數(shù)組的第2個(gè)位置開始比較铜涉，若果前方位置的元素比較大智玻，則交換位置，若自己元素較大芙代，而繼續(xù)下一個(gè)元素吊奢，如此排列，那么被操作的那個(gè)元素前方位置的所有元素皆為有序纹烹。
解析：對(duì)于隨機(jī)排列的長(zhǎng)度為 N 且主鍵不重復(fù)的數(shù)組,平均情況下插入排序需要~ N^2/4 次比較以及~ N^2/4 次交換页滚。最壞情況下需要~ N^2/2 次比較和~ N^2/2 次交換,最好情況下需要 N-1次比較和 0 次交換召边。
插入排序需要的交換操作和數(shù)組中倒置的數(shù)量相同,需要的比較次數(shù)大于等于倒置的數(shù)量,小于等于倒置的數(shù)量加上數(shù)組的大小再減一。
圖解：
聲明：
NSMutableArray *InsetSort(NSMutableArray *mArray, NSInteger start)
實(shí)現(xiàn)：
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;
}
調(diào)用：
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
插入排序優(yōu)勢(shì)：對(duì)于有序數(shù)組或部分有序數(shù)組，此排序方法是十分高效的踱稍，很適合小規(guī)模的數(shù)組曲饱，很多高級(jí)的排序算法都會(huì)利用到插入排序。
插入排序劣勢(shì)：若果最少的元素都在最后部分的位置珠月，那么該排序方法就會(huì)變得非常費(fèi)勁了扩淀，最后的元素都要比較改元素位置減一次。
3桥温、希爾排序
希爾排序?yàn)槭裁串a(chǎn)生：希爾排序是以插入排序?yàn)榛A(chǔ)的一種快速的排序算法引矩。因?yàn)樵诖笠?guī)模亂序數(shù)組中使用插入排序很慢，因?yàn)樗粫?huì)交換相鄰的兩個(gè)元素侵浸，因此，如果越小的元素越是靠后氛谜，那么操作的復(fù)雜度將會(huì)大大提升掏觉，所以，人們把插入排序進(jìn)行了改良值漫，變成了希爾排序澳腹。
希爾排序的思想：希爾排序的思想是使數(shù)組中任意間隔為 h 的元素都是有序的。這樣的數(shù)組為 h 有序數(shù)組杨何。換句話說,一個(gè) h 有序數(shù)組就是 h 個(gè)互相獨(dú) 的有序數(shù)組編織在一起 成的一個(gè)數(shù)組酱塔。在進(jìn)行排序時(shí),如果 h 很大,我們就能將元素動(dòng)到很遠(yuǎn)的地方,為實(shí)現(xiàn)更小的 h 有序創(chuàng)造方便。用這種方式,對(duì)于任意以 1 結(jié)尾的 h 序列,我們都能夠?qū)?shù)組排序危虱。這就是希爾排序羊娃。
圖解：
前方高能。埃跷。蕊玷。最后一個(gè)算法，用的C語(yǔ)言弥雹。
聲明：
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("數(shù)組越界了");
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);
}
}
}
}
}
}
調(diào)用:
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]);
}
輸出過程：
原數(shù)組: 49 38 65 97 26 13 27 49 55 4
第一次輸出：gap = 5 / 2 = 2垃帅，數(shù)組為： 13 27 49 55 4 49 38 65 97 26
第二次輸出：gap = 2 / 2 = 1，數(shù)組為：4 26 13 27 38 49 49 55 97 65
第三次輸出：gap = 1 / 2 = 0剪勿，數(shù)組為：4 13 26 27 38 49 49 55 65 97
希爾排序優(yōu)勢(shì)：希爾排序優(yōu)化了插入排序贸诚，在性能上比選擇排序和插入排序快得多，而這種優(yōu)勢(shì)會(huì)隨著數(shù)組越大變得越為明顯。而且算法代碼短簡(jiǎn)單酱固，非常容易實(shí)現(xiàn)械念，所以我們基本上所有排序工作一開始都是用希爾排序，若在實(shí)際中不夠快媒怯，我們?cè)俑某煽焖倥判虻雀鼮楦呒?jí)的算法订讼。
希爾排序劣勢(shì)： 排序時(shí)間復(fù)雜度的下界是n*log2n。希爾排序沒有快速排序算法快 O(n(logn))扇苞，因此中等大小規(guī)模表現(xiàn)良好欺殿，對(duì)規(guī)模非常大的數(shù)據(jù)排序不是最優(yōu)選擇。
好了鳖敷，基礎(chǔ)排序的三種算法就為以上三種了脖苏，希望大家都能看懂。
@end
