每次提起快排，内心中都有点隐隐作痛。
当时腾讯的那个面试官让我写快排的前两遍排序结果，结果，我当时居然没写上来……
这个，就是所谓的关键时刻掉链子吧，这么经典的快排都不会，真是丢死人了……
今天在实验室的时候我第三次不借助任何资料，根据快排思想，写出了快排的程序~
先看看我第二次的那篇文章，第一次完成的已经不知道被我丢哪里去了~
1 void qsort(int * array, int length) 2 { 3if(length <= 1) 4 return; 5int i = 0,j = length - 1; 6int Addr = 0; 7int KeyWord = array[0];//the first number to be sort 8while(i < j) 9{10 while(array[j] >= KeyWord && j > i)11 -- j;12 swap(array[j], array[i]);13 while(array[i] <= KeyWord && j > i)14 ++ i;15 swap(array[i], array[j]);16}17qsort(array, i);18qsort(&array[i] + 1, length - i - 1);19 }
再看看我第二次写的代码，也就是今天写的。
1 void qsort(int * parray, int size) 2 { 3if(size <= 1) 4 return; 5int npLocal = 0; 6int npCmp = size - 1; 7while(npLocal < npCmp) 8{ 9 for(;npCmp > npLocal;-- npCmp)10 {11 if(parray[npCmp] >= parray[npLocal])12 continue;13 else14 break;15 }16 swap(parray[npCmp], parray[npLocal]);17 //swap之后，npCpm和npLocal指向相反18 for(;npLocal < npCmp;npLocal ++)19 {20 if(parray[npLocal] <= parray[npCmp])21 continue;22 else23 break;24 }25 swap(parray[npCmp], parray[npLocal]);26}27qsort(parray, npLocal);28qsort(parray + npLocal + 1, size - npLocal - 1);29 }
比较之后，感觉，两段代码貌似差别不大，结构和递归形式基本一致。我觉得还是因为今天的代码收到了以前的影响吧，不过这个结构我觉得还可以，至少看着还是挺明朗的。
在写代码之前，我的习惯基本就是，先拿出笔和纸，写一写，弄清楚步骤，至少在写代码之前，要自己明白具体是怎么一回事。
我认为在还没有明白算法的情况下就开始写代码，是很低效的。谋而后动，效率肯定会更高。
快排之所以这么重要，我觉得主要还是因为其非凡的速度。
举个例子：排10w个整数的时候，我的计算机用选择排序和起泡法排序的速度基本都是在32秒左右，单线程。
而改用快排之后，时间好像在0.5秒以内。这个速度还是包含了10w个数的rand函数初始化的。
这个速度简直就是无与伦比~我是很佩服的。
接下来看今天写的另外一个算法：二分查找
二分查找也是因为效率了。对于一个已排序的线性队列使用二分法查找，最慢次数为log2N，可以说是最快的查找方式之一了。
当然了，如果是双线程，就更快了。
接着看代码：
1 int bSearch(int * parray, int size, const int objval) 2 { 3if(size <= 1) 4 return 0; 5int start = 0; 6int mid = size / 2; 7int end = size - 1; 8while(objval != parray[mid]) 9{10 if(mid == end)11 {12 if(objval == parray[start])13 return start;14 else15 return -1;16 }17 if(mid == start)18 {19 if(objval == parray[end])20 return end;21 else22 return -1;23 }24 if(objval > parray[mid])25 {26 start = mid;27 mid += (end - start) / 2;28 }29 else30 {31 end = mid;32 mid -= (end - start) / 2;33 }34}35return mid;36 }
代码中使用了三个变量：start mid end三个变量来进行区间划分，效果还挺不错的。
其中，在边界上，会出现两种情况：start == mid 以及mid == end的情况。这个情况的出现，是因为当end - start == 1的时候，就会出现1 / 2 == 0的情况，此时mid的值是无法更新的。所以要对这种情况专门进行处理，所有就出现了代码中循环语句最上面的两个if比较了。
今天在写着两个算法的时候，都出现了走歪路的情况，不过，觉得，还是挺有意义的。
其实二分法还有一个不错的设想，就是用单地址根据比较结果进行增减，来比较值，但是因为会出现有空缺值无法访问的情况，所以放弃了那种形式，但思想还是不错的。
就到这啦，最近是要重学数据结构的，原因很简单：这东西长时间不设计，肯定会忘~
