《算法三部曲》 之 排序和查找算法（上篇）

Knuth学徒

排序和查找算法目录:
      

中篇:https://www.chinapyg.com/viewthread.php?tid=62641

        这是三部曲中的第二部，之前有过了搜索算法的三章，排序算法不知道是否有必要细说。

        因为排序算法在应用的过程中比搜索算法简单的多，本来想考虑先介绍图论算法的，不过对于大部分人在没有基础的前提下，图论算法显得有点空中阁楼了。

       个人觉得，第一部曲的搜索算法和本篇的排序算法以及查找算法是作为程序员必备的算法功底之一. 因为程序员就是用程序来解决问题，程序就是把算法用计算机语言表示出来，所以基本的算法是必备的。

       这里先介绍下众人熟知的冒泡排序算法：
       对于一个顺序存储的数组 val[Max_num] ,将它进行从小到大的排序, 我们可以这样:

1. bool flag;
   
2. for(int i = 0; i < N - 1  ; ++i )
   
3. {
   
4.        flag  = true;                     //监视变量，如果当前循环未发生交换，排序停止
   
5.        for(int j = 0 ; j < N - i - 1 ; ++ j )
   
6.        {
   
7.                if( val[j] < val[j+1] ) {
   
8.                       swap ( val[j],val[j+1]);
   
9.                       flag = false;
   
10.                }
    
11.         }
    
12.         if(flag) break;
    
13. }

复制代码

由于排序算法非常注重效率，所以这里再简要的补充一下“如何评定一个算法的效率”的方法。

       我们假设一个函数 T(N) ，用它来表示 “在数据量为 N 时，这个算法所需要的基本执行次数”

       那么对于冒泡排序，T(N) 怎么计算呢？

       一共有两个 for 循环 ，最里层的循环体是 if 语句，if 语句中一共执行了3个命令。  同时，for 的 j 循环一共执行了N-i-1次，而 for 的 i 循环一共执行了 N-1 次，所以 T(N) = 3*( N- 1 + N -2 + N-3 + ...... + 3 + 2 + 1 ) = 3*(N-1)*N / 2

       我们可以发现 这里的 T(N) 是关于自变量 "N" 的二次函数, 我们暂且把它看成 N^2 , 用符号作为 θ ( N^2 ) , 这里的
“θ (N^2)”就是所谓的“时间复杂度”.

      //  上面的那段话看懂了么？   没看懂没关系，因为是第一次接触算法分析，直接跳过即可

      我们可以再举几个 θ(N^2) 效率的排序算法，比如：直接插入排序、选择排序 等

      这些排序算法都是简单易懂的，但这绝不是我要说的重点，我们要追求更快的算法。

      下面引出快速排序算法:

      之所以叫“快速排序”，说明它的速度一定很“快”了.. 呵呵，是这样没错，它比起以上的排序算法，要快的多！

      待排序数组：val [Max];

      快速排序的思想是：先把 val 数组变成 两部分，使得左边部分的所有元素 都小于 右边部分的所有元素，然后递归的处理那两部分，这样迭代下去，整个数组就变得有序了——即，对于任何一个区间，所有左边的元素都小于右边的，那是不是就相当于有序了呢？

      那如何 才能把 一个区间分成两部分，并做到左边的小于右边呢？

      我们可以这样：用两个指针 i 和 j , 一开始 i 指向区间左端点,  j  指向区间右端点 , 然后把 i 和j 往中间靠拢，顺便使得 i 左边的元素 都小于 j  右边的元素.
     具体怎么做呢？  请看代码:

1. 
   
2. void  Qsort(int val[], int left , int right )  //将区间 [left, right]分成两部分，递归进行
   
3. {
   
4.        int i (left) , j (right) ;
   
5.        int k( val[left] );
   
6.        while( i < j )
   
7.        {
   
8.                while( i < j && k <= val[ j ] )  j -- ;  
   
9.                //从右往左找第一个比 k 小的
   
10.                if ( i < j ) {
    
11.                       val[ i ] = val[ j ];
    
12.                       i ++;
    
13.                }
    
14.                while( i < j && val[ i ] < k ) i ++;
    
15.                // 再从左往右找第一个比 k 大的
    
16.                if ( i < j) {
    
17.                       val[ j ] = val[ i ];
    
18.                       j --;
    
19.                }
    
20.        }
    
21.        val[ i ] = k ;  //此时的 i == j , 即是中线
    
22.        if ( i > left ) Qsort( val , left , i -1 );    //递归左部分
    
23.        if ( i < right ) Qsort(val , i , right ) ;   //递归右部分
    
24. }
    

复制代码

以上就是快排的主要代码，这里说明一下为什么 快速排序比 其他排序方式要快一点，我们假设每次中线都在区间的中点，那么，T( N ) 就是由此递推定义的：

             T (N) = 2*T(N/2) + N

       如果要求出 T(N) 的表达式，我们才能够知道它的效率，不过这些都是数学上面的东西，不宜多说，我就简要给个结论.

       T (N) = N*log2(N) + N , 记作 θ(N*log2(N))

       我们可以发现 相对于 冒泡排序的 θ(N^2) , N*logN 远远小于 N*N, 因为对数函数的图像趋势要远远慢于一次函数的增长趋势.

       对于排序算法, 我只准备介绍 快速排序 和 堆排序，这两个方法都是 θ(N*log2(N) ) 的高效复杂度，但是也有其他的一样高效的排序算法，但是不常用, 我也就不细说了，因为要完全说透一个快排已经很累了……估计还有很多人没理解，其他不实用的方法对大家也都没意义了。

    ///////////////////////////////////////////////

    不知道还有多少人记得 搜索算法的大概，我总觉得我已经尽可能的说的明白了，有些东西也不是一朝一夕能够理解的。
    这和语言一样需要过程，还需要其他的诸如  数学的基础.

    算法这东西讲起来实在太麻烦，它的麻烦主要 在理解上，一个好的算法为什么是好，三言两语说不清，需要用公式去证明它好，证明它效率高，同时还需要实践。

    当然了，所有算法都是要有它的用武之地，不然没必要发明出来，我总是从应用的角度来考虑它，再中篇我介绍完堆排序之后，我就会介绍查找，查找和排序是一对 好基友~~~

   上篇到此为止，谢谢。

    //////////////////////////////////////////////

Knuth学徒

自己顶一个

yhtjay

/:017最爱看你的帖！都是数据结构和算法，大爱啊！

qifeng09

楼主写的很详细，谢谢

Knuth学徒

回复 3# yhtjay


    这几天开学了，专业课很忙，一直没有时间续写 算法三部曲了…… 让你失望了

Knuth学徒

终于更新了.

Knuth学徒

终于更新排序算法了

Doris

这个一定要学习

jmgsdz

好好学习天天向上