目录
1.概念
2.快速排序hoare版本
2.1基本思想
2.2解释相遇处的值为何一定小于key
2.3hoare版本快速排序的实现
3.快速排序挖坑法
3.1基本思想
3.2挖坑法快速排序的实现
4. 快速排序前后指针版本
4.1基本思想
4.2快速排序前后指针版本实现
5.快速排序非递归版本
5.1基本思想
5.2快速排序非递归版本实现
6.快速排序的优化
6.1三数取中
6.1.2三数取中代码实现
6.2小区间优化
6.3优化后的代码
7.快速排序的特性总结
1.概念
快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法,其基本思想为:任取待排序元素序列中的某元素(一般为最左边的元素)作为基准值(key),按照该排序码将待排序集合分割成两子序列,左子序列中所有元素均小于基准值,右子序列中所有元素均大于基准值,然后最左右子序列重复该过程,直到所有元素都排列在相应位置上为止。
接下来介绍三种最基本的快速排序版本、非递归版本以及两种对快速排序的优化。
2.快速排序hoare版本
2.1基本思想
选择最左边的元素作为key,用一个left指针指向最左边,用一个right指针指向最右边。right从最右边开始往左边走,找到比key小的元素保持不动,left从最左边开始往右边走,找到比key大的元素保持不动,然后交换left和right指向的元素,再重复上述过程,直到left和right相遇,将相遇处(相遇处的值一定小于key)的值和key交换,这样就可以将小于key的值放到左边,大于key的值放到右边,然后左右子序列重复该过程,直到所以元素都排列在相应位置上为止。
2.2解释相遇处的值为何一定小于key
left和right相遇只有两种情况:(1)left遇上right。(2)right遇上left。
情况1:left遇上right
如果是该情况,表面right是保持不动的,就说明right现在找到的这个元素是小于key的,然后当left遇到right时,则是将right指向的这个元素和key交换。
情况2:right遇上left
如果是right遇上left,是right在走动,left已经在上一轮完成了交换,现在的left指向的元素,是上一轮right找到的小于key的元素,当right遇上left时,则是将right指向的这个小于key的元素和key交换。
注:如果确定左边的值为key,一定要从右边先开始找,不然就会出错。
2.3hoare版本快速排序的实现
void QuickSort1(int* a, int left, int right)
{if (left >= right){return;}//单趟int begin = left; int end = right;int keyi = left;while (begin < end){while (begin < end && a[end] >= a[keyi]) //=防止找到与key相同的值进入死循环{end--;}while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[keyi], &a[end]);keyi = end;//[left, keyi - 1] keyi [keyi + 1, right]QuickSort1(a, left, keyi - 1);QuickSort1(a, keyi + 1, right);
}
3.快速排序挖坑法
3.1基本思想
选择最左边的元素作为key,用一个临时变量tmp将key存储起来,用一个left指针指向最左边,用一个right指针指向最右边。right从右往左走找到小于key的值将它放到left处,然后left从左往右走找到大于key的值将它放到right处。重复上述过程,直到left和right相遇,将tmp中保存的key值放到相遇处。然后左右子序列重复上述过程,直到全部元素排好序为止。
该方法就很自然的在左边挖坑,从右边开始走,不用考虑选择key值从哪边开始走的问题。
3.2挖坑法快速排序的实现
void QuickSort2(int* a, int left, int right)
{if (left >= right){return;}int keyi = left;int tmp = a[keyi];int begin = left;int end = right;while (begin < end){if (begin < end && a[end] >= tmp){end--;}a[begin] = a[end];if (begin < end && a[begin] <= tmp){begin++;}a[end] = a[begin];}a[begin] = tmp;keyi = begin;QuickSort2(a, left, keyi - 1);QuickSort2(a, keyi + 1, right);
}
4. 快速排序前后指针版本
4.1基本思想
4.2快速排序前后指针版本实现
void QuickSort3(int* a, int left, int right)
{if (left >= right){return;}//cur指针找小,找到小于key的,++prev,然后交换int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur) //判断条件的后半部分是防止自身进行交换{Swap(&a[prev], &a[cur]);}cur++; //交换完cur++,a[cur] >= a[keyi] cur也要++,故写在外面合成一句}Swap(&a[prev], &a[keyi]);keyi = prev;QuickSort3(a, left, keyi - 1);QuickSort3(a, keyi + 1, right);
}
5.快速排序非递归版本
5.1基本思想
为什么要实现快速排序的非递归版本,是因为有时可能递归深度太深,会造成栈溢出的风险,用非递归的方式可以有效的避免该风险。在这里我们用栈的方式来实现快速排序的非递归版本。
对于递归版本来说,如何能够确定递归子序列的范围,是用子序列的left指针和right指针来确定的,所以对于非递归版本,只要我们能确定子序列的left和right就能确定需要进行递归的子序列范围。所以我们用栈来存储子序列的left和right指针。
首先,将原数组中left和right存入栈中,然后取出,再依次将右子序列的right,left和左子序列的right和left存入栈中,重复上述操作,对每个子序列进行排序,当栈为空时,结束排序,则此时的数组已被排好序了。
该方法中使用到栈的接口可以参考C语言实现栈。
5.2快速排序非递归版本实现
因为非递归版本内部实现的逻辑和递归版本是一样的,不同的只是用栈来存储区间,所以在这我将内部的逻辑写成一个子函数的形式。
该代码是hoare版本的子函数形式,返回值为上一次单趟之后的keyi。
int PartSort1(int* a, int left, int right)
{int keyi = left;int begin = left;int end = right;while (begin < end){//右边找小while (begin < end && a[end] >= a[keyi]) //加等于方式找到与key相同的数进入死循环{end--;}//左边找大while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[end], &a[keyi]);return begin;
}
void QuickSortNonR(int* a, int left, int right)
{ST st;STInit(&st);STPush(&st, right);STPush(&st, left);while (!(STEmpty(&st))){int begin = STTop(&st);STPop(&st);int end = STTop(&st);STPop(&st);int keyi = PartSort1(a, begin, end);if (keyi + 1 < end) //区间里的值大于1个{STPush(&st, end);STPush(&st, keyi + 1);}if (begin < keyi - 1){STPush(&st, keyi - 1);STPush(&st, begin);}}STDestroy(&st);
}
6.快速排序的优化
6.1三数取中
当key值每次都为数组中的最大值或者最小值的话,则要递归n次,快速排数的时间复杂度就会退化为O(N^2)。为了避免取到的key为最大值或者最小值,对取key进行了一个优化,取数组中left,right以及中间mid指向的元素中,三个元素大小为中间的那个元素,与left交换。
6.1.2三数取中代码实现
//三数取中
int GetMidi(int* a, int left, int right)
{int midi = (left + right) / 2;if (a[midi] > a[left]){if (a[midi] < a[right]){return midi;}else{if (a[left] > a[right]){return left;}else{return right;}}}else{if (a[midi] > a[right]){return midi;}else{if (a[right] < a[left]){return right;}else{return left;}}}
}
6.2小区间优化
对于快速排序的递归来说,当在递归到最后一层时,递归的次数是整个递归的一般,递归创建栈帧和销毁栈帧也会有一定的消耗,并且在元素少的时候,时间复杂度为O(NlogN)的快速排序算法和时间复杂度为O(N^2)的插入排序的消耗差不多,所以在小区间的时候,我们选择用插入排序来代替快速排序,以此来减少递归栈帧的创建和销毁,提高程序性能。
if ((right - left + 1) < 20){InsertSort(a + left, right - left + 1);}
上述代码表示,区间元素的个数小于20个时,采用插入排序进行排序。
6.3优化后的代码
首先,我先把上述介绍的三种快速排序的版本写成子程序的版本:
// 快速排序hoare版本
int PartSort1(int* a, int left, int right)
{//三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int begin = left;int end = right;while (begin < end){//右边找小while (begin < end && a[end] >= a[keyi]) //加等于方式找到与key相同的数进入死循环{end--;}//左边找大while (begin < end && a[begin] <= a[keyi]){begin++;}Swap(&a[begin], &a[end]);}Swap(&a[end], &a[keyi]);return begin;
}
// 快速排序挖坑法
int PartSort2(int* a, int left, int right)
{//三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);int keyi = left;int tmp = a[keyi];int begin = left;int end = right;while (begin < end){if (begin < end && a[end] >= tmp){end--;}a[begin] = a[end];if (begin < end && a[begin] <= tmp){begin++;}a[end] = a[begin];}a[begin] = tmp;return begin;
}
// 快速排序前后指针法
int PartSort3(int* a, int left, int right)
{//三数取中int midi = GetMidi(a, left, right);Swap(&a[left], &a[midi]);//cur指针找小,找到小于key的,++prev,然后交换int keyi = left;int prev = left;int cur = prev + 1;while (cur <= right){if (a[cur] < a[keyi] && ++prev != cur) //判断条件的后半部分是防止自身进行交换{Swap(&a[prev], &a[cur]);}++cur; //交换完cur++,a[cur] >= a[keyi] cur也要++,故写在外面合成一句}Swap(&a[prev], &a[keyi]);return prev;
}
然后写一个快速排序的程序来调用上述三个版本并加上优化:
void QuickSort(int* a, int left, int right)
{if (left >= right) //一个值的区间和不存在的区间都是结束条件{return;}//小区间优化if ((right - left + 1) < 20){InsertSort(a + left, right - left + 1);}else{int keyi = PartSort1(a, left, right);QuickSort(a, left, keyi - 1);QuickSort(a, keyi + 1, right);}
}
如果要修改调用的子程序,将PartSort1修改为PartSort2或者PartSort3即可。
优化后的性能比较: