選擇排序

選擇排序(SelectionSort)的基本思想是：每次從當前待排序的記錄中選取關鍵字最小的記錄表，然後與待排序的記錄序列中的第一個記錄進行交換，直到整個記錄序列有序為止。

1.簡單選擇排序

簡單選擇排序(Simple Selection Sort，又稱為直接選擇排序)的基本操作是：通過n-i次關鍵字間的比較，從n-i+1個記錄中選取關鍵字最小的記錄，然後和第i個記錄進行交換，i=1,2, …n-1 。

1 .1 排序示例

1.2 算法實例

//選擇排序
#include 
#include 

#define SIZE 10

void SelectionSort(int *a,int len)
{
    int i,j,k,h;
    int temp;
    
    for (i=0; i
運行結果如圖：

              





2.堆排序


<喎?http://www.Bkjia.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8aDI+Mi4xICC20bXEtqjS5TwvaDI+CjxwPjwvcD4KPHA+PGJyPgo8L3A+CjxwPiAgICAgICAgysduuPbUqsvYtcTQ8sHQSD17azEsIGsyICwgoa1rbn0go6zC+tfjo7o8L3A+CjxwPjxicj4KPC9wPgo8cD48aW1nIHNyYz0="http://www.Bkjia.com/uploadfile/Collfiles/20131224/20131224104656238.jpg" alt="\">






     由堆的定義知，堆是一棵以k1為根的完全二叉樹。若對該二叉樹的結點進行編號(從上到下，從左到右)，得到的序列就是將二叉樹的結點以順序結構存放，堆的結構正好和該序列結構完全一致。



2.2  堆的性質



       ①  堆是一棵采用順序存儲結構的完全二叉樹，k1是根結點；
       ②  堆的根結點是關鍵字序列中的最小(或最大)值，分別稱為小(或大)根堆；
       ③  從根結點到每一葉子結點路徑上的元素組成的序列都是按元素值(或關鍵字值)非遞減(或非遞增)的；
       ④堆中的任一子樹也是堆。
        利用堆頂記錄的關鍵字值最小(或最大)的性質，從當前待排序的記錄中依次選取關鍵字最小(或最大)的記錄，就可以實現對數據記錄的排序，這種排序方法稱為堆排序。



2.3   堆排序思想



       ①  對一組待排序的記錄，按堆的定義建立堆；
       ②  將堆頂記錄和最後一個記錄交換位置，則前n-1個記錄是無序的，而最後一個記錄是有序的；
       ③  堆頂記錄被交換後，前n-1個記錄不再是堆，需將前n-1個待排序記錄重新組織成為一個堆，然後將堆頂記錄和倒數第二個記錄交換位置，即將整個序列中次小關鍵字值的記錄調整(排除)出無序區；
       ④  重復上述步驟，直到全部記錄排好序為止。



       結論：排序過程中，若采用小根堆，排序後得到的是非遞減序列；若采用大根堆，排序後得到的是非遞增序列。




4.4  堆的調整——篩選




⑴ 堆的調整思想
       輸出堆頂元素之後，以堆中最後一個元素替代之；然後將根結點值與左、右子樹的根結點值進行比較，並與其中小者進行交換；重復上述操作，直到是葉子結點或其關鍵字值小於等於左、右子樹的關鍵字的值，將得到新的堆。稱這個從堆頂至葉子的調整過程為“篩選”，如圖10-10所示。

注意：篩選過程中，根結點的左、右子樹都是堆，因此，篩選是從根結點到某個葉子結點的一次調整過程。










2.5   代碼實現：
//堆排序
#include 
#include 

#define SIZE 10

void HeapSort(int a[],int n)
{
    int i,j,h,k;
    int t;
    
    for (i = n/2-1; i >= 0; i--)
    {
        while (2*i + 1 < n)
        {
            j = 2*i + 1;
            if ((j+1) < n)
            {
                if (a[j] < a[j+1])
                {
                    j++;
                }
            }
            
            if (a[i]0; i--)
    {
        t = a[0];
        a[0] = a[i];
        a[i] = t;
        k =0;
        while (2*k+1









參考書籍:《C/C++常用算法手冊》  《數據結構-清華大學嚴蔚敏》