内部排序之选择排序：简单选择排序，堆排序

2019-11-14 08:56:59

字体：大中小

来源：转载

供稿：网友

这里写图片描述

#include<stdio.h>#include <stdio.h>#define N 10void Select_Sort(int A[],int n){ int i,j,min,temp; for(i=0;i<n;i++) //一共进行n趟 { min=i; //将第一位记录为最小元素 for(j=i+1;j<n;j++) //在A[i...n-1]中选择最小的元素 { if(A[j]<A[min]) //如果有后序元素要比最小值要小，更新最小元素 { min=j; } } if(min!=i) //A[min]与A[i]交换(将最小元素放在已排号序列后面) { temp=A[min]; A[min]=A[i]; A[i]=temp; } }}int main() { int m = 0; int B[N] = {4,5,6,1,2,3,7,8,9}; PRintf("=============================/n/n"); printf("排序前的数据是:/n4 5 6 1 2 3 7 8 9/n"); Select_Sort(B,10); printf("排序后的结果是：/n"); for(m=1; m<N;m++) { printf(" %d ", B[m]); } printf("/n/n=============================/n/n"); return 0; }

这里写图片描述

#include<stdio.h>#define N 10void Adjust_Down(int A[],int k,int n) //将元素k向下进行调整{ int i,temp; A[0]=A[k]; //A[0]作为哨兵暂存A[k] for(i=2*k;i<n;i*=2) //沿key较大的子节点向下筛选 { if(i<n&&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 Build_Max_Heap(int A[],int n) //建立大根堆{ int i; for(i=n/2;i>0;i--) //反复调整堆 { Adjust_Down(A,i,n); }}void Heap_Sort(int A[],int n){ int i,temp; Build_Max_Heap(A,n); for(i=n;i>1;i--) { temp=A[i]; //输出栈顶元素（和堆底元素交换） A[i]=A[1]; A[1]=temp; Adjust_Down(A,1,i-1);//整理，把剩余i-1个元素整理成堆 }}int main() { int m ; int B[N] = {0,1,6,8,2,3,7,4,5}; printf("=============================/n/n"); printf("排序前的数据是:/n0 1 6 8 2 3 7 4 5/n"); Build_Max_Heap(B,9); printf("建立大堆根后的顺序序列为(完全二叉)：/n"); for(m=1; m<N;m++) { printf(" %d ", B[m]); } Heap_Sort(B,9); printf("/n堆排序后的序列为（完全二叉）：/n"); for(m=1; m<N;m++) { printf(" %d ", B[m]); } printf("/n/n=============================/n/n"); return 0; }

这里写图片描述