标题:实现选择排序,堆排序


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

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

 

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(n2),它是不稳定排序。

 

堆排序是一树形选择排序,在排序过程中,将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),它是不稳定排序。



看文字不过瘾?点击我,进入腾讯课堂视频教学
麦洛科菲长期致力于IT安全技术的推广与普及,我们更专业!我们的学员已经广泛就职于BAT360等各大IT互联网公司。详情请参考我们的 业界反馈 《周哥教IT.C语言深学活用》视频

我们的微信公众号,敬请关注