選擇排序

選擇排序的基本思想： 每一趟(第i趟，i=0,1，…，n-2)在後面n-i個待排序的資料元素集合中選出關鍵碼最小的資料元素，作為有序元素序列的第i個元素。待到第n-2趟 做完，待排序元素集合中隻剩下1個元素，排序結束。

選擇排序主要包括：直接選擇排序和堆排序

1.直接選擇排序

【直接選擇排序】

• 在元素集合array[i]–array[n-1]中選擇關鍵碼最大(小)的資料元素
• 若它不是這組元素中的最後一個(第一個)元素，則将它與這組元素中 的最後一個（第一個）> 元素交換
• 在剩餘的array[i]–array[n-2]（array[i+1]–array[n-1]）集合中， 重複上述步驟，直到集合剩餘> 1個元素

特性：

• 直接選擇排序的時間複雜度為O(n^2)；
• 它是一種不穩定的排序算法

C語言實作

//##################################  1.1 直接選擇排序
//直接選擇排序
//直接選擇排序的時間複雜度為O(n^2)； 
//它是一種不穩定的排序算法
void SelectSort(int* array, int size)
{

    for (int i = ; i < size - ; i++)
    {
        int min_ = i;
        for (int j = i+; j < size ; j++)
        {
            if (array[j] < array[min_])
            {
                min_ = j;
            }
        }
        if (min_ != i)
        {
            array[min_] ^= array[i];
            array[i] ^= array[min_];
            array[min_] ^= array[i];
        }
    }
}
           

上面的代碼每一次排序隻移動了一個最大的或者最小的，我們可以通過一次移動一個最大的和一個最小的來減少整體排序的次數，使直接選擇排序得以優化。

C語言實作

//#################################  1.2 直接選擇排序優化
// 使用每次找最大最小元素對選擇排序進行優化 
void SelectSort_OP(int* array, int size)
{
    for (int i = ; i < size/; i++)
    {
        int max_ = i;
        int min_ = i;
        for (int j = i + ; j < size - i; j++)//尋找最小的和最大的資料
        {
            if (array[max_] < array[j])
                max_ = j;
            if (array[min_] > array[j])
                min_ = j;
        }
        if (min_ != i)//交換最小的資料
        {
            if (max_ == i)//這裡有一個問題，如果最小值要交換的位置剛好是最大值得位置，那麼就要改變最大值得位置，確定max_所在的值為最大值
                max_ = min_;
            swap(&array[min_], &array[i]);//交換資料
        }

        if(max_ != size -  - i)//交換最大的資料
            swap(&array[max_], &array[size--i]);//交換資料
    }
}
           

要注意的一點，在找到最小值和最大值之後，因為先要交換的是最小值，那麼要保證，最小值所要交換的位置不是最大值的位置，確定沒有改變最大值，否則在下面交換最大值時，max_ （最大值得下标）所指向的已将不是最大值，最大值已經最小值被換走。是以在交換之前要判斷一下目标位置是否是最大值得位置，如果不是則繼續交換，沒有影響，如果是最大值的位置，就要使max_ 等于 min_ ,因為在最小值交換完成後（實際上是最大值和最小值進行交換），最大值的位置已經跑到最小值得位置了。

2.堆排序

思路：執行如下步驟，直到數組為空

• 把堆頂array[0]元素和目前最堆的最後一個元素交換
• 堆元素個數減1
• 由于第1步後根節點不再滿足最堆定義，向下調整根結點
• 把一棵完全二叉樹調整為堆，以及每次将堆頂元素交換後進行調整的時間複雜度均為O( log(2) n )，是以堆排序的時間複雜度為：O(n * log(2) n )
• 堆排序是一種不穩定的排序算法

C語言實作：

//###########################################  2.堆排序
//堆排序的時間複雜度為：O(n*log_n)
//堆排序是一種不穩定的排序算法

// 堆調整 向下調整 
void HeapAdjust(int* array, int size, int parent)
{
    int Lchild = parent *  + ;
    int Rchild = Lchild + ;
    while (Lchild < size)
    {
        if (Rchild < size && array[Rchild] < array[Lchild])
            Lchild = Rchild;
        if (array[Lchild] < array[parent])
        {
            swap(&array[Lchild], &array[parent]);//交換函數
            parent = Lchild;
            Lchild = parent * ;
            Rchild = Lchild + ;
        }
        else
            break;
    }
}

// 堆排序 
void HeapSort(int* array, int size)
{
    //建堆
    int parent = (size - ) >> ;//時間複雜度：n/2 * log_n

    for (; parent >= ; parent--)
    {
        HeapAdjust(array, size, parent);
    }

    //排序
    while (--size)// 時間複雜度：n * log_n
    {
        swap(&array[], &array[size]);
        HeapAdjust(array, size, );
    }
}