快速排序(quicksort)算法实现

快速排序(quicksort)是分治法的典型例子,它的主要思想是将一个待排序的数组以数组的某一个元素X为轴,使这个轴的左侧元素都比X大,而右侧元素都比X小(从大到小排序)。然后以这个X在变换后数组的位置i分为左右两个子数组,再分别进行快速排序,直到子数组中只有一个元素为止。

快速排序算法如下



Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->, r);
    }   
}

其中partition函数将得到X所在的位置i(在这里总以数组的最后一个元素为轴)。



Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->;
}

由于总是选择数组的最后一个元素做为轴,因此可能出现X的左边为n - 1或接近n - 1个元素,而右边没有元素,或元素很少的情况,即X最大或比较大。这样使quicksort将出现最坏的情况,也就是时间复杂度为O(n^2)。因此partition可以采用随机方式得到轴X的位置i。 这样它的平均情况是非常好的(时间复杂度为O(nlogn)),也就是说,最坏情况很难出现。



Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->int new_random(int min, int max)
{
    return (min + (int)(((float)rand()/RAND_MAX)*(max - min)));
}

int randomize_partition(int A[], int p, int r)
{
    int i = new_random(p, r);
    swap(&A[i], &A[r]);
    return partition(A, p, r);
}

完整的代码如下



Code highlighting produced by Actipro CodeHighlighter (freeware)
http://www.CodeHighlighter.com/

-->;
}

上一篇:centos7


下一篇:windows7 安装python