转载自:http://blog.csdn.net/wzy_1988/article/details/8043168
前言
今天要重写之前的快排算法,重新翻看自己之前的博客,总是会有稚嫩的感觉,这是好事,说明我一直在进步!
快排是分治策略很好的应用,IT面试大部分都会考察你对快排算法的掌握,博主面试阿里巴巴、创新工厂均在快排算法上有涉及,这里记录一下
算法思想
快速排序采用了一种分治策略,学术上称之为分治法(Divide-and-Conquer Method)
分治的基本思想
将原问题分解成若干个规模更小但是结构跟原问题相似的子问题。递归的解决这些子问题,然后将这些子问题的解合并为原问题的解
快排的思想
设当前需要排序的数组为int A[bt...ed]
分解:
在A[]中任选一个记录作为基准(pivot),以pivot为基准将数组A划分为两个小的数组A[bt...pivot-1]和A[pivot+1...ed],并使左边的数组元素均小于等于pivot,右边数组元素均大于等于piovt。此时,pivot处于正确的位置上,它不需要再参加后续的排序
求解:
递归的调用快速排序,对A[bt...pivot-1]和A[pivot+1...ed]进行快速排序
组合:
跟归并排序不同,因为每次调用快速排序,左右两个数组均已有序,因此对于快速排序来说,组合是一个空操作
实现代码(C语言)
快排用c实现其实可以直接调用系统的qsort函数,自己写compare比较函数即可,在php里是调用usort函数,但是面试考察大部分都是不能调用系统函数的,所以这里提供一下代码,供参考:
-
-
-
-
-
-
-
int pivotLoc(int *arr, int bt, int ed)
-
{
-
int stand;
-
-
stand = arr[bt];
-
-
while (bt < ed) {
-
while (bt < ed && arr[ed] >= stand) ed --;
-
if (bt < ed) arr[bt ++] = arr[ed];
-
-
while (bt < ed && arr[bt] <= stand) bt ++;
-
if (bt < ed) arr[ed --] = arr[bt];
-
}
-
-
arr[bt] = stand;
-
-
return bt;
-
}
-
-
-
-
-
-
-
-
void quickSort(int *arr, int bt, int ed)
-
{
-
int pivot;
-
-
if (bt < ed) {
-
pivot = pivotLoc(arr, bt, ed);
-
quickSort(arr, bt, pivot - 1);
-
quickSort(arr, pivot + 1, ed);
-
}
-
}
优化
快排的平均时间复杂度是O(nlogn),但是考虑一下最坏的情况:
假设给定的排序序列是逆序,例如5、4、3、2、1,然后用上述快排代码进行从小到大排序,很明显,快排从O(nlogn)降到了O(n^2),如何避免这种情况呢?
解答:基准点的随机选取,我这里每次采用mid作为基准点
-
-
-
-
-
void optimizeSort(int *arr, int bt, int ed)
-
{
-
int mid = bt + ((ed - bt) >> 1);
-
-
-
if (arr[bt] != arr[mid]) {
-
arr[bt] = arr[bt] ^ arr[mid];
-
arr[mid] = arr[bt] ^ arr[mid];
-
arr[bt] = arr[bt] ^ arr[mid];
-
}
-
}
-
-
-
-
-
-
-
-
int pivotLoc(int *arr, int bt, int ed)
-
{
-
int stand;
-
-
-
if (bt < ed) {
-
optimizeSort(arr, bt, ed);
-
}
-
-
stand = arr[bt];
-
-
while (bt < ed) {
-
while (bt < ed && arr[ed] >= stand) ed --;
-
if (bt < ed) arr[bt ++] = arr[ed];
-
-
while (bt < ed && arr[bt] <= stand) bt ++;
-
if (bt < ed) arr[ed --] = arr[bt];
-
}
-
-
arr[bt] = stand;
-
-
return bt;
-
}
-
-
-
-
-
-
-
-
void quickSort(int *arr, int bt, int ed)
-
{
-
int pivot;
-
-
if (bt < ed) {
-
pivot = pivotLoc(arr, bt, ed);
-
quickSort(arr, bt, pivot - 1);
-
quickSort(arr, pivot + 1, ed);
-
}
-
}
-
阅读(513) | 评论(0) | 转发(0) |