1500字范文,内容丰富有趣,写作好帮手!
1500字范文 > 快速排序quicksort算法优化

快速排序quicksort算法优化

时间:2018-08-11 15:12:44

相关推荐

快速排序quicksort算法优化

1.基本想想

快速排序使用分治的思想

通过一趟排序将待排序列分割成两部分,其中一部分所有元素均比基准大,另一部分均比基准小

分别对这两部分元素继续进行排序,以达到整个序列有序

2.快排的步骤

1.选择基准

在待排序列中,按照某种方式挑出一个元素,作为 “基准”(pivot)2.分割操作

在基准左边的元素都比该基准小,在基准右边的元素都比基准大3.递归

递归地对两个序列进行快速排序,直到序列为空或者只有一个元素

3.基准的选取

固定位置

取序列的第一个或最后一个元素作为基准

int pval = arr[left];

随机选取基准

取待排序列中任意一个元素作为基准

int pval = arr[rand()%(right-left)+left];

三数取中

对待排序序列中low、mid、high三个位置上数据进行排序,取他们中间的那个数据作为枢轴

void selectmedianofthree(int *arr, size_t left, size_t right) {size_t mid = left + (right - left)/2; //中部数据的下标if(arr[mid]>arr[right]){swap(arr[mid],arr[right]);}if(arr[left]>arr[right]){swap(arr[left],arr[right]);}if(arr[mid]>arr[left]){swap(arr[mid],arr[left]); //把中间大小的数值放到首位,取为基准}}

4.快排算法优化

当待排序序列的长度分割到一定大小后,使用插入排序或者其它排序(数组短的时候,快排分割效率不高)

if(left >= right){return;}else if(right-left > 0 && right-left < 20) //数组长度较小时,调用希尔排序,减少调用快排{size_t len = right - left + 1;shellsort(len, &arr[left]); //数组首地址为&arr[left]}else{qsort(****);}

在一次分割结束后,可以把与基准p相等的元素聚在一起,继续下次分割时,不用再对与基准p相等元素分割

void partion(int *arr, size_t left, size_t right, size_t &lessPnum, size_t &largePnum)//数据分段{selectmedianofthree(arr,left,right); //找出中间大小的哨兵,让分段尽量均匀,提高效率int pval = arr[left]; //中间大小的数赋值给哨兵int *temp = new int [right-left+1]; //开辟堆空间存放临时数组int tempLindex=0, tempRindex = right-left; //临时数组的首末位下标for(int i = left+1; i <= right; ++i){if(pval > arr[i]) //比哨兵小的放在左边,从左边首位往中间写入,记录下比哨兵小的有多少个{temp[tempLindex++] = arr[i];++lessPnum;}if(pval < arr[i]) 比哨兵大的放在右边,从右边末位中间写入,记录下比哨兵大的有多少个{temp[tempRindex--] = arr[i];largePnum++;}}for( ; tempLindex <= tempRindex; ++tempLindex)//中间还未被写入的位置,写入哨兵(哨兵可能是多个相同的值){temp[tempLindex] = pval;}for(int i = left, j=0; i <= right; ++i){arr[i] = temp[j++]; //把分好段的数组写回原数组{ [小于哨兵的], [等于哨兵的], [大于哨兵的] }}delete [] temp; //释放临时数组temp = NULL; //指针置空}

5.效率比较

同样的环境下,运行时间(s)

参考文献

/hacker00011000/article/details/52176100

本内容不代表本网观点和政治立场,如有侵犯你的权益请联系我们处理。
网友评论
网友评论仅供其表达个人看法,并不表明网站立场。