查看“选择类排序”的源代码


===5）直接选择类排序===
https://www.bilibili.com/video/BV1hg411V7Bm/?p=70

过程：首先在所有记录中选出排序码最小的记录，把它与第1个记录交换，然后再其余的记录内选出排序码最小的记录，与第2个记录交换......依次类推，直到所有记录排完为止。[[文件:直接选择排序.png|无|缩略图|链接=http://www.jihongchang.top/index.php/%E6%96%87%E4%BB%B6:%E7%9B%B4%E6%8E%A5%E9%80%89%E6%8B%A9%E6%8E%92%E5%BA%8F.png]]<syntaxhighlight lang="c">
void selectSort(int data[], int n)
{
    //对data[0]~data[n-1]中的n个整数按非递减有序的方式进行排列
    int i,j,k;
    int temp;
    for(i = 0; i < n - 1; i++)
    {
        for(k = i, j = i + 1; j < n; j++) //k表示data[i]~data[n-1]中最小元素的下标
        {
            if(data[j] < data[k]) {
                k = j;
            }
            if(k!=i){
                //将本趟找出的最小元素与data[i]交换
                temp=data[i];
                data[i]=data[k];
                data[k]=temp;
            }
        }//end inner for
    }//end outter for
}
</syntaxhighlight>
===4）堆排序===
设有n个元素的序列{K<sub>1</sub>，K<sub>2，</sub>...，K<sub>n</sub>}，当且仅当满足下述关系之一时，称之为堆。

（1）K<sub>i</sub>≤K<sub>2i</sub>且K<sub>i</sub>≤K<sub>2i+1</sub>；（父结点总是小于孩子结点）

（2）K<sub>i</sub>≥K<sub>2i</sub>且Ki≥K<sub>2i+1</sub>。（父结点总是大于孩子结点）

其中（1）称为小顶堆/小根堆，（2）称为大顶堆/大根堆[[文件:小顶堆和大顶堆.png|无|缩略图|600x600像素|链接=http://www.jihongchang.top/index.php/%E6%96%87%E4%BB%B6:%E5%B0%8F%E9%A1%B6%E5%A0%86%E5%92%8C%E5%A4%A7%E9%A1%B6%E5%A0%86.png]][[文件:堆排序过程.png|无|缩略图|600x600像素|链接=http://www.jihongchang.top/index.php/%E6%96%87%E4%BB%B6:%E5%A0%86%E6%8E%92%E5%BA%8F%E8%BF%87%E7%A8%8B.png]]堆排序的时间复杂度为：O(nlog<sub>2</sub>n)

===考点：大顶堆和小顶堆===
对于n个元素的关键字序列{K<sub>1</sub>，K<sub>2</sub>，...，K<sub>n</sub>}，当且仅当满足K<sub>i</sub>≤K<sub>2i</sub>且K<sub>i</sub>≤K<sub>2i+1</sub>(1<i<n/2)，则称该序列为小顶堆。

若将其中的“≤”换为“≥”则称其为大顶堆。

由此可知，（）是大顶堆。

A、7，2，3，4，5，6，1

B、7，5，4，2，6，3，1

C、7，6，4，2，5，3，1  √

D、7，5，3，1，6，4，2

解：

选项中的数列就是0，1，2，3，4，5，6作为i参数，按4个选项中的序列顺序画树，看哪个符合大顶堆的定义：K<sub>i</sub>≥K<sub>2i</sub>且K<sub>i</sub>≥K<sub>2i+1</sub>

A
{| class="wikitable"
! colspan="3" |7
|-
! colspan="2" |2
!3
|-
!4
!
!
|}2作为4的父结点却小于4，所以不是大顶堆。


B
{| class="wikitable"
! colspan="3" |7
|-
! colspan="2" |5
!4
|-
!2
!6
!
|}5作为6的父结点却小于6，所以不是大顶堆。


C
{| class="wikitable"
! colspan="4" |7
|-
! colspan="2" |6
! colspan="2" |4
|-
!2
!5
!3
!1
|}父结点均大于子节点，符合大顶堆的定义。


D
{| class="wikitable"
! colspan="3" |7
|-
! colspan="2" |5
!3
|-
!1
!6
!
|}5作为6的父结点却小于6，所以不是大顶堆。