脚本宝典收集整理的这篇文章主要介绍了快速排序,脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
快排是对冒泡的改进,采用分治策略 时间复杂度O(n log n),最好情况O(n log n),最坏情况退化为O(n2),空间复杂度O(log n)
// 主函数,参数分别为:待排整型数组、数组长度、需要排序的序列起始和结束索引
void QuickSort(int data[],int length,int start,int end){
// 非法参数检查
// 进行第一次划分初始化“基准”的索引值
// 对左右两个子序列递归地进行划分,同样要检查非法参数(作为结束条件)
}
// 划分子函数,返回值为进行一次划分后“基准”的索引值(整型)
int Paritition(int data[],int length,int start,int end){
// 非法参数检查
// 初始化指定一个“基准”
// 对序列进行划分,比“基准”大的放其右边,小的放其左边
return pivot;
}
#include<algorithm>
#include<time.h>
#include<stdlib.h>
using namespace std;
int RandomInRange(int start,int end){
srand(time(NULL));
return rand() % (end-start+1)+start;
}
int Paritition(int data[],int length,int start,int end){
if(data == nullptr || length<=0 || start<0 || end>=length){
throw new exception("Invalid Parameters");
}
int index = RandomInRange(start,end);
swap(data[index],data[end]);// 交换后end指向的就相当于是基准的值
int small = start - 1;
for(index = start;index<end;++index){
if(data[index]<data[end]){
++small;
if(small!=index){
// 条件判断可写可不写,直接换就行
// 只是当两个指针相等时,下面的交换换了跟没换没区别
swap(data[small],data[index]);
}
}
}
++small;
swap(data[small],data[end]);
return small;
}
void QuickSort(int data[],int length,int start,int end){
if(start == end) return;
int index = Paritition(data,length,start,end);
if(index>start){
QuickSort(data,length,start,index-1);
}
if(index<end){
QuickSort(data,length,index+1,end);
}
}
int main() {
int test[9] = { 5,2,8,3,6,4,9,7,1 };
QuickSort(test, 9, 0, 8);
for (int a : test) {
cout << a << " ";
}
}
for(index = start;index<end;++index){
if(data[index]<data[end]){
++small;
if(small!=index){
swap(data[small],data[index]);
}}}// 这诡异的括号是为了省篇幅
index指针遍历整个数组,如果遇到比最后一个元素(基准)小的元素,small+1指向第一个比“基准”大的元素(两个指针指向同一元素例外,相当于初始化指向第一个(也是最后一个)比基准小的值),然后两个指针指向的元素值互换。 这样small指针就更新为指向了了最新(也是最后)一个比“基准”小的元素,原本第一个比“基准”大的元素位置则被换到了(比“基准”大的子数列的末尾) 如果遇到比最后一个元素(基准)大的元素,跳过循环,small不变,index指向下一个,这样比“基准”大的元素就夹在两个指针之间了
++small;
swap(data[small],data[end]);
当遍历结束后,small仍然指向前端比“基准”小的子序列的最后一个,++small则指向了第一个比“基准”大的元素 交换则small的位置不变,指向的值变为“基准”的值。 因为被换到末尾的值仍然比“基准”大,那么现在的数组就是划分完成的样子:small指向的基准左边都比基准小,右边都比基准大
以上是脚本宝典为你收集整理的快速排序全部内容,希望文章能够帮你解决快速排序所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。