思想:用过一趟排序将要排序的数据分割成独立的两部分,其中一部分的所有数据都比另外一部分的所有数据要小,然后再对这两部分重复此步骤,直到整个数组变成有序序列.
对一个数组实现一趟快速排序的过程:
1.定义两个变量,一个指向数组最前,一个指向最后,即i=0,j=len-1;
2.将数组的第一个元素的值赋值给key,key=a[0];
3.从j开始向前搜索,直到找到一个小于key的值,然后swap(a[i],a[j]);
4.从i开始向后搜索,直到找到一个大于key的值,然后swap(a[i],a[j]);
5.i=j时退出;
代码如下:
void QuickSortOnce(int a[], int len)
{
int key = a[0];
int i = 0, j = len-1;
while (i!=j)
{
while (a[j] > key)
{
j--;
}
swap(a[j], a[i]);
while (a[i] < key)
{
i++;
}
swap(a[i], a[j]);
}
}
因为这一趟是要被完整的快速排序调用的,所以要知道要排序的一段数组的前后两个下标,同时要返回最后key值所在的位置(即下标)
快排指定区间一次代码:
int QuickSortPart(int a[], int start,int end)
{
int key = a[start];
while (start!=end)
{
while (a[end] > key)
{
end--;
}
swap(a[start], a[end]);
while (a[start] < key)
{
start++;
}
swap(a[start], a[end]);
}
return start;//此时start和end相等,都是key的下标
}
递归部分:
void QuickSortPart2(int a[],int start,int end)
{
int key_position;
if (start<end)//start==end时跳出循环
{
key_position = QuickSortPart(a, start, end);
QuickSortPart2(a, start, key_position - 1);
QuickSortPart2(a, key_position + 1, end);
}
}
快速排序:
void QuickSort(int a[], int len)
{
QuickSortPart2(a, 0, len - 1);
}