快速排序算法
基本思想
快速排序是一类交换排序,它是对起泡排序的一种改进.它的基本思想是, 通过一趟排序将待排记录分割成独立的两个部分, 其中一部分记录的关键字均比另一部分的关键字小, 然后再分别对这两个部分继续进行快速排序, 以达到整个序列有序的目的.
快速排序的工作过程
-
在数组中选择一个关键字作为枢纽(pivot)
这里pivot的选择对快速排序算法的性能启关键性的影响
当每次选中的pivot在执行完一趟快速排序后, 都能使数组中大致一半的记录在pivot的左边, 另一边在pivot的右边, 此时快速排序算法的执行效率最高, 时间复杂度为O(nlogn)
当每次选中的pivot在执行完一趟快速排序后, 都使数组中除pivot外的所有记录都在pivot的一边时, 快速排序算法的执行效率最低, 时间复杂度为O( n^2 )选择pivot的常用方式
选择待排数组的第一个数left和最后一个数right, center = (left + right) / 2, 这里的left, center, right为数组中记录的下标值; 选择center位置的记录为pivot -
划分待排数组元素, 将小于pivot的记录放在pivot的左边, 大于pivot的记录放在pivot的右边
-
重复上述两个步骤, 直到每个划分中的记录个数小于2, 此时待排数组有序, 快速排序算法执行完毕
这里以整型数组A[] = {49, 38, 65, 97, 76, 13, 27}
为例, 演示一趟快速排序算法的执行过程, 即对待排数组的划分过程
选择38作为pivot, 此时数组A的初始状态如下
pivot.png
如果A[low] < pivot, low++
如果A[high] > pivot, high--
如果A[low] >= pivot, A[high] <= pivot, 交换A[low]与A[high]的位置
partition.png
快速排序算法实现
/**
选择pivot并将pivot放到right - 1位置
@param A 待排数组
@param left 左边序号
@param right 右边序号
*/
int Median3(ElementType A[], int left, int right) {
int center = (left + right) / 2;
if (A[left] > A[center]) {
Swap(&A[left], &A[center]);
}
if (A[left] > A[right]) {
Swap(&A[left], &A[right]);
}
if (A[center] < A[right]) {
Swap(&A[center], &A[right]);
}
Swap(&A[center], &A[right - 1]);
return A[right - 1];
}
/**
快速排序
@param A 待排数组
@param left 左边序号
@param right 右边序号
*/
void QuickSort(ElementType A[], int left, int right) {
int pivot = Median3(A, left, right);
int i = left;
int j = right - 1;
for (; ; ) {
while (A[++i] < pivot) {}
while (A[--j] > pivot) {}
if (i < j) {
Swap(&A[i], &A[j]);
} else {
break;
}
}
Swap(&A[i], &A[right - 1]);
QuickSort(A, left, i - 1);
QuickSort(A, i + 1, right);
}
网友评论