重学数据结构——快速排序，二分法查找

时间：2022-04-04 22:09:23

每次提起快排，内心中都有点隐隐作痛。

当时腾讯的那个面试官让我写快排的前两遍排序结果，结果，我当时居然没写上来……

这个，就是所谓的关键时刻掉链子吧，这么经典的快排都不会，真是丢死人了……

今天在实验室的时候我第三次不借助任何资料，根据快排思想，写出了快排的程序~

先看看我第二次的那篇文章，第一次完成的已经不知道被我丢哪里去了~

 1 void qsort(int * array, int length)
 2 {
 3     if(length <= 1)
 4         return;
 5     int i = 0,j = length - 1;
 6     int Addr = 0;
 7     int KeyWord = array[0];//the first number to be sort
 8     while(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     }
17     qsort(array, i);
18     qsort(&array[i] + 1, length - i - 1);
19 }

再看看我第二次写的代码，也就是今天写的。

 1 void qsort(int * parray, int size)
 2 {
 3     if(size <= 1)
 4         return;
 5     int npLocal = 0;
 6     int npCmp = size - 1;
 7     while(npLocal < npCmp)
 8     {
 9         for(;npCmp > npLocal;-- npCmp)
10         {
11             if(parray[npCmp] >= parray[npLocal])
12                 continue;
13             else
14                 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             else
23                 break;
24         }
25         swap(parray[npCmp], parray[npLocal]);
26     }
27     qsort(parray, npLocal);
28     qsort(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 {
 3     if(size <= 1)
 4         return 0;
 5     int start = 0;
 6     int mid = size / 2;
 7     int end = size - 1;
 8     while(objval != parray[mid])
 9     {
10         if(mid == end)
11         {
12             if(objval == parray[start])
13                 return start;
14             else
15                 return -1;
16         }
17         if(mid == start)
18         {
19             if(objval == parray[end])
20                 return end;
21             else
22                 return -1;
23         }
24         if(objval > parray[mid])
25         {
26             start = mid;
27             mid += (end - start) / 2;
28         }
29         else
30         {
31             end = mid;
32             mid -= (end - start) / 2;
33         }
34     }
35     return mid;
36 }

代码中使用了三个变量：start mid end三个变量来进行区间划分，效果还挺不错的。

其中，在边界上，会出现两种情况：start == mid 以及mid == end的情况。这个情况的出现，是因为当end - start == 1的时候，就会出现1 / 2 == 0的情况，此时mid的值是无法更新的。所以要对这种情况专门进行处理，所有就出现了代码中循环语句最上面的两个if比较了。

今天在写着两个算法的时候，都出现了走歪路的情况，不过，觉得，还是挺有意义的。

其实二分法还有一个不错的设想，就是用单地址根据比较结果进行增减，来比较值，但是因为会出现有空缺值无法访问的情况，所以放弃了那种形式，但思想还是不错的。

就到这啦，最近是要重学数据结构的，原因很简单：这东西长时间不设计，肯定会忘~

标签：

相关文章