每次从序列中找出最大/最小元素,插入已排列部分的最后。
过程:
1、设一个变量min,先放在第一个元素的位置,设i,j,i=0,j=i+1。
2、在未排序数组中找到最小的赋给min,与i比较,开始交换
3、i++ j++
代码展示:
//简单选择排序 #include<stdio.h> void SimpleSelectSort(int arr[],int len) { int tmp=0; int i=0; int j=i+1; int min=i; for(i;i<len-1;i++) { min=i; for(j=i+1;j<len;j++) { if(arr[j]<arr[min]) { min=j; } } if(min!=i) { tmp=arr[min]; arr[min]=arr[i]; arr[i]=tmp; } } } void Print(int arr[],int len) { for(int i=0;i<len;i++) { printf("%d ",arr[i]); } } int main() { int arr[]={1,3,2,4,3,6,8,7,9}; int len=sizeof(arr)/sizeof(arr[0]); SimpleSelectSort(arr,len); Print(arr,len); }
过程:
1、调出大顶堆
从最后一个非叶子节点开始,从下往上调整,比较两个叶子大小,再和父节点比较,取较大的交换。
2、交换顶和最后一个节点,取下最后一个节点,再继续调出大顶堆
代码展示:
//堆排序 #include<stdio.h> //调整大顶堆 void AdjustHeap(int arr[],int pos,int len) { int i=pos; int j=2*i+1; int tmp=0; for(j;j<len;j=2*i+1) { if(j<len-1&&arr[j+1]>arr[j]) ++j; if(arr[i]>=arr[j]) break; tmp=arr[i]; arr[i]=arr[j]; arr[j]=tmp; i=j;//结束条件 } } //调大顶堆,交换顶和最后一个,再调整 void HeapSort(int arr[],int len) { int tmp=0; int i; for(i=len/2-1;i>=0;i--)//i最后一个非叶子结点 { AdjustHeap(arr,i,len);//调大顶堆 } for(i=len-1;i>0;i--) { tmp=arr[0]; arr[0]=arr[i]; arr[i]=tmp; AdjustHeap(arr,0,i); } } void Print(int arr[],int len) { for(int i=0;i<len;i++) { printf("%d ",arr[i]); } } int main() { int arr[]={1,3,2,4,3,6,8,7,9}; int len=sizeof(arr)/sizeof(arr[0]); HeapSort(arr,len); Print(arr,len); }
运行结果: