首页 > 代码库 > 【数据结构之八大内排序】选择排序(简单选择,堆排序)
【数据结构之八大内排序】选择排序(简单选择,堆排序)
简单选择
不稳定
最差时间:O(n)
平均时间:O(n)
最好时间:O(n)
空间:O(1)
最差时间:O(n)
平均时间:O(n)
最好时间:O(n)
空间:O(1)
#include <stdio.h> #define Swap(x,y,t) ((t)=(x),(x)=(y),(y)=(t)) #define MaxSize 100 typedef struct list { int Size,MaxList; int Elements[MaxSize]; }List; List CreateList(int n,int max) { List ls ; int i ; ls.Size=n; ls.MaxList=max; for(i=0;i<n;i++) { scanf("%d",&ls.Elements[i]); } return ls; } void SelectSort(List *list) { int small,i,j,temp; for(i=0;i<list->Size-1;i++) { small=i; for(j=i+1;j<list->Size;j++) { if(list->Elements[j]<list->Elements[small])small=j; } if(small!=i)Swap(list->Elements[i],list->Elements[small],temp); } } void PrintList(List list) { int i ; for(i=0;i<list.Size;i++) { printf("%d ",list.Elements[i]); } } void main() { int n ,maxList; List list; while(scanf("%d%d",&n,&maxList)!=EOF) { list=CreateList(n,maxList); SelectSort(&list); PrintList(list); } }
堆排序
不稳定
最差时间:O(nlogn)[堆是完全二叉树,向下调整函数AdjustDown的执行时间不超过O(logn),因此建堆最坏时间是O(logn), 运算的最坏时间为 O(n),每输出一个记录都调用一次AjustDown,所以执行时间O(nlogn).]
平均时间:O(nlogn)
最好时间:O(nlogn)
空间:O(1)[只需要一个用于交换两个记录时使用的记录变量temp,而不再需要其他额外的记录空间]
最好时间:O(nlogn)
空间:O(1)[只需要一个用于交换两个记录时使用的记录变量temp,而不再需要其他额外的记录空间]
#include <stdio.h> #define MaxSize 100 #define Swap(x,y,t) ((t)=(x),(x)=(y),(y)=(t)) typedef int T; typedef struct minheap { int Size,MaxHeap; T Elements[MaxSize]; }MinHeap; void AdjustDown(T heap[],int r,int n ) { int child=2*r; T temp=heap[r]; while(child<=n) { if(child<n && heap[child]>heap[child+1])child++; if(temp <= heap[child])break; heap[child/2] = heap[child]; child*=2; } heap[child/2]=temp; } void HeapSort(MinHeap *hp) { int i ; int temp; for(i=hp->Size/2;i>0;i--) { //建堆 AdjustDown(hp->Elements,i,hp->Size); } for(i=hp->Size;i>1;i--) {//选择排序 printf("%d ",hp->Elements[1]); Swap(hp->Elements[1],hp->Elements[i],temp); AdjustDown(hp->Elements,1,i-1); } printf("%d\n",hp->Elements[1]); } //2th Method /* void reaheap(T *heap,int n) { int parent = 0 , end = n , child = 1,right,temp; while(child<end) { right = child +1; if((right<end)&&(heap[right]<heap[child])) { child = right; } if(heap[parent]<heap[child]) break; temp = heap[child]; heap[child]=heap[parent]; heap[parent]=temp; parent = child; child = 2*parent+1; } }*/ MinHeap CreateInitHeap(int n , int max){ int i; MinHeap hp ; hp.Size=n ; //下标从1开始 hp.MaxHeap=max; for (i=1;i<=n;i++ ) { scanf("%d",&hp.Elements[i]); } return hp; } void PrintHeap(MinHeap hp) { int i; for(i=1;i<=hp.Size;i++) { printf("%d ",hp.Elements[i]); } } void main() { int n ,maxHeap; MinHeap hp; while(scanf("%d %d",&n,&maxHeap)) { hp=CreateInitHeap(n,maxHeap); HeapSort(&hp); // PrintHeap(hp); } }
【数据结构之八大内排序】选择排序(简单选择,堆排序)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。