文章目錄

• • 1.只申請一次內(nèi)存，避免多次遞歸調(diào)用時反復(fù)的申請和釋放內(nèi)存，提高程序運(yùn)行效率
  • 2.不申請內(nèi)存，在原數(shù)組上直接排序
  • 優(yōu)化比較總結(jié)

對鏈接中快速排序進(jìn)行代碼優(yōu)化

https://blog.csdn.net/qq_21201267/article/details/80993672#t6

1.只申請一次內(nèi)存，避免多次遞歸調(diào)用時反復(fù)的申請和釋放內(nèi)存，提高程序運(yùn)行效率

/** 6-1-opti1.快速排序(best version)(三數(shù)取中基準(zhǔn)+希爾排序+基準(zhǔn)群)(opti1,只申請一次內(nèi)存)* 對數(shù)組找出一個中間大小的合適哨兵，把小于哨兵的放左邊，大于哨兵的放右邊，中間是等于哨兵的* 分別對左右遞歸調(diào)用快排*/void partion1_opti1(int *arr, size_t left, size_t right, size_t &lessPnum, size_t &largePnum, int *temp)//數(shù)據(jù)分段 {selectmedianofthree1(arr,left,right); //找出中間大小的哨兵，讓分段盡量均勻，提高效率int pval = arr[left]; //中間大小的數(shù)賦值給哨兵int tempLindex=0, tempRindex = right-left; //臨時數(shù)組的首末位下標(biāo)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++]; //把分好段的數(shù)組寫回原數(shù)組{[小于哨兵的],[等于哨兵的],[大于哨兵的]}} } void qsort1_opti1(int *arr, size_t left, size_t right, int deep, int *temp) {if(left >= right){return;}else if(right-left == 1)//只有兩個數(shù)直接比較交換（也可以設(shè)置長度小于X（比如10），調(diào)用其他排序，如歸并，減少不必要的調(diào)用快排）{if(arr[left]>arr[right]){swap(arr[left], arr[right]);}}else if(right-left > 1 && right-left < 20) //數(shù)組長度較小時，調(diào)用希爾排序，減少調(diào)用快排{size_t len = right - left + 1;shellsort(len, &arr[left]); //數(shù)組首地址為&arr[left]}else{size_t lessPnum = 0, largePnum=0;partion1_opti1(arr,left,right,lessPnum,largePnum,temp); //數(shù)據(jù)分段，{[小于哨兵],[等于哨兵],[大于哨兵]}size_t pl_index = left + lessPnum; //首位哨兵的下標(biāo)size_t pr_index = right - largePnum; //末位哨兵的下標(biāo)if(pr_index == right && pl_index != left) //哨兵群位于數(shù)組最右邊，且左邊還有數(shù)據(jù){qsort1_opti1(arr,left,pl_index-1,deep,temp); //只對左邊非哨兵數(shù)據(jù)快排}else if(pl_index == left && pr_index != right) //哨兵群位于數(shù)組最左邊，且右邊還有數(shù)據(jù){qsort1_opti1(arr,pr_index+1,right,deep,temp); //只對右邊非哨兵數(shù)據(jù)快排}else if(pl_index == left && pr_index == right) //全部是哨兵，兩側(cè)無數(shù)據(jù)，退出{return;}else //兩側(cè)都有非哨兵數(shù)據(jù)，對兩側(cè)調(diào)用快排{qsort1_opti1(arr,left,pl_index-1,deep,temp);qsort1_opti1(arr,pr_index+1,right,deep,temp);}} } void quicksort1_opti1(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}size_t left = 0, right = dsize-1;int deep = 0; //可以打印顯示出調(diào)用的層數(shù)int *temp = new int [dsize]; //一次性開辟堆空間存放臨時數(shù)組qsort1_opti1(arr,left,right,deep,temp);delete [] temp; //釋放臨時數(shù)組temp = NULL; //指針置空 }

運(yùn)行比較： 優(yōu)化1效率提升

2.不申請內(nèi)存，在原數(shù)組上直接排序

/** 6-1-opti2.快速排序(best version)(三數(shù)取中基準(zhǔn)+希爾排序+基準(zhǔn)群)(不申請內(nèi)存)* 對數(shù)組找出一個中間大小的合適哨兵，把小于哨兵的放左邊，大于哨兵的放右邊，中間是等于哨兵的* 分別對左右遞歸調(diào)用快排*/ void partion1_opti2(int *arr, size_t left, size_t right, size_t &pl_index, size_t &pr_index)//數(shù)據(jù)分段 {selectmedianofthree1(arr,left,right); //找出中間大小的哨兵，讓分段盡量均勻，提高效率int pval = arr[left]; //中間大小的數(shù)賦值給哨兵size_t i = left, j = right;while(i < j){while(i < j && pval <= arr[j]) //把<=改成<,則哨兵群都在左邊,下面相應(yīng)代碼可減少--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; //左右跟哨兵相等的元素個數(shù)pl_index = pindex;//記得初始化！！！之前沒有寫，假如進(jìn)不去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 = pindex+1; 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)//只有兩個數(shù)直接比較交換（也可以設(shè)置長度小于X（比如10），調(diào)用其他排序，如歸并，減少不必要的調(diào)用快排）{if(arr[left]>arr[right]){swap(arr[left], arr[right]);}}else if(right-left > 1 && right-left < 20) //數(shù)組長度較小時，調(diào)用希爾排序，減少調(diào)用快排{size_t len = right - left + 1;shellsort(len, &arr[left]); //數(shù)組首地址為&arr[left]}else{size_t pl_index; //首位哨兵的下標(biāo)size_t pr_index; //末位哨兵的下標(biāo)partion1_opti2(arr,left,right,pl_index,pr_index); //數(shù)據(jù)分段{[小于哨兵][等于哨兵][大于哨兵]}if(pr_index == right && pl_index != left) //哨兵群位于數(shù)組最右邊，且左邊還有數(shù)據(jù){qsort1_opti2(arr,left,pl_index-1,deep); //只對左邊非哨兵數(shù)據(jù)快排}else if(pl_index == left && pr_index != right) //哨兵群位于數(shù)組最左邊，且右邊還有數(shù)據(jù){qsort1_opti2(arr,pr_index+1,right,deep); //只對右邊非哨兵數(shù)據(jù)快排}else if(pl_index == left && pr_index == right) //全部是哨兵，兩側(cè)無數(shù)據(jù)，退出{return;}else //兩側(cè)都有非哨兵數(shù)據(jù)，對兩側(cè)調(diào)用快排{qsort1_opti2(arr,left,pl_index-1,deep);qsort1_opti2(arr,pr_index+1,right,deep);}} } void quicksort1_opti2(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}size_t left = 0, right = dsize-1;int deep = 0; //可以打印顯示出調(diào)用的層數(shù)qsort1_opti2(arr,left,right,deep); }

運(yùn)行效率：

優(yōu)化比較總結(jié)

以下數(shù)據(jù)為5次運(yùn)行的平均數(shù)據(jù)

windows下效率提升：optimization1 -----6%----- optimization2 -----14%-----
linux 下效率提升：optimization1 -----2%----- optimization2 -----20%-----

測試程序運(yùn)行時間shell腳本
https://blog.csdn.net/qq_21201267/article/details/81840299

最后特別感謝阿福同學(xué)的幫忙調(diào)試找BUG！！！

總結(jié)

以上是生活随笔為你收集整理的快速排序quicksort算法细节优化（一次申请内存/无额外内存排序）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。