排序算法--选择排序,堆排序

          介绍学习完插入排序和交换排序，本篇博客来学习选择排序，选择排序的基本思想是：每趟从待排的记录中选出关键字最小的记录，顺序放在已经排好序子表的最后，直到全部记录排序完毕。由于选择排序每趟总是从无序区中选出全局最小或最大的关键字，所以适合于大量的记录中选择一部分排序记录。在这里，我们主要介绍选择排序里的直接选择排序和堆排序。

 

1.直接选择排序(简单选择排序)

 

基本思想

           在要排序的一组数中，选出最小（或者最大）的一个数与第1个位置的数交换；然后在剩下的数当中再找最小（或者最大）的与第2个位置的数交换，依次类推，直到第n-1个元素（倒数第二个数）和第n个元素（最后一个数）比较为止。

 

示例图

 

实现代码

 

//直接选择排序
void  SelectSort(int a[],int len)
{
	int k,j;
	for(int i=0;i<len-1;i++)//要进行len-1趟选择
	{
		k=i;

		for(j=i+1;j<len;j++)//寻找最小，从未排序区间开始，即i+1
		{
			if(a[k]>a[j])
			{
				k=j;
			}
		}
		//i本身不是最小
		if(k!=i)
		{
			int temp=a[k];
			a[k]=a[i];
			a[i]=temp;
		}
	}

	for(int i=0;i<len;i++)
		cout<<a[i]<<" ";
}

 

效率分析

 

     当初始表为正序时，记录移动次数为0，初始表为反序时，每趟均要进行交换操作，然而，无论记录的初始状态如何，都要进行相同次数的关键字对比，均为(n(n-1))/2，因此总的平均时间复杂度为O(n^2)。

      直接选择排序算法只使用了几个辅助变量，与问题规模n无关，故辅助空间复杂度为O(1)，是一个就地排序，另外，直接选择排序是一个不稳定的排序，可能会交换相等关键字的前后顺序。

 

 

2.堆排序

     堆排序是一种树形的选择排序，是对直接选择排序的有效改进

 

 堆的定义：

        n个元素的序列{k₁，k₂，…,k_n}当且仅当满足下列关系之一时，称之为堆。

　　情形1：k_i <= k_2i 且k_i <= k_2i+1 （最小化堆或小顶堆）

 

　　情形2：k_i >= k_2i 且k_i >= k_2i+1（最大化堆或大顶堆）

 

       堆是一种完全二叉树或者近似完全二叉树，所以效率极高。

 

例如：

（a）大顶堆序列：（96, 83,27,38,11,09)----根结点大于孩子结点

  (b)  小顶堆序列：（12，36，24，85，47，30，53，91）----根结点小于孩子结点

 堆排序的思想

      利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中选择最大记录(最小记录)变得简单。

 其基本思想为(大顶堆)：

    1)将初始待排序关键字序列(R0,R2....Rn-1)构建成大顶堆，此堆为初始的无序区；

    2)将堆顶元素R[0]与最后一个元素R[n-1]交换，此时得到新的无序区(R0,R2,......Rn-2)和新的有序区(Rn-1),且满足R[1,2...n-2]<=R[n-1]; 

    3)由于交换后新的堆顶R[0]可能违反堆的性质，因此需要对当前无序区(R0,R2,......Rn-2)调整为新堆，然后再次将R[0]与无序区最 后一个元素交换，得到新的无序区(R0,R2....Rn-3)和新的有序区(Rn-2,Rn-1)。不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。

 

例如：

 

给定一个整形数组a[]={16,7,3,20,17,8}，对其进行堆排序，我们使用大顶堆。

首先根据该数组元素构建一个完全二叉树，得到

 

 然后需要构造初始堆，则从最后一个非叶节点开始调整，调整过程如下：

 

 最后得到初始堆

 把20和3交换位置(堆顶的元素和最后一个元素)

 

 交换之后可能造成被交换的孩子节点不满足堆的性质，因此每次交换之后要重新对被交换的孩子节点进行调整。此时放到最后的20不在进行堆排序。初始化堆得到

 把17和3交换位置(堆顶的元素和最后一个元素,红色的20不参与)得

 以此类推，最后得到

 

     这样整个区间便已经有序了。由排序过程可见，若想得到升序，则建立大顶堆，若想得到降序，则建立小顶堆。 从上述过程可知，堆排序其实也是一种选择排序，是一种树形选择排序。

 

实现代码

 

调整建立初始堆函数为：

//堆排序--初始化堆函数
//完全二叉树若根节点n为从0开始，则左孩子为2n+1，右孩子为2n+2。
void  init(int a[],int start,int end)//对a[low....high]进行初始化
{
	int temp = a[start];

    for(int i = 2*start + 1; i<=end; i*=2)
    {
        //因为假设根结点的序号为0而不是1，所以i结点左孩子和右孩子分别为2i+1和2i+2
        if(i<end &&a[i]<a[i+1])//左右孩子的比较
        {
            i++;//i为较大的记录的下标
        }

        if(temp > a[i])//左右孩子中获胜者与父亲的比较
        {
            break;
        }

        //将孩子结点上位，则以孩子结点的位置进行下一轮的筛选
        a[start]= a[i];
        start = i;
        
    }

    a[start]= temp; //插入最开始不和谐的元素

}

 

堆排序代码

void HeapSort(int a[],int len)
{
	//先建立大顶堆
    for(int i=len/2; i>=0; --i)
    {
        init(a,i,len);
    }
    //进行排序
    for(int i=len-1; i>0; --i)
    {
        //最后一个元素和第一元素进行交换
        int temp=a[i];
        a[i] = a[0];
        a[0] = temp;

        //然后将剩下的无序元素继续调整为大顶堆
        init(a,0,i-1);
    }
	
	//输出结果
	for(int i=0;i<len;i++)
		cout<<a[i]<<" ";
}

 

效率分析

     堆排序的时间主要由建立初始堆和反复重建初始堆着两部分时间构成。堆排序最坏的时间复杂度为O(nlog2(n)),堆排序为不稳定排序,可能改变相等元素的前后位置，由于初始化堆需要比较次数较多，所以堆排序不适合记录较少的排序。

 

附上源码地址：https://github.com/longpo/algorithm/tree/master/SelectSort