网站模版怎么做的,网站开发服务费,青岛设计优化公司,公司网络维护服务1.基本想想 快速排序使用分治的思想 通过一趟排序将待排序列分割成两部分#xff0c;其中一部分所有元素均比基准大#xff0c;另一部分均比基准小 分别对这两部分元素继续进行排序#xff0c;以达到整个序列有序
2.快排的步骤
1.选择基准 在待排序列中#xff0c;按…1.基本想想 快速排序使用分治的思想 通过一趟排序将待排序列分割成两部分其中一部分所有元素均比基准大另一部分均比基准小 分别对这两部分元素继续进行排序以达到整个序列有序
2.快排的步骤
1.选择基准 在待排序列中按照某种方式挑出一个元素作为 “基准”pivot2.分割操作 在基准左边的元素都比该基准小在基准右边的元素都比基准大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-left1]; //开辟堆空间存放临时数组int tempLindex0, tempRindex right-left; //临时数组的首末位下标for(int i left1; 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, j0; i right; i){arr[i] temp[j]; //把分好段的数组写回原数组{ [小于哨兵的], [等于哨兵的], [大于哨兵的] }}delete [] temp; //释放临时数组temp NULL; //指针置空
}
5.效率比较
同样的环境下运行时间s
参考文献
https://blog.csdn.net/hacker00011000/article/details/52176100
