排序算法及优化举例

た入场券 2022-09-24 04:24 186阅读 0赞

（1）插入排序，对于大部分有序或者规模较小的问题，使用插入排序，效率是很高的。

for (i = l ; i < n ; i++)
    {
    
        for(j = i; j > 0 && x[j-1] < x[j] ; j--)
        {
             swap(j-1,j);
        }
    }

优化部分：  
如上代码十分简单的实现插入排序，不过大量在循环体内部调用函数并不是很好的选择，因此swap(j-1,j)用如下替代：

t = x[j];
     x[j] = x[j-1];
     x[j-1] = t;

再观察，实际第一条和最后一条赋值语句又可以拿出内循环，最终得到：

for (i = l ; i < n ; i++)
    {
        t = x[i];
        for(j = i; j > 0 && x[j-1] < x[j] ; j--)
             x[j] = x[j-1];
        x[j] = t;//此处的j是上面循环跳出之后的j，进行过j--
    }

（2）快速排序  
快速排序中运用到了分治的思想，将待排数组分成两个部分，然后对它们进行递归。常见的快速排序有很多种，有单向进行扫描的，接下来列举的是双向扫描的快速排序，在非随机的输入上性能有很大提升。

void qsort(int l ,int u)
    {
        if (u < 1)
            return -1;
        int i = l+1,j = u;
        int t = x[l];
        while(x[i] < t && i <= u)
            i++;//遇到比标记值大的停止扫描
        while(x[j] > t)
            j--;
        if (i > j)
            break;
        swap(i,j);//此上三行不要忽略，扫描一次结束，对不合格位置换位
        //一次扫描结束
        swap(l,j);
        qsort(l,j-1);
        qsort(j+1,u);
    
    
    }

然而，仔细考虑，上诉快速排序仍可以调优，对于随机输入，没有什么问题，但是对于一些输入部分升序的情况，就会效果很不好，可以使用随机生成的方式来解决，随机选择算法的起始位置：

swap(l,randint(l,u));

还有一个问题就是快速排序对于处理较小数组问题时效率不如插入排序，因此，我们可以设置一个门限，当待处理问题规模变得较小时调用插入排序解决：

if ((u - l)<threshold)
        return

最后还可以优化的部分就是可以将循环层内的swap函数改写成内联代码。  
实际上，C++标准库中的sort函数已经十分高效，不过当因为某些条件，系统的函数不能解决问题时，还是需要我们自己“造轮子”的。

排序方法还有很多，陆续在之后博客中进行介绍。