---

选择排序的思想是：每一趟从待排序的数据元素中选出最小（或最大）的一个元素，顺序放在已排好序的数列的最后，直到全部待排序的数据元素排完。

下面是基本选择排序的实现算法：

 

void selectsort(int a[], int n)

{

     int i, j, k, tmp;

     for (i = 1; i <= n-1; i++)

    {

         k = i;

         for (j = i + 1; j <= n; j++)

        {

              if (a[j] < a[k])

                   k = j;

         }

         if (k != i)

        {

              tmp = a[i];

              a[i] = a[k];

              a[k] = tmp;

         }

     }

}

 

简单选择排序的时间复杂度为O(n²)，它是不稳定排序。

 

堆排序是一树形选择排序，在排序过程中，将R[1..N]看成是一颗完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系来选择最小的元素。

 

void sfilter(int a[], int l, int m)

{

     int i, j x;

     i = l;

     j = 2 * i;

     x = a[i];

     while ( j <= m)

    {

         if (j < m && a[j] < a[j+1])

              j++;

         if (x < a[j])

        {

              a[i] = a[j];

              i = j;

              j = 2 * i;

         }

        else

        {

              j = m + 1;

         }

     }

     a[i] = x;

}

void heapsort(int a[], int n)

{

     int i, w;

     for (i = n/2; i >= 1; i--)

         sfilter(a, i, n);

     for (i = n; i >= 2; i--)

    {

         w = a[i];

         a[i] = a[1];

         a[1] = w;

         sfilter(a, 1, i - 1);

     }

}

 

堆排序的时间复杂度为O(nlogn)，它是不稳定排序。