技术笔试面试

快速排序-最重要的排序算法

昨天笔试google,不甚理想。算法大题用到了快排算法。在这里温故知新一下,以绝后患:D

大家一定对冒泡排序(Bubble Sort)非常熟悉吧,这种排序算法的思路很简单,但是由于时间复杂度比较高(O(n*n)),所以渐渐被更高效的算法所取代。这些高效算法中就包括了著名的快速排序算法(Quick Sort)。

快速排序算法的基本思想是,通过一趟排序将待排记录分隔成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可分别对这两部分记录继续进行排序,以达到整个序列有序。

一趟快速排序的算法是:附设两个指针low和high,它们的初值分别为low和high,设枢轴记录的关键字为pivotkey,则首先从high所指位置起向前搜索找到第一个关键字小于pivotkey的记录和枢轴记录相互交换,然后从low所指位置起向后搜索,找到第一个关键字大于pivotkey的记录和枢轴记录互相交换,重复这两步直至low=high为止。由此可以该“枢轴”记录最后所落的位置i作为分界线,将序列分隔成两个子序列。

实际上low和high可以被理解为位置标志,它们所指向的只是位置。而pivotkey就是一个数值,它被选取被序列中的一个特定元素。在每趟的快排当中,都是low和high所指位置的元素和pivotkey来做比较。

快速排序的算法要分两大块:

第一大块:一趟快速排序的算法程序,我们将其定为一个函数partseq()

第二大块:整个快速排序算法程序,此程序要调用第一大块的partseq函数,而且在这个部分,我们使用了递归算法来实现多趟快排。

===================================================================================

快速排序算法源代码如下:

[rocrocket@wupengchong Sort_Method]$ cat -n Quick_Sort.c
    #include
    #include
    #include

    int partition(int arr[],int low,int high)
    {
    arr[0]=arr[low];
    while(lowarr[0])) high--;
        arr[low]=arr[high];
        while((low

over~

10条评论

  1. 贴代码不是好的方法,起码我不建议这样,毕竟不同的开发人员使用不一样的编程语言,最好就贴算法原型吧,用伪代码来表示,能表达算法的思想就OK了,如果能够随时根据伪代码写出合适的测试代码,这样才是重要的,不论是工作还是面试,都很有用处

  2. 兄弟, 你这个算法有问题

    while(low<high){
    while((lowarr[0])) high–;
    arr[low]=arr[high];
    while((low<high)&&(arr[low] while((low<high)&&(arr[low]<=arr[0])) low++;
    arr[high]=arr[low];

    把注释里那行替换成你的代码, 你少考虑了一个有重复值的情况:)

发表您的评论

请您放心,您的信息会被严格保密。必填项已标识 *