选择排序介绍

选择排序的核心思想是：每一趟从无序区中选出关键字最小的元素，按顺序放在有序区的最后，新生成的有序区元素个数加1，无序区元素个数减1，知道全部排完为止。

• 直接选择排序

也称简单选择排序，整个过程就是每一趟都将无序区中的元素进行逐一比较，找到最小的元素，与无序区中的首个元素进行交换，有序区长度加1，无序区长度减1。重复以上步骤，直到所有元素均已排好。

• 树形选择排序

也称锦标赛排序，是为了优化每次在无序区中确定最小元素时比较次数过多的问题。核心思想是借助树形结构对整个序列进行两两比较，将数值较小的元素作为优胜者上升到父节点。最后能够在树形结构中记录每一次优胜者之间的关系，按规则取出即可。

• 堆排序

堆排序是对树形选择排序的优化，由于树形选择排序需要花费较多的存储空间，堆排序的主要思想是构建一个小顶堆（升序排列中），整个过程就是不断的弹出堆顶元素，归入有序区，然后继续将堆中剩余元素调整为小顶堆，重复这个过程，直到排好所有元素。

直接选择排序

• 输入

n个数的序列，通常直接存放在数组中，可能是任何顺序。

• 输出

输入序列的一个新排列，满足从小到大的顺序（默认讨论升序，简单的修改就可以实现降序）

• 算法说明

直接选择排序的主要步骤是：在第1趟中，从n个记录中找出关键字最小的记录与第一个记录交换；在第2趟中，从n-1个记录中找出关键字最小的记录与第二个记录交换；可以归纳为：从第i趟中，从n-i+1个记录中找出关键字最小的记录与第i个记录交换；直到完成i=n-1时的操作，此时整个序列有序。

伪代码

for i= 1 to n-1
    k=i
    for j=i+1 to n
        if A[j]<A[k]
            k = j
    if k!=i
        exchange A[i] with A[k]