排序总结

快速排序

时间复杂度：O(NlogN)
空间复杂度：O(NlogN)
最坏情况：当数组全都排好序时，此时划分区间会出现一个为0，一个为n的情况，此时的时间复杂度是O(N*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);
}

堆排序

时间复杂度：O(NlogN)
空间复杂度：O(1)，每次只需要交换一个元素。
最坏情况：也是O(NlogN)。即使排序好了，也只影响建堆，不影响每次排序并swap的时间。因此一直是O(N*logN)。
算法不稳定

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); 
    }
}

归并排序

时间复杂度：O(N*logN)
空间复杂度：O(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); 
      }
}