堆排序+选择排序详解

堆排序+选择排序详解

选择排序(SelectSort)，以第一个为开始值，从下一个元素开始，依次寻比开始值大/小的元素，当到最大/小的下标，此时将开始值与到的元素进行交换，这样就实现了最大/小元素的正确去向。按照这种方式，从第一个元素一直进行到倒数第二个元素，此时就是一个有序的数组。

如图所示

2.1优点

• 相较于其他排序算法，选择排序易于理解
• 更加适用于入门级学者

2.2缺点

虽然选择排序实现较为简单，首当其冲的就是他的时间复杂度，

结果一目了然，与快速排序，堆排序等相比时间复杂度较差，他的简单带来的后果就是时间复杂度较差。

既然选择排序是从第一个开始寻最大/小的，那么可不可以同时寻最大和最小，并且将他们放到正确的位置，这样就可以大大提升了选择排序的时间复杂度了。

首先要有begin和end，begin位置记录最小值，end位置记录最大值。接着就是循环条件就是i=begin+1，是从begin后面开始比较的，一直循环到end，每次i++。循环里面首先就是让mini和maxi为begin，如果有比最值更小/大的值，那就修改最值的下标。当一次循环之后，然后就是让最值去正确位置，接着begin++，end--，这样就实现了选择排序。

注意：

如果没有这个代码的话，第一个是最大的，当交换一次之后，最小值到了begin，然后最大值还是begin与end交换就错误了。

void SelectSort(int *arr,int n)
{
    int begin=0,end=n-1;
    while(begin<end)
    {
        int mini=begin,maxi=begin;
        for(int i=begin+1;i<=end;i++)
    {
        
        if(arr[mini]>arr[i])
        {
            mini=i;
        }
        if(arr[maxi]<arr[i])
        {
            maxi=i;
        }
       
       
        
        }
            if(maxi==begin)
        {
            maxi=mini;
        }
           Swap(&arr[begin],&arr[mini]);
        Swap(&arr[end],&arr[maxi]);
        end--;
        begin++;
        
     
    }
      
    

      
    }

堆排序(HeapSort),堆排序是通过建堆，然后调整，来实现排序的。堆排序着较好的时间复杂度，同时堆排序也较难理解的一种排序。

详细介绍见.2014.001.5501

void AdjustDown(int *arr,int parent,int n)
{
    int child=parent*2+1;
    while(child<n)
    {
        if(child+1<n&&arr[child]<arr[child+1])
        {
            child++;
        }
        if(arr[child]>arr[parent])
        {
            Swap(&arr[parent],&arr[child]);
            parent=child;
            child=parent*2+1;
        }
        else
        {
            break;
        }
    }
    
}

void HeapSort(int *arr,int n)
{
    for(int i=(n-1-1)/2;i>=0;i--)
    {
        AdjustDown(arr,i,n);
    }
    int end=n-1;
    while(end>0)
    {
        Swap(&arr[end],&arr[0]);
        AdjustDown(arr,0,end);
        end--;
    }
}