文章目錄

• • 1.插入排序
  • 2.冒泡排序
  • 3.選擇排序
  • 4.希爾排序
  • 5.歸并排序
  • 6.快速排序
  • 6.1.快速排序（改進(jìn)）
  • 7.堆排序
  • 8.計(jì)數(shù)排序
  • 9.桶排序
  • 9.1.桶排序（改進(jìn)）
  • 10.基數(shù)排序

題目：LeetCode 912. 排序數(shù)組（10種排序）
下面博文，為早期學(xué)習(xí)寫的，很不簡(jiǎn)潔，請(qǐng)參考上面題目的版本。

1.插入排序

/** 1.插入排序* 每次在末尾插入一個(gè)數(shù)字，依次向前比較，類似與抓撲克牌(插入排序，每次左邊的子序列都是有序的)*/ void insertsort(size_t dsize, int *arr) //dsize是數(shù)組arr的長度 {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}for (size_t i = 0; i != dsize; ++i) {for (size_t j = i; j > 0 && arr[j-1] > arr[j]; --j)//每次的子列都是有序的，判斷條件可寫在for(內(nèi))，否則不可（這么做減少運(yùn)行次數(shù)）//每次和有序數(shù)組最后一個(gè)比較，向前搜索，直到找到位置停止{swap(arr[j-1], arr[j]);}} }/*時(shí)間復(fù)雜度分析最好情況：原數(shù)列有序，每次放在最后就好了，復(fù)雜度為n最壞情況：原數(shù)列倒序的，每次都要挪到最前面，1+2+...+n-1=n(n-1)/2*/

2.冒泡排序

/**2.冒泡排序，數(shù)從前向后冒泡比較，冒泡過程中，數(shù)列無序狀態(tài)*/ void bsort(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}bool arrisok = false;for(size_t i = 0; i != dsize; ++i){ arrisok = true;for(size_t j=1;j <= dsize-1-i;++j) //后面的數(shù)都排好了，所以j<=dsize-1-i,不減i,也可，但時(shí)間長{ if(arr[j-1]> arr[j]) //比較的過程中是無序的，判斷條件寫在for{}里//寫在for()里會(huì)出現(xiàn)局部條件不滿足就退出for循環(huán)了，以至于還未排序完{swap(arr[j-1],arr[j]);arrisok = false; //如果交換過，則數(shù)組未完成排序}}if(arrisok == true){return; //經(jīng)過一輪冒泡后,數(shù)據(jù)沒有發(fā)生交換則數(shù)據(jù)為有序，可退出函數(shù)，可減少12%時(shí)間（用自己的程序）}} }/*時(shí)間復(fù)雜度分析最好情況：原數(shù)列有序，復(fù)雜度為n最壞情況：原數(shù)列倒序的，每次都要從前挪到后面，n-1+n-2+...+1=n(n-1)/2*/

3.選擇排序

/**3.選擇排序,每次找出數(shù)值最小的下標(biāo)，交換未排序區(qū)域第一個(gè)與最小的(與冒泡的區(qū)別，只交換一次)*/ void selecsort(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}size_t mindex=0;for(size_t i =0; i!= dsize-1; ++i){ mindex= i ;for(size_t j=i+1;j!=dsize;++j){ if(arr[j]< arr[mindex]) //子列為無序的，判斷條件寫在for{}里{ mindex = j; //記錄下最小數(shù)的下標(biāo)}}swap(arr[i],arr[mindex]);} }/*時(shí)間復(fù)雜度分析最好情況：（與最壞一樣）最壞情況：每次都要從前到后比較，n-1+n-2+...+1=n(n-1)/2*/

4.希爾排序

/** 4.希爾排序，分組插入排序，相隔gap個(gè)數(shù)的都為一組，從第gap個(gè)數(shù)開始*/ void shellsort(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}size_t gap = 1;size_t j=0;for(gap=dsize/2;gap> 0;gap /= 2){ for(size_t i = gap;i < dsize;++i){ for(j=i;int(j-gap)>=0 && arr[j-gap]> arr[j];j -= gap) //int()轉(zhuǎn)換類型，避免溢出，相當(dāng)于分組的插入排序{swap(arr[j-gap],arr[j]);}}} }/*時(shí)間復(fù)雜度分析 [參考](https://blog.csdn.net/ginnosx/article/details/12263619)最好情況：最壞情況：*/

5.歸并排序

/**5.歸并排序，自頂向下，遞歸*/ void merge(int *arr,size_t left,size_t mid,size_t right) {int len = right - left + 1;int *temp = new int [len]; //數(shù)組較長時(shí)請(qǐng)用new，不然棧空間容易溢出size_t index = 0;size_t i = left, j = mid + 1;while(i <= mid && j <= right){temp[index++] = arr[i]<= arr[j]? arr[i++]: arr[j++]; //對(duì)兩邊的數(shù)組從小到大放入臨時(shí)空間}while(i <= mid) //比較完后，左半邊有沒放進(jìn)去的，直接寫入{temp[index++]= arr[i++];}while(j <= right) //比較完后，右半邊有沒有放進(jìn)去的，直接寫入{temp[index++]= arr[j++];}for(int k = 0;k< len;++k){arr[left++ ]= temp[k]; //把有序的臨時(shí)數(shù)組寫入原來數(shù)組的起始位置}delete [] temp; //釋放空間temp = NULL; //指針置空 } void divide(int *arr,size_t left,size_t right) {if(left == right){ return;}size_t mid = (left+right)/2; //找出區(qū)間中部的數(shù)，將數(shù)組分段divide(arr,left,mid); //遞歸調(diào)用，對(duì)左邊繼續(xù)分段；divide(arr,mid+1,right); //遞歸調(diào)用，對(duì)右邊繼續(xù)分段；merge(arr,left,mid,right); //對(duì)左右兩半進(jìn)行排序合并成一小段有序的數(shù)組 } void mergesort(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}size_t left = 0, right = dsize-1;divide(arr,left,right); }

6.快速排序

/*1. 6.快速排序2. 對(duì)數(shù)組找出一個(gè)中間大小的合適哨兵，把小于哨兵的放左邊，大于哨兵的放右邊，中間是等于哨兵的3. 分別對(duì)左右遞歸調(diào)用快排*/ size_t parr [2]; //全局變量，全局變量不好，長期占用內(nèi)存，每個(gè)函數(shù)都可訪問，容易被修改，函數(shù)間相互干擾 void selectmedianofthree(int *arr, size_t left, size_t right) //找出中間大小的數(shù)做哨兵 {size_t mid = left + (right - left)/2; //中部數(shù)據(jù)的下標(biāo)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]); //把中間大小的數(shù)值放到首位} } void partion(int *arr, size_t left, size_t right) //數(shù)據(jù)分段 {selectmedianofthree(arr,left,right); //找出中間大小的哨兵，讓分段盡量均勻，提高效率size_t lessPnum = 0, largePnum=0;int pval = arr[left]; //中間大小的數(shù)賦值給哨兵int *temp = new int [right-left+1]; //開辟堆空間存放臨時(shí)數(shù)組int tempLindex=0, tempRindex = right-left; //臨時(shí)數(shù)組的首末位下標(biāo)for(int i = left+1; i <= right; ++i){if(pval > arr[i]) //比哨兵小的放在左邊，從左邊首位往中間寫入，記錄下比哨兵小的有多少個(gè){temp[tempLindex++] = arr[i];++lessPnum;}if(pval < arr[i]) 比哨兵大的放在右邊，從右邊末位中間寫入，記錄下比哨兵大的有多少個(gè){temp[tempRindex--] = arr[i];largePnum++;}}for( ; tempLindex <= tempRindex; ++tempLindex)//中間還未被寫入的位置，寫入哨兵（哨兵可能是多個(gè)相同的值）{temp[tempLindex] = pval;}for(int i = left, j=0; i <= right; ++i){arr[i] = temp[j++]; //把分好段的數(shù)組寫回原數(shù)組{[小于哨兵的],[等于哨兵的],[大于哨兵的]}}delete [] temp; //釋放臨時(shí)數(shù)組temp = NULL; //指針置空parr[0]=lessPnum;parr[1]=largePnum; //可以采用被調(diào)用函數(shù)的參數(shù)引用回傳給主函數(shù) } void qsort(int *arr, size_t left, size_t right, int deep) {if(left >= right){return;}else if(right-left == 1) //只有兩個(gè)數(shù)直接比較交換（也可以設(shè)置長度小于X（比如10），調(diào)用其他排序，如歸并，減少不必要的調(diào)用快排）{if(arr[left]>arr[right]){ swap(arr[left], arr[right]);}}else{partion(arr,left,right); //數(shù)據(jù)分段，{[小于哨兵的],[等于哨兵的],[大于哨兵的]}size_t pl_index = left + parr[0]; //首位哨兵的下標(biāo)size_t pr_index = right - parr[1]; //末位哨兵的下標(biāo)if(pr_index == right && pl_index != left) //哨兵群位于數(shù)組最右邊，且左邊還有數(shù)據(jù){qsort(arr,left,pl_index-1,deep); //只對(duì)左邊非哨兵數(shù)據(jù)快排}else if(pl_index == left && pr_index != right) //哨兵群位于數(shù)組最左邊，且右邊還有數(shù)據(jù){ qsort(arr,pr_index+1,right,deep); //只對(duì)右邊非哨兵數(shù)據(jù)快排}else if(pl_index == left && pr_index == right) //全部是哨兵，兩側(cè)無數(shù)據(jù)，退出{return;}else //兩側(cè)都有非哨兵數(shù)據(jù)，對(duì)兩側(cè)調(diào)用快排{qsort(arr,left,pl_index-1,deep);qsort(arr,pr_index+1,right,deep);}} } void quicksort(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}size_t left = 0, right = dsize-1;int deep = 0; //可以打印顯示出調(diào)用的層數(shù)qsort(arr,left,right,deep); }

6.1.快速排序（改進(jìn)）

/** 6-1.快速排序(改進(jìn)：不使用全局變量傳遞參數(shù))* 對(duì)數(shù)組找出一個(gè)中間大小的合適哨兵，把小于哨兵的放左邊，大于哨兵的放右邊，中間是等于哨兵的* 分別對(duì)左右遞歸調(diào)用快排*/ void selectmedianofthree(int *arr, size_t left, size_t right) //找出中間大小的數(shù)做哨兵 {size_t mid = left + (right - left)/2; //中部數(shù)據(jù)的下標(biāo)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]); //把中間大小的數(shù)值放到首位} } void partion(int *arr, size_t left, size_t right, size_t &lessPnum, size_t &largePnum)//數(shù)據(jù)分段 {selectmedianofthree(arr,left,right); //找出中間大小的哨兵，讓分段盡量均勻，提高效率int pval = arr[left]; //中間大小的數(shù)賦值給哨兵int *temp = new int [right-left+1]; //開辟堆空間存放臨時(shí)數(shù)組int tempLindex=0, tempRindex = right-left; //臨時(shí)數(shù)組的首末位下標(biāo)for(int i = left+1; i <= right; ++i){if(pval > arr[i]) //比哨兵小的放在左邊，從左邊首位往中間寫入，記錄下比哨兵小的有多少個(gè){temp[tempLindex++] = arr[i];++lessPnum;}if(pval < arr[i]) 比哨兵大的放在右邊，從右邊末位中間寫入，記錄下比哨兵大的有多少個(gè){temp[tempRindex--] = arr[i];largePnum++;}}for( ; tempLindex <= tempRindex; ++tempLindex)//中間還未被寫入的位置，寫入哨兵（哨兵可能是多個(gè)相同的值）{temp[tempLindex] = pval;}for(int i = left, j=0; i <= right; ++i){arr[i] = temp[j++]; //把分好段的數(shù)組寫回原數(shù)組{[小于哨兵的],[等于哨兵的],[大于哨兵的]}}delete [] temp; //釋放臨時(shí)數(shù)組temp = NULL; //指針置空 } void qsort(int *arr, size_t left, size_t right, int deep) {if(left >= right){return;}else if(right-left == 1)//只有兩個(gè)數(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ù)組長度較小時(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;partion(arr,left,right,lessPnum,largePnum); //數(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ù){qsort(arr,left,pl_index-1,deep); //只對(duì)左邊非哨兵數(shù)據(jù)快排}else if(pl_index == left && pr_index != right) //哨兵群位于數(shù)組最左邊，且右邊還有數(shù)據(jù){ qsort(arr,pr_index+1,right,deep); //只對(duì)右邊非哨兵數(shù)據(jù)快排}else if(pl_index == left && pr_index == right) //全部是哨兵，兩側(cè)無數(shù)據(jù)，退出{return;}else //兩側(cè)都有非哨兵數(shù)據(jù)，對(duì)兩側(cè)調(diào)用快排{qsort(arr,left,pl_index-1,deep);qsort(arr,pr_index+1,right,deep);}} } void quicksort(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}size_t left = 0, right = dsize-1;int deep = 0; //可以打印顯示出調(diào)用的層數(shù)qsort(arr,left,right,deep); }

7.堆排序

/** 7.堆排序，建堆（升序建大堆，降序建小堆）* 交換堆頂與最后一位無序數(shù)據(jù)* 調(diào)整堆，遞歸，交換調(diào)整*/ void adjust(int *arr, size_t i, size_t dsize) {size_t LowerLeftNode = i*2+1; //下一層左邊的節(jié)點(diǎn)while(LowerLeftNode < dsize){if(LowerLeftNode+1< dsize && arr[LowerLeftNode]< arr[LowerLeftNode+1] ){++LowerLeftNode;}if(arr[i]> arr[LowerLeftNode]) //如果上層節(jié)點(diǎn)大于小面兩個(gè)子節(jié)點(diǎn)，結(jié)束{break;}swap(arr[i], arr[LowerLeftNode]);i = LowerLeftNode; //往下循環(huán)調(diào)整LowerLeftNode = i*2+1;} } void makeheap(size_t dsize, int *arr) {for(size_t i = dsize/2 -1; i >=0;--i) //從后往前，底下第二層（第一個(gè)有子節(jié)點(diǎn)的元素的下標(biāo)）{adjust(arr,i,dsize); //有子節(jié)點(diǎn)，調(diào)整堆（從i節(jié)點(diǎn)往下，末位固定dsize-1）if(i == 0)break;} } void heapsort(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}makeheap(dsize,arr); //建立堆，大堆，上面父節(jié)點(diǎn)比子節(jié)點(diǎn)大size_t i = 0;for(i=dsize-1;i>=0;--i) //從最后一位開始，與堆頂交換，調(diào)整堆，尾部數(shù)據(jù)減1{swap(arr[i],arr[0]); //把最大的arr[0]與隊(duì)尾交換adjust(arr,0,i); //從第0位往下開始調(diào)整，末位不固定，數(shù)組長度i，每次減一if(i == 0) //i = 0，退出，防止--i，size_t溢出break;} }

8.計(jì)數(shù)排序

/**8.計(jì)數(shù)排序，找出數(shù)列中最大最小的數(shù)，并記錄下每一個(gè)元素的個(gè)數(shù)，然后放回*/ void countsort(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}int index = 0;int min, max;min = max = arr[0];for(int i = 1; i<dsize;++i){min=(arr[i] < min)? arr[i] : min;max=(arr[i] > max)? arr[i] : max;}//創(chuàng)建新的數(shù)組存放int k = max -min +1;int *temp = new int [k](); //（）初始化為0for(int i = 0;i< dsize;++i){++temp[arr[i]-min]; //記錄每個(gè)數(shù)的個(gè)數(shù)，存入數(shù)組}for(int i = min; i <= max;++i){for(int j = 0; j < temp[i-min];++j) //存放元素個(gè)數(shù)不為0的，才進(jìn)入循環(huán){arr[index++] = i; //把元素值寫回?cái)?shù)組}}delete [] temp;temp = NULL; }

9.桶排序

/**9.桶排序，將數(shù)據(jù)按規(guī)則分組，對(duì)各小組再分別排序*/ void bucketsort(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}int maxval = arr[0];int minval = arr[0];for(int i = 0; i != dsize; ++i) //遍歷數(shù)組，找出最大最小元素{maxval = maxval > arr[i] ? maxval : arr[i];minval = minval < arr[i] ? minval : arr[i];}if(maxval == minval) //如果最大==最小，數(shù)組不需要排序（排除下面div=0，進(jìn)不了位，div總是為0）{return;}else{int space = 10000; //每個(gè)桶數(shù)元素值的最大差值（區(qū)間大小）int div = ceil((double)(maxval-minval)/space); //桶的個(gè)數(shù)，ceil取進(jìn)位數(shù)(先double強(qiáng)轉(zhuǎn)（float的精度不夠高），避免丟失小數(shù)點(diǎn))//space 太小，桶個(gè)數(shù)太多，會(huì)造成棧空間溢出int numsofeachbucket[div]; //開辟數(shù)組，存放每個(gè)桶內(nèi)的元素個(gè)數(shù)//知識(shí)點(diǎn)：//1.桶的個(gè)數(shù)跟數(shù)據(jù)相關(guān)，space是固定的，但是桶的個(gè)數(shù)會(huì)根據(jù)環(huán)境變化，不能確保程序在其他環(huán)境下正確運(yùn)行//2.div很大時(shí)，int numsofeachbucket[div]，直接撐爆棧空間，需要采用new 開辟堆空間//3.當(dāng)(maxval-minval)是space的整數(shù)倍的時(shí)候，段錯(cuò)誤，訪問越界//第3個(gè)問題改成int div = floor((double)(maxval-minval)/space)+1;即可for(size_t i =0; i != div; ++i){numsofeachbucket[i] = 0; //每個(gè)桶的元素個(gè)數(shù)初始化為0}for(size_t i = 0; i != dsize; ++i){++numsofeachbucket[(arr[i]-minval)/space]; //把元素按大小分到不同的桶，并增加該桶元素個(gè)數(shù)}int **p = new int* [div]; //開辟堆空間，指針數(shù)組，每個(gè)元素（指針）指向每個(gè)桶的0位int **temp = new int* [div]; //臨時(shí)數(shù)組，保存某些指針的初始值，方便delete（delete時(shí)，指針必須位于初始位置）int **temp_1 = new int* [div]; //同上（改進(jìn)啟發(fā)：數(shù)組長度是一定的，申請(qǐng)一次內(nèi)存，知道每個(gè)桶始末位置即可）for(size_t i = 0; i != div; ++i){if(numsofeachbucket[i] != 0) //桶內(nèi)有元素（沒有元素就不要申請(qǐng)空間了，如申請(qǐng)了，指針的地址是不為NULL的，會(huì)出問題）{p[i] = new int [numsofeachbucket[i]]; //指針數(shù)組，每個(gè)元素（指針）指向每個(gè)桶的0位temp[i] = p[i]; //記錄每個(gè)桶申請(qǐng)的空間的初始地址，后面delete temp_1[i]即可刪除開辟的p[i] new出的空間temp_1[i] = p[i]; //記錄初始地址，后面p[i],temp[i]（指針）也要挪動(dòng)}else{p[i] = NULL; //沒有元素的桶，不申請(qǐng)空間，指針初始化為NULLtemp[i] = NULL;temp_1[i] = NULL;}}for(size_t i = 0; i != dsize; ++i){size_t bucketidx = (arr[i]-minval)/space; //遍歷數(shù)組，每個(gè)元素的桶號(hào)*p[bucketidx] = arr[i]; //把每個(gè)元素寫入對(duì)應(yīng)的桶中++p[bucketidx]; //該桶指針后移一位}size_t idx = 0; //之前用了static，下次調(diào)用的時(shí)候idx不會(huì)被賦值 =0 操作//cout << "static idx " << idx << endl;for(size_t i = 0; i != div; ++i){if(numsofeachbucket[i] != 0) //桶非空{if(numsofeachbucket[i]>1) //桶元素個(gè)數(shù)2個(gè)或更多{quicksort(numsofeachbucket[i], temp[i]); //對(duì)動(dòng)態(tài)數(shù)組進(jìn)行快速排序（p[i]挪動(dòng)過了，temp[i]指向數(shù)組首位）}for(size_t j = 0; j != numsofeachbucket[i]; ++j){arr[idx++] = *temp[i]; //對(duì)排序后的數(shù)組（1個(gè)元素不需排序），寫入原數(shù)組++temp[i];//cout << "static idx " << idx << endl;}}}for(size_t i = 0; i != div; ++i){if(numsofeachbucket[i] != 0) //對(duì)申請(qǐng)出來的空間，釋放掉{delete [] temp_1[i]; //上面每個(gè)桶的數(shù)組初始位置指針p[i],temp[i]都動(dòng)過了，所以用此副本初始地址temp_1[i] = NULL; //被釋放的空間的相關(guān)的指針置為空temp[i] = NULL;p[i] = NULL;}}delete [] temp_1; //delete 與 new 配對(duì)出現(xiàn)，釋放數(shù)組，指針置NULLdelete [] temp; //內(nèi)存檢測(cè)工具valgrind http://valgrind.org/delete [] p;temp_1 = NULL;temp = NULL;p = NULL;} }

9.1.桶排序（改進(jìn)）

/**9-1.桶排序，將數(shù)據(jù)按規(guī)則分組，對(duì)各小組再分別排序*（改進(jìn)）*1.數(shù)組長度一定的，只申請(qǐng)一次內(nèi)存，避免內(nèi)存碎片化，提高效率*2.給定桶的個(gè)數(shù)，程序運(yùn)行狀況在不同環(huán)境下可控*/ void bucketsort1(size_t dsize, int *arr) {if(dsize <= 1) //預(yù)防特殊情況下后面代碼失效{return;}int maxval = arr[0];int minval = arr[0];for(int i = 0; i != dsize; ++i) //遍歷數(shù)組，找出最大最小元素{maxval = maxval > arr[i] ? maxval : arr[i];minval = minval < arr[i] ? minval : arr[i];}if(maxval == minval) //如果最大==最小，數(shù)組不需要排序{return;}else{int div = 1000; //桶的個(gè)數(shù)int space = (maxval-minval)/div+1; //每個(gè)桶的數(shù)值跨度，+1放大一點(diǎn)包住int *numsofeachbucket = new int [div](); //開辟數(shù)組，存放每個(gè)桶內(nèi)的元素個(gè)數(shù)，（）初始化為0int *endpositionofeachbucket = new int [div](); for(size_t i = 0; i != dsize; ++i){++numsofeachbucket[(arr[i]-minval)/space]; //把元素按大小分到不同的桶，并增加該桶元素個(gè)數(shù)++endpositionofeachbucket[(arr[i]-minval)/space];}for(int i = 1; i != div; ++i){endpositionofeachbucket[i] += endpositionofeachbucket[i-1]; //每個(gè)桶區(qū)間的最大下標(biāo)+1的值}int *temparr = new int [dsize]; //開辟堆空間，存放臨時(shí)數(shù)組for(size_t i = 0; i != dsize; ++i){temparr[--endpositionofeachbucket[(arr[i]-minval)/space]] = arr[i]; //遍歷數(shù)組，把每個(gè)元素寫入對(duì)應(yīng)的桶中，從每個(gè)桶的后部往前寫//--運(yùn)行完成后endpositionofeachbucket[i]就是該桶的首位}for(size_t i = 0; i != div; ++i){if(numsofeachbucket[i] > 1) //桶元素2個(gè)或以上才排序{quicksort(numsofeachbucket[i], &temparr[endpositionofeachbucket[i]]); //對(duì)每個(gè)桶的數(shù)組進(jìn)行快速排序（元素個(gè)數(shù)，每個(gè)桶數(shù)組首位的地址）} }for(size_t i = 0; i != dsize; ++i){arr[i] = temparr[i]; //對(duì)排序后的數(shù)組，寫入原數(shù)組}delete [] numsofeachbucket; //delete 與 new 配對(duì)出現(xiàn)，釋放數(shù)組，指針置NULLdelete [] endpositionofeachbucket; //內(nèi)存檢測(cè)工具valgrind http://valgrind.org/delete [] temparr;numsofeachbucket = NULL;endpositionofeachbucket = NULL;temparr = NULL;} }

比較優(yōu)化前后的桶排序計(jì)算效率（同樣的環(huán)境下）
優(yōu)化前 運(yùn)行時(shí)間：149s
優(yōu)化后 運(yùn)行時(shí)間：96s （提升35%）堆的申請(qǐng)和釋放次數(shù)也降低了

10.基數(shù)排序

/**10.基數(shù)排序*/ void radix_countsort(size_t dsize, int *arr, int exp) {int numofeachbucket[10] = {0}; //十個(gè)數(shù)位，每個(gè)桶上有0個(gè)元素for(int i = 0; i != dsize; ++i){++numofeachbucket[(arr[i]/exp)%10]; //記錄該數(shù)位上相同的元素個(gè)數(shù)}for(int i = 1; i < 10; ++i){numofeachbucket[i] += numofeachbucket[i-1]; //每個(gè)位數(shù)區(qū)間的最大下標(biāo)+1的值（現(xiàn)在存儲(chǔ)的是下標(biāo)區(qū)間的上限+1）}int *output = new int [dsize];for(int i = dsize-1; i >= 0; --i){output[--numofeachbucket[(arr[i]/exp)%10]] = arr[i]; //把數(shù)組放在不同的區(qū)間位置上}for(int i = 0; i != dsize; ++i){arr[i] = output[i]; //一個(gè)數(shù)位排好后，寫回原數(shù)組}delete [] output;output = NULL; } void radixsort(size_t dsize, int *arr) {if(dsize <= 1){return;}int maxval = arr[0];for(size_t i = 0; i != dsize; ++i){maxval = arr[i] > maxval ? arr[i] : maxval; //找出最大的數(shù)}for(int exp = 1; maxval/exp > 0; exp *= 10) //從最低位開始對(duì)每個(gè)數(shù)位進(jìn)行排序{radix_countsort(dsize, arr, exp);} }

總結(jié)

以上是生活随笔為你收集整理的10种C++排序算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

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