选择排序

直接选择排序：

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

typedef int T;void SelectSort(T a[],int length){    for (int i=0;i

复杂度分析：

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

堆排序：

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

http://blog.csdn.net/clam_clam/article/details/6799763 

//调整为大顶堆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]
     
      0;i--)   {      shift(a,i,n);                   //n只是起条件判断作用，并不参与实际计算。   }}
     

void HeapSort(int *a,int size)    //堆排序 {
       int i;     BuildHeap(a,size);     for(i=size;i>=1;i--)     {
           //cout<
     
      <<" ";         swap(a[1],a[i]);           //交换堆顶和最后一个元素，即每次将剩余元素中的最大者放到最后面           //BuildHeap(a,i-1);        //将余下元素重新建立为大顶堆           HeapAdjust(a,1,i-1);      //重新调整堆顶节点成为大顶堆     } }
     

补充：

复杂度表：

稳定性：

稳定的排序算法：插入排序，冒泡排序，归并排序。

不稳定排序算法：选择排序，希尔排序，快速排序，堆排序。

排序算法选择：

1.数据规模较小

  （1）待排序列基本序的情况下，可以选择直接插入排序；

  （2）对稳定性不作要求宜用选择排序，对稳定性有要求宜用插入或冒泡

2.数据规模不是很大

（1）完全可以用内存空间，序列杂乱无序，对稳定性没有要求，快速排序，此时要付出log（N）的额外空间。

（2）序列本身可能有序，对稳定性有要求，空间允许下，宜用归并排序

3.海量级别的数据，必须按块放在外存上

   （1）对稳定性有求，则可考虑归并排序。

    （2）对稳定性没要求，宜用堆排序

 

算法总结：http://blog.csdn.net/morewindows/article/details/7961256