怎样与其它网站做友情链接,qinmei wordpress,深圳国内网站设计公司,可以发外链的论坛有哪些文章目录1.只申请一次内存#xff0c;避免多次递归调用时反复的申请和释放内存#xff0c;提高程序运行效率2.不申请内存#xff0c;在原数组上直接排序优化比较总结对链接中快速排序进行代码优化
https://blog.csdn.net/qq_21201267/article/details/80993672#t6
1.只申请…
文章目录1.只申请一次内存避免多次递归调用时反复的申请和释放内存提高程序运行效率2.不申请内存在原数组上直接排序优化比较总结对链接中快速排序进行代码优化
https://blog.csdn.net/qq_21201267/article/details/80993672#t6
1.只申请一次内存避免多次递归调用时反复的申请和释放内存提高程序运行效率
/** 6-1-opti1.快速排序(best version)(三数取中基准希尔排序基准群)(opti1,只申请一次内存)* 对数组找出一个中间大小的合适哨兵把小于哨兵的放左边大于哨兵的放右边中间是等于哨兵的* 分别对左右递归调用快排*/void partion1_opti1(int *arr, size_t left, size_t right, size_t lessPnum, size_t largePnum, int *temp)//数据分段
{selectmedianofthree1(arr,left,right); //找出中间大小的哨兵让分段尽量均匀提高效率int pval arr[left]; //中间大小的数赋值给哨兵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]; //把分好段的数组写回原数组{[小于哨兵的],[等于哨兵的],[大于哨兵的]}}
}
void qsort1_opti1(int *arr, size_t left, size_t right, int deep, int *temp)
{if(left right){return;}else if(right-left 1)//只有两个数直接比较交换也可以设置长度小于X比如10调用其他排序如归并减少不必要的调用快排{if(arr[left]arr[right]){swap(arr[left], arr[right]);}}else if(right-left 1 right-left 20) //数组长度较小时调用希尔排序减少调用快排{size_t len right - left 1;shellsort(len, arr[left]); //数组首地址为arr[left]}else{size_t lessPnum 0, largePnum0;partion1_opti1(arr,left,right,lessPnum,largePnum,temp); //数据分段{[小于哨兵],[等于哨兵],[大于哨兵]}size_t pl_index left lessPnum; //首位哨兵的下标size_t pr_index right - largePnum; //末位哨兵的下标if(pr_index right pl_index ! left) //哨兵群位于数组最右边且左边还有数据{qsort1_opti1(arr,left,pl_index-1,deep,temp); //只对左边非哨兵数据快排}else if(pl_index left pr_index ! right) //哨兵群位于数组最左边且右边还有数据{qsort1_opti1(arr,pr_index1,right,deep,temp); //只对右边非哨兵数据快排}else if(pl_index left pr_index right) //全部是哨兵两侧无数据退出{return;}else //两侧都有非哨兵数据对两侧调用快排{qsort1_opti1(arr,left,pl_index-1,deep,temp);qsort1_opti1(arr,pr_index1,right,deep,temp);}}
}
void quicksort1_opti1(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}size_t left 0, right dsize-1;int deep 0; //可以打印显示出调用的层数int *temp new int [dsize]; //一次性开辟堆空间存放临时数组qsort1_opti1(arr,left,right,deep,temp);delete [] temp; //释放临时数组temp NULL; //指针置空
}运行比较 优化1效率提升
2.不申请内存在原数组上直接排序
/** 6-1-opti2.快速排序(best version)(三数取中基准希尔排序基准群)(不申请内存)* 对数组找出一个中间大小的合适哨兵把小于哨兵的放左边大于哨兵的放右边中间是等于哨兵的* 分别对左右递归调用快排*/
void partion1_opti2(int *arr, size_t left, size_t right, size_t pl_index, size_t pr_index)//数据分段
{selectmedianofthree1(arr,left,right); //找出中间大小的哨兵让分段尽量均匀提高效率int pval arr[left]; //中间大小的数赋值给哨兵size_t i left, j right;while(i j){while(i j pval arr[j]) //把改成,则哨兵群都在左边,下面相应代码可减少--j;swap(arr[i],arr[j]);while(i j pval arr[i])// 号至少有一个才行一个等号忽略下面半边集合哨兵代码是最高效的i;swap(arr[i],arr[j]);}size_t pindex i;size_t leftpnum 0, rightpnum 0; //左右跟哨兵相等的元素个数pl_index pindex;//记得初始化之前没有写假如进不去for没有初始化就越界了pr_index pindex;if(pindex ! 0)//!!!如果pindex 0下面 i pindex - 1 越界{for(i pindex-1; i left; --i)//左边哨兵群向中间集合哨兵都在右边即可忽略以下代码{if(arr[i] pval){leftpnum;pl_index pindex - leftpnum;swap(arr[i],arr[pl_index]);}if(i left) //size_t 做减法要小心越界break;}}for(i pindex1; i right; i)//右边哨兵群向中间集合,哨兵都在左边边即可忽略以下代码{if(arr[i] pval){rightpnum;pr_index pindex rightpnum;swap(arr[i],arr[pr_index]);}}
}
void qsort1_opti2(int *arr, size_t left, size_t right, int deep)
{if(left right){return;}else if(right-left 1)//只有两个数直接比较交换也可以设置长度小于X比如10调用其他排序如归并减少不必要的调用快排{if(arr[left]arr[right]){swap(arr[left], arr[right]);}}else if(right-left 1 right-left 20) //数组长度较小时调用希尔排序减少调用快排{size_t len right - left 1;shellsort(len, arr[left]); //数组首地址为arr[left]}else{size_t pl_index; //首位哨兵的下标size_t pr_index; //末位哨兵的下标partion1_opti2(arr,left,right,pl_index,pr_index); //数据分段{[小于哨兵][等于哨兵][大于哨兵]}if(pr_index right pl_index ! left) //哨兵群位于数组最右边且左边还有数据{qsort1_opti2(arr,left,pl_index-1,deep); //只对左边非哨兵数据快排}else if(pl_index left pr_index ! right) //哨兵群位于数组最左边且右边还有数据{qsort1_opti2(arr,pr_index1,right,deep); //只对右边非哨兵数据快排}else if(pl_index left pr_index right) //全部是哨兵两侧无数据退出{return;}else //两侧都有非哨兵数据对两侧调用快排{qsort1_opti2(arr,left,pl_index-1,deep);qsort1_opti2(arr,pr_index1,right,deep);}}
}
void quicksort1_opti2(size_t dsize, int *arr)
{if(dsize 1) //预防特殊情况下后面代码失效{return;}size_t left 0, right dsize-1;int deep 0; //可以打印显示出调用的层数qsort1_opti2(arr,left,right,deep);
}运行效率
优化比较总结
以下数据为5次运行的平均数据 windows下效率提升optimization1 -----6%----- optimization2 -----14%----- linux 下效率提升optimization1 -----2%----- optimization2 -----20%-----
测试程序运行时间shell脚本 https://blog.csdn.net/qq_21201267/article/details/81840299
最后特别感谢阿福同学的帮忙调试找BUG
