八大排序算法之選擇排序

前面已經介紹了四種排序算法—-直接插入排序、希爾排序、冒泡排序和快速排序，今天再介紹兩種排序算法：直接選擇排序和堆排序。

這裡還是以升序為例進行說明。

一、直接選擇排序

1.基本思想

直接選擇排序也是比較簡單，容易了解的排序算法。對于一個有N個數的序列，每次周遊過程中找到序列中值最大或者最小的元素的下标并記錄下來。并将其和最左邊或者最右邊的元素進行交換，這樣的話就可以保證每次周遊都能排序好一個元素。依此類推，排序所有的元素。
           

2.排序過程

直接選擇排序中的選擇展現在每次選擇一個值最大或者值最小的元素進行交換。下面的圖是一次排序過程：
           

3.代碼實作

#include <stdio.h>
#include <stdlib.h>

void PrintArray(int *pArray, int iLen);
void Swap(int *iLhs, int *iRhs);
void SelectSort(int *pArray, int iLen);

int main(void)
{
    int iArray[] = {, , , ,  };
    int iLen = sizeof(iArray) / sizeof(*iArray);    //計算數組元素個數
    PrintArray(iArray, iLen);
    SelectSort(iArray, iLen);
    PrintArray(iArray, iLen);
    return ;
}

void PrintArray(int *pArray, int iLen)
{
    int iIndex;
    for (iIndex = ; iIndex < iLen; ++iIndex)
    {
        printf("%5d", pArray[iIndex]);
    }
    printf("\n");
}

void Swap(int *iLhs, int *iRhs)
{
    int iTemp = *iLhs;
    *iLhs = *iRhs;
    *iRhs = iTemp;
}

void SelectSort(int *pArray, int iLen)
{
    int iCount;
    int iIndex;
    for (iCount = ; iCount < iLen - ; ++iCount)  //N個數需要N-1趟
    {
        int iMinIndex = iCount;
        for (iIndex = iCount + ; iIndex < iLen; ++iIndex)
        {
            if (pArray[iMinIndex] > pArray[iIndex])     //每次将比較的兩個元素中值較大的元素下标記錄下來，一趟完了以後iMaxIndex存的是所有資料中值最大的元素的下标
            {
                iMinIndex = iIndex;
            }
        }
        if (iMinIndex != iCount)   //如果iMaxIndex值改變了說明最開始iMaxIndex裡面存的元素值不是最大的
        {
            Swap(&pArray[iMinIndex], &pArray[iCount]);  //交換兩個元素的值
        }
    }
}
           

4.算法分析

(1)時間複雜度

由上面的代碼可以有兩層循環，循環次數為為((N-1)+(N-2)+.......+2+1)=(N*(N-1))/2,是以時間複雜度O(N^2)。
           

(2)空間複雜度

空間複雜度從代碼中可以很明顯看出來為O(1)。
           

(3)穩定性

因為是跳躍式交換元素，是以是該排序算法是不穩定。
           

二、堆排序

1.基本思想

堆排序過程借助于完全二叉樹的某些概念來實作，過程不是很複雜，但需要仔細揣摩每一步。說明算法之前先介紹什麼是大根堆和小根堆。大根堆是每一個父節點都比子節點的值要大，而小根堆則相反。下面以大根堆進行說明。
基本思想是先将原始序列看成是一棵完全二叉樹組成，每個元素是一個節點。首先将這個二叉樹的每個節點調整為大根堆，此時根節點為整棵樹中值最大的節點，然後将根節點和最後一個節點進行交換，即排序出值最大的那個元素。然後繼續從根節點開始進行調整，一次排序出其他元素。
           

2.排序過程

這裡有兩點要注意的地方，我們調整大根堆時不是從最後一個節點開始，而是從最後一個節點的父節點開始進行調整；另外一點就是，已經調整好的節點不再參與下一次調整，即下一次調整時要将其剔除在外；在将整個序列調整為大根堆以後，将根節點交換到最後一個節點後，以後的每次調整隻需要調整根節點就可以了。
           

3.代碼實作

#include <stdio.h>
#include <stdlib.h>

void PrintArray(int *pArray, int iLen);
void Swap(int *iLhs, int *iRhs);
void HeapSort(int *pArray, int iLen);
void Adjust(int *pArray, int iStart, int iEnd);

int main(void)
{
    int iArray[] = {,  , ,,  };
    int iLen = sizeof(iArray) / sizeof(*iArray);    //計算數組元素個數
    PrintArray(iArray, iLen);
    HeapSort(iArray, iLen);
    PrintArray(iArray, iLen);
    return ;
}

void PrintArray(int *pArray, int iLen)
{
    int iIndex;
    for (iIndex = ; iIndex < iLen; ++iIndex)
    {
        printf("%5d", pArray[iIndex]);
    }
    printf("\n");
}

void Swap(int *iLhs, int *iRhs)
{
    int iTemp = *iLhs;
    *iLhs = *iRhs;
    *iRhs = iTemp;
}

void Adjust(int *pArray, int iStart, int iEnd)
{
    int iIndex;
    int iTemp = pArray[iStart];
    for (iIndex = iStart *  + ; iIndex < iEnd; iIndex =  * iIndex + )
    {
        //找iStart的左右孩子中值較大的那個
        if ((iIndex +  <= iEnd) && (pArray[iIndex] < pArray[iIndex + ]))
        {
            ++iIndex;
        }
        if (iTemp < pArray[iIndex])
        {
            pArray[iStart] = pArray[iIndex];
            iStart = iIndex;
        }
        else
        {
            break;
        }
    }
    pArray[iStart] = iTemp;
}

void HeapSort(int *pArray, int iLen)
{
    int iIndex;
    for (iIndex = (iLen -  - ) / ; iIndex >= ; iIndex--)
    {
        Adjust(pArray, iIndex, iLen - );
    }

    for (int i = ; i < iLen - ; ++i)
    {
        int iTemp = pArray[];
        pArray[] = pArray[iLen -  - i];
        pArray[iLen -  - i] = iTemp;
        Adjust(pArray, , iLen -  - i - );
    }
}
           

4.算法分析

(1)時間複雜度

堆排序中序列的每個元素都要進行調整，即N個元素要調整N次;然後每次調整過程中需要進行比較，而且比較是以二叉樹形式進行，是以最多需要O(logN)次，是以時間複雜度為O(NlogN)。
           

(2)空間複雜度

從代碼中可以看出，堆排序是就地排序，隻需要借助有限的臨時變量即可實作，是以空間複雜度為O(1)。
           

(3)穩定性

不穩定。