您现在的位置是:首页 >技术教程 >这个 快速排序详解过程 我能吹一辈子!网站首页技术教程
这个 快速排序详解过程 我能吹一辈子!
快速排序概念
快速排序是公认的排序之王,快速排序是Hoare于1962年提出的一种二叉树结构的交换排序算法,其基本思想为:
任取待排序元素序列中的某元素作为基准值,按照该基准值将待排序列分为两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后左右序列重复该过程,直到所有元素都排列在相应位置上为止。
对于如何按照基准值将待排序列分为两子序列,常见的方式有:
1、Hoare版本
2、挖坑法
3、前后指针法
快速排序递归实现
Hoare版本
单趟的动图演示:
Hoare版本的单趟排序的基本步骤如下:
1、选出一个key,一般是最左边或是最右边的。
2、定义一个L和一个R,L从左向右走,R从右向左走。(需要注意的是:若选择最左边的数据作为key,则需要R先走;若选择最右边的数据作为key,则需要L先走)。
3、在走的过程中,若R遇到小于key的数,则停下,L开始走,直到L遇到一个大于key的数时,将L和R的内容交换,R再次开始走,如此进行下去,直到L和R最终相遇,此时将相遇点的内容与key交换即可。(选取最左边的值作为key)
经过一次单趟排序,最终使得key左边的数据全部都小于key,key右边的数据全部都大于key。
然后我们在将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作,因为这种序列可以认为是有序的。
代码示例:
//快速排序(Hoare版本)
void QuickSort1(int* a, int begin, int end)
{
if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
return;
int left = begin;//L
int right = end;//R
int keyi = left;//key的下标
while (left < right)
{
//right先走,找小
while (left < right&&a[right] >= a[keyi])
{
right--;
}
//left后走,找大
while (left < right&&a[left] <= a[keyi])
{
left++;
}
if (left < right)//交换left和right的值
{
Swap(&a[left], &a[right]);
}
}
int meeti = left;//L和R的相遇点
Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值
QuickSort1(a, begin, meeti - 1);//key的左序列进行此操作
QuickSort1(a, meeti + 1, end);//key的右序列进行此操作
}
时间复杂度:O(N*logN)
挖坑法
单趟的动图演示:
挖坑法的单趟排序的基本步骤如下:
1、选出一个数据(一般是最左边或是最右边的)存放在key变量中,在该数据位置形成一个坑。
2、还是定义一个L和一个R,L从左向右走,R从右向左走。(若在最左边挖坑,则需要R先走;若在最右边挖坑,则需要L先走)。
3、在走的过程中,若R遇到小于key的数,则将该数抛入坑位,并在此处形成一个坑位,这时L再向后走,若遇到大于key的数,则将其抛入坑位,又形成一个坑位,如此循环下去,直到最终L和R相遇,这时将key抛入坑位即可。(选取最左边的作为坑位)
经过一次单趟排序,最终也使得key左边的数据全部都小于key,key右边的数据全部都大于key。
然后也是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作。
代码示例:
//快速排序(挖坑法)
void QuickSort2(int* a, int begin, int end)
{
if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
return;
int left = begin;//L
int right = end;//R
int key = a[left];//在最左边形成一个坑位
while (left < right)
{
//right向左,找小
while (left < right&&a[right] >= key)
{
right--;
}
//填坑
a[left] = a[right];
//left向右,找大
while (left < right&&a[left] <= key)
{
left++;
}
//填坑
a[right] = a[left];
}
int meeti = left;//L和R的相遇点
a[meeti] = key;//将key抛入坑位
QuickSort2(a, begin, meeti - 1);//key的左序列进行此操作
QuickSort2(a, meeti + 1, end);//key的右序列进行此操作
}
时间复杂度:O(N*logN)
前后指针法
单趟的动图演示:
前后指针法的单趟排序的基本步骤如下:
1、选出一个key,一般是最左边或是最右边的。
2、起始时,prev指针指向序列开头,cur指针指向prev+1。
3、若cur指向的内容小于key,则prev先向后移动一位,然后交换prev和cur指针指向的内容,然后cur指针++;若cur指向的内容大于key,则cur指针直接++。如此进行下去,直到cur指针越界,此时将key和prev指针指向的内容交换即可。
经过一次单趟排序,最终也能使得key左边的数据全部都小于key,key右边的数据全部都大于key。
然后也还是将key的左序列和右序列再次进行这种单趟排序,如此反复操作下去,直到左右序列只有一个数据,或是左右序列不存在时,便停止操作。
代码示例:
//快速排序(前后指针法)
void QuickSort3(int* a, int begin, int end)
{
if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
return;
//三数取中
int midIndex = GetMidIndex(a, begin, end);
Swap(&a[begin], &a[midIndex]);
int prev = begin;
int cur = begin + 1;
int keyi = begin;
while (cur <= end)//当cur未越界时继续
{
if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
int meeti = prev;//cur越界时,prev的位置
Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
QuickSort3(a, begin, meeti - 1);//key的左序列进行此操作
QuickSort3(a, meeti + 1, end);//key的右序列进行此操作
}
时间复杂度:O(N*logN)
快速排序非递归实现
当我们需要将一个用递归实现的算法改为非递归时,一般需要借用一个数据结构,那就是栈。将Hoare版本、挖坑法以及前后指针法的快速排序改为非递归版本,其实主体思想一致,只是调用的单趟排序的算法不同而已。
于是我们可以先将Hoare版本、挖坑法和前后指针法的单趟排序单独封装起来。然后写一个非递归的快速排序,在函数内部调用单趟排序的函数即可。
Hoare版本
Hoare版本的单趟排序代码:
//Hoare版本(单趟排序)
int PartSort1(int* a, int left, int right)
{
int keyi = left;//key的下标
while (left < right)
{
//right走,找小
while (left < right&&a[right] >= a[keyi])
{
right--;
}
//left先走,找大
while (left < right&&a[left] <= a[keyi])
{
left++;
}
if (left < right)
{
Swap(&a[left], &a[right]);//交换left和right的值
}
}
int meeti = left;//L和R的相遇点
Swap(&a[keyi], &a[meeti]);//交换key和相遇点的值
return meeti;//返回相遇点,即key的当前位置
}
挖坑法
挖坑法的单趟排序代码:
//挖坑法(单趟排序)
int PartSort2(int* a, int left, int right)
{
int key = a[left];//在最左边形成一个坑位
while (left < right)
{
//right向左,找小
while (left < right&&a[right] >= key)
{
right--;
}
//填坑
a[left] = a[right];
//left向右,找大
while (left < right&&a[left] <= key)
{
left++;
}
//填坑
a[right] = a[left];
}
int meeti = left;//L和R的相遇点
a[meeti] = key;//将key抛入坑位
return meeti;//返回key的当前位置
}
前后指针法
前后指针法的单趟排序代码:
//前后指针法(单趟排序)
int PartSort3(int* a, int left, int right)
{
int prev = left;
int cur = left + 1;
int keyi = left;
while (cur <= right)//当cur未越界时继续
{
if (a[cur] < a[keyi] && ++prev != cur)//cur指向的内容小于key
{
Swap(&a[prev], &a[cur]);
}
cur++;
}
int meeti = prev;//cur越界时,prev的位置
Swap(&a[keyi], &a[meeti]);//交换key和prev指针指向的内容
return meeti;//返回key的当前位置
}
快速排序的非递归算法基本思路:
1、先将待排序列的第一个元素的下标和最后一个元素的下标入栈。
2、当栈不为空时,读取栈中的信息(一次读取两个:一个是L,另一个是R),然后调用某一版本的单趟排序,排完后获得了key的下标,然后判断key的左序列和右序列是否还需要排序,若还需要排序,就将相应序列的L和R入栈;若不需排序了(序列只有一个元素或是不存在),就不需要将该序列的信息入栈。
3、反复执行步骤2,直到栈为空为止。
代码示例:
//快速排序(非递归实现)
void QuickSortNonR(int* a, int begin, int end)
{
Stack st;//创建栈
StackInit(&st);//初始化栈
StackPush(&st, begin);//待排序列的L
StackPush(&st, end);//待排序列的R
while (!StackEmpty(&st))
{
int right = StackTop(&st);//读取R
StackPop(&st);//出栈
int left = StackTop(&st);//读取L
StackPop(&st);//出栈
//该处调用的是Hoare版本的单趟排序
int keyi = PartSort1(a, left, right);
if (left < keyi - 1)//该序列的左序列还需要排序
{
StackPush(&st, left);//左序列的L入栈
StackPush(&st, keyi - 1);//左序列的R入栈
}
if (keyi + 1 < right)// 该序列的右序列还需要排序
{
StackPush(&st, keyi + 1);//右序列的L入栈
StackPush(&st, right);//右序列的R入栈
}
}
StackDestroy(&st);//销毁栈
}
时间复杂度:O(N*logN)
快速排序的俩个优化
三数取中
快速排序的时间复杂度是O(NlogN),是我们在理想情况下计算的结果。在理想情况下,我们每次进行完单趟排序后,key的左序列与右序列的长度都相同:
若每趟排序所选的key都正好是该序列的中间值,即单趟排序结束后key位于序列正中间,那么快速排序的时间复杂度就是O(NlogN)。
可是谁能保证你每次选取的key都是正中间的那个数呢?当待排序列本就是一个有序的序列时,我们若是依然每次都选取最左边或是最右边的数作为key,那么快速排序的效率将达到最低:
可以看到,这种情况下,快速排序的时间复杂度退化为O(N2)。其实,对快速排序效率影响最大的就是选取的key,若选取的key越接近中间位置,则则效率越高。
为了避免这种极端情况的发生,于是出现了三数取中:
三数取中,当中的三数指的是:最左边的数、最右边的数以及中间位置的数。三数取中就是取这三个数当中,值的大小居中的那个数作为该趟排序的key。这就确保了我们所选取的数不会是序列中的最大或是最小值了。
代码示例:
//三数取中
int GetMidIndex(int* a, int left, int right)
{
int mid = left + (right - left) / 2;
if (a[mid] > a[left])
{
if (a[mid] < a[right])
return mid;
else if (a[left]>a[right])
return left;
else
return right;
}
else
{
if (a[mid] > a[right])
return mid;
else if (a[left] > a[right])
return right;
else
return left;
}
}
注意:当大小居中的数不在序列的最左或是最右端时,我们不是就以居中数的位置作为key的位置,而是将key的值与最左端的值进行交换,这样key就还是位于最左端了,所写代码就无需改变,而只需在单趟排序代码开头加上以下两句代码即可:
int midIndex = GetMidIndex(a, begin, end);//获取大小居中的数的下标
Swap(&a[begin], &a[midIndex]);//将该数与序列最左端的数据交换
//以下代码保持不变...
小区间优化
我们可以看到,就算是上面理想状态下的快速排序,也不能避免随着递归的深入,每一层的递归次数会以2倍的形式快速增长。
为了减少递归树的最后几层递归,我们可以设置一个判断语句,当序列的长度小于某个数的时候就不再进行快速排序,转而使用其他种类的排序。小区间优化若是使用得当的话,会在一定程度上加快快速排序的效率,而且待排序列的长度越长,该效果越明显。
代码示例:
//优化后的快速排序
void QuickSort0(int* a, int begin, int end)
{
if (begin >= end)//当只有一个数据或是序列不存在时,不需要进行操作
return;
if (end - begin + 1 > 20)//可自行调整
{
//可调用快速排序的单趟排序三种中的任意一种
//int keyi = PartSort1(a, begin, end);
//int keyi = PartSort2(a, begin, end);
int keyi = PartSort3(a, begin, end);
QuickSort(a, begin, keyi - 1);//key的左序列进行此操作
QuickSort(a, keyi + 1, end);//key的右序列进行此操作
}
else
{
//HeapSort(a, end - begin + 1);
ShellSort(a, end - begin + 1);//当序列长度小于等于20时,使用希尔排序
}
}