选择排序 -- 简单选择排序、堆排序

简单选择排序

// 简单选择排序
void SelectSort(RecType R[], int n)
{
?? ?int i, j, k;
?? ?for (i = 0; i < n - 1; i++)
?? ?{
?? ??? ?k = i;
?? ??? ?for (j = i + 1; j < n; j++) //找最小
?? ??? ??? ?if (R[j].key < R[k].key)
?? ??? ??? ??? ?k = j;
?? ??? ?if (k != i)
?? ??? ??? ?swap(R[i], R[k]);
?? ?}
}

堆排序

// 堆排序
void sift(RecType R[], int low, int high)
{
?? ?int i = low, j = 2 * i; //j是i的左孩子
?? ?RecType tmp = R[i];
?? ?while (j <= high)
?? ?{
?? ??? ?if (j < high && R[j].key < R[j + 1].key) //右孩子大，j指向右孩子 否则为左孩子
?? ??? ??? ?j++;
?? ??? ?if (tmp.key < R[j].key) //根节点小于最大的孩子
?? ??? ?{
?? ??? ??? ?R[i] = R[j]; ?//R[j] 调整到双亲结点的位置
?? ??? ??? ?i = j; //便于向下筛选
?? ??? ??? ?j = 2 * i;
?? ??? ?}
?? ??? ?else break; //根节点已最大
?? ?}
?? ?R[i] = tmp; // 被筛选的结点放入到最终位置
}
void HeapSort(RecType R[], int n)
{
?? ?int i;
?? ?for (i = n / 2; i >= 1; i--) ?// 建立初始堆
?? ??? ?sift(R, i, n);
?? ?for (i = n; i >= 2; i--) //
?? ?{
?? ??? ?swap(R[1], R[i]); // 最后一个元素与根R[1]交换
?? ??? ?sift(R, 1, i - 1);
?? ?}
}