【数据结构】简单选择排序、堆排序

选择排序：每一趟在待排序元素中选取关键字最小（或最大）的元素加入有序子序列。

1. 简单选择排序

1. 执行过程

说明：第1趟将最小的13加入到0的位置，和原来49互换位置。第2趟在剩余待排序序列中将27加入到1的位置，和原来38互换位置，依次类推...

2. 算法实现

// 交换
void swap(int &a,int &b){
    int temp=a;
    a=b;
    b=temp;
}

// 简单选择排序
void SelectSort(int A[],int n){
    for(int i=0;i<n-1;i++){  // 一共进行n-1趟
        int min=i;  // 记录最小元素
        for(int j=i+1;j<n;j++){  // 在A[i...n-1]中选择最小的元素
            if(A[j]<A[min]){
                min=j;  // 更新最小元素位置
            }
        }
        if(min!=i){
            swap(A[i],A[min]);  // 封装的swap()函数共移动元素3次
        }
    }
}

3. 算法性能分析

空间复杂度：O(1)

时间复杂度：O(n^2)

稳定性：不稳定。

4. 适用性

即可适用于顺序表，也可适用于链表。

2. 堆排序

1. 堆的定义

若n个关键字序列L[1,2,...,n]满足下面某一条性质，则称为堆（Heap）：

若满足：L(i)>=L(2i)且L(i)>=L(2i+1)(1<=i<=n/2)，则称为大根堆（大顶堆）。
若满足：L(i)<=L(2i)且L(i)<=L(2i+1)(1<=i<=n/2)，则称为小根堆（小顶堆）。

【数据结构】二叉树的性质与存储结构

2. 建立大根堆

大根堆：根>=左、右

思路：把所有非终端结点都检查一遍，是否满足大根堆的要求，如果不满足，则进行调整。

i向左移动，继续上述操作，直到最大的元素在根结点。同时需要注意，若元素的互换破坏了下一级的堆，则采用相同的方法继续往下调整（小元素不断“下坠”）。

3. 算法实现

选择排序：每一趟在待排序元素中选取关键字最大的元素加入有序子序列。

堆排序：每一趟将对顶元素加入有序子序列（与待排序序列中的最后一个元素交换）。

并将待排序元素序列再次调整为大根堆（小元素不断“下坠”）。

// 将以k为根的子树调整为大根堆
void HeadAdjust(int A[],int k,int len){
    A[0]=A[k];  // A[0]暂存子树的根结点
    for(int i=2*k;i<len;i*=2){  // 沿key较大的子结点向下筛选
        if(i<len && A[i]<A[i+1]){
            i++;  // 取key较大的子结点的下标
        }
        if(A[0]>=A[i]){
            break;  // 筛选结束
        }else{
            A[k]=A[i];  // 将A[i]调整到双亲结点上
            k=i;  // 修改k值，以便继续向下筛选
        }
    }
    A[k]=A[0];  // 被筛选结点的值放入最终位置
}

// 建立大根堆
void BuildMaxHeap(int A[],int len){
    for(int i=len/2;i>0;i--){  // 从后往前调整所有非终端结点
        HeadAdjust(A,i,len);
    }
}

// 堆排序完整逻辑
void HeapSort(int A[],int len){
    BuildMaxHeap(A,len);  // 初始建堆
    for(int i=len;i>1;i--){  // n-1趟交换和建堆过程
        swap(A[i],A[1]);  // 堆顶元素和堆底元素互换
        HeadAdjust(A,1,i-1);  // 把剩余的待排序元素整理成堆
    }
}