排序算法--（二）

时间：2014-06-07 21:11:01 阅读：391 评论：0 收藏：0 [点我收藏+]

选择排序

直接选择排序：

选择排序，每一趟找到一个最小（大）值，每一趟遍历的数据减少一次。

template <typename T>
void SelectSort(T a[],int length)
{
    T temp;
    for (int i=0;i<length;i++)
    {
        int k =i;
        for (int j=i+1;j<length;j++)
        {
            if (a[j]<a[k])
                k=j;           //这里只是对比它小的元素中最小的位置进行标记，每次相当于最多移动一次。
        }
        if(k!=i)
            swap(a[i],a[k]);
    }
}

复杂度分析：

可以看出，选择排序过程中所需要进行记录移动的操作次数最少为0，最大值为3（n-1）。然而，无论记录的初始排序如何，所需进行的关键字间的比较次数相同。均为n(n-1)/2.所以时间复杂度为O(n²),附加存储空间为O（1）。

堆排序：

由于堆排序是一个完全二叉树，则在实际操作过程中，我们通常用一维数组存储一个堆。

//调整为大顶堆
void shift(int a[],int i,int length)
{
   int j=2*i;
   while(j<=(length-1))              //j<=(length-1)表示存在子树（左子树或者右子树）的时候就要进行判断
   {
      if(j<(length-1)&&a[j]<a[j+1])  //j<(length-1) 表示当存在右子树的时候
          j++;
      if(a[i]<a[j])
          swap(a[i],a[j]);

      i=j;j=2*i;
   }
}

//建堆
void createHeap(int &a[],int n)
{
   int i; 
   for (i=n/2;i>0;i--)
   {
      shift(a,i,n);                   //n只是起条件判断作用，并不参与实际计算。
   }
}