快速排序
時(shí)間復(fù)雜度：O(NlogN)
空間復(fù)雜度：O(NlogN)
最壞情況：當(dāng)數(shù)組全都排好序時(shí)痴奏，此時(shí)劃分區(qū)間會(huì)出現(xiàn)一個(gè)為0，一個(gè)為n的情況水孩，此時(shí)的時(shí)間復(fù)雜度是O(N*N)
算法不穩(wěn)定
void quickSort(int* pArr,int nLIndex,int nRIndex{
if(pArr==NULL||nLIndex>=nRIndex||nLIndex<0)
return;
int nL = nLIndex;
int nR = nRIndex;
int nFlag = pArr[nL];
while (nL<nR) {
while (nL<nR) {
if (pArr[nR]<nFlag) {
pArr[nL] = pArr[nR];
break;
} nR--;
}
while (nL<nR) {
if (pArr[nL]>nFlag) {
pArr[nR] = pArr[nL];
break;
}
nL++;
}
}
pArr[nL] = nFlag;
quickSort(pArr, nLIndex, nL-1);
quickSort(pArr, nL+1, nRIndex);
}
堆排序
時(shí)間復(fù)雜度：O(NlogN)
空間復(fù)雜度：O(1)痕鳍，每次只需要交換一個(gè)元素级遭。
最壞情況：也是O(NlogN)疲憋。即使排序好了凿渊，也只影響建堆，不影響每次排序并swap的時(shí)間。因此一直是O(N*logN)埃脏。
算法不穩(wěn)定
void swap(int &nA,int &nB){
int nTmp = nA;
nA = nB;
nB = nTmp;
}
void shiftUp(int *pArr, int nNode, int nSize){
if (pArr==NULL&&nSize<=0) {
return;
}
int nLChild = 2*nNode;
int nRChild = 2*nNode+1;
int nMax = nNode;
if (nLChild<nSize&&pArr[nLChild]>pArr[nMax]) {
nMax = nLChild;
}
if (nRChild<nSize&&pArr[nRChild]>pArr[nMax]) {
nMax = nRChild;
}
if (nMax!=nNode) {
swap(pArr[nNode],pArr[nMax]);
shiftUp(pArr, nMax, nSize);
}
}
void buildHeap(int *pArr, int nSize){
for (int nIndex = nSize/2; nIndex>=0; nIndex--) {
shiftUp(pArr, nIndex, nSize);
}
}
歸并排序
時(shí)間復(fù)雜度：O(N*logN)
空間復(fù)雜度：O(n)搪锣，占用的空間較多。
算法穩(wěn)定
void merge(int* pArr,int nL,int nM,int nR,int* pTmp){
if (pArr==NULL||pTmp==NULL) {
return;
}
int i=nL;
int j=nM+1;
int k=nL;
while (i<=nM&&j<=nR) {
if (pArr[i]<pArr[j]) {
pTmp[k] = pArr[i++];
} else{
pTmp[k] = pArr[j++];
} k++;
}
while (i<=nM) {
pTmp[k++] = pArr[i++];
}
while (j<=nR) {
pTmp[k++] = pArr[j++];
}
for (int nIndex=nL; nIndex<=nR; nIndex++) {
pArr[nIndex] = pTmp[nIndex];
}
}
void mergeSort(int* pArr,int nL,int nR,int* pTmp)
{
if (nL<nR) {
int nM = (nL+nR)/2;
mergeSort(pArr,nL,nM,pTmp);
mergeSort(pArr,nM+1,nR,pTmp);
merge(pArr,nL,nM,nR,pTmp);
}
}
