专注细节
努力进步

选择排序

选择排序

选择排序的基本思想是每次从待排序的数据元素集合中选取关键字最小(最大)的数据元素放到数据元素集合的最前(或最后),数据元素不断缩小,当数据元素集合为空时选择排序结束。常用的选择排序有直接选择排序和堆排序两种。

1,直接选择排序

直接选择排序:每次从待排序中选择最小的放到最前面,如下图

2,堆排序

在直接选择排序中,待排序的数据元素集合构成一个线性表结构,要从n个数据元素的线性表中选择一个最小的元素需要n-1次,如果能把待排序的数据集合构成一个完全二叉树结构,则每次选择最大或者最小的元素只需要log2 N,所以排序算法的时间复杂度就会变为O(nlog2 n)。这就是堆排序的思想。

a什么是最大堆、最小堆?

最大堆定义:假设数组a中存放了n个数据元素,数组下标从0开始,当数组下标2i+1<n,有a[i]>=a[2*i+1]且a[i]>=a[2*j+2]。同理最小堆也这样定义!!!

B创建堆

 从数据下标i=(n-1)/2,即最后一个有叶子节点的点,从这个点开始进行子树的更新,更新完成后i–,进行下一个子树的更新,一次直到i=0,即可创建一个最大(最小)堆

C取出堆顶元素

比如取出第一个堆顶元素,在数组中,即与数组最后元素交换;但是之后0~n-1被破坏了最大堆结构,但是很显然不需要再从最后一个有叶子节点的节点开始更新来创建堆,因为此时,只是堆顶元素被取出,后面基本的结果完全可以保持不变,故,只需更新一次,更新时,起始点为0即可


#include
using namespace std;
#define DataType int
/*创建堆从数据下标i=(n-1)/2,即最后一个有叶子节点的点,从这个点开始进行子树的
更新,更新完成后i--,进行下一个子树的更新,一次直到i=0,即可创建一个最大(最小)堆*/
void CreateHeap(DataType a[],int n, int h){
int i,j,flag;
DataType temp;

i=h;
j=2*i+1;
temp=a[i];
flag=0;
while(j<n&&flag!=1){
if(j<n-1&&a[j]a[j])
flag=1;
else{
a[i]=a[j];
i=j;
j=2*i+1;
}
}
a[i]=temp;
}

void InitCreateHeap(DataType a[], int n){
for(int i=(n-1)/2;i>=0;i–)
CreateHeap(a,n,i);
}

void display(DataType* a,int n){
for(int i=0;i<n;i++){
cout<<a[i]<<” “; } } DataType* HeapSort(DataType a[], int n){ int i; DataType temp; InitCreateHeap(a,n); for(i=n-1;i>0;i–){
temp=a[0];
a[0]=a[i];
a[i]=temp;
// 每次取出最大值后,将堆更新为最大堆
display(a,n);
//比如取出第一个堆顶元素,在数组中,即与数组最后元素交换;
//但是之后0~n-1被破坏了最大堆结构,但是很显然不需要再从最
//后一个有叶子节点的节点开始更新来创建堆,因为此时,只是堆
//顶元素被取出,后面基本的结果完全可以保持不变,故,只需更
//新一次,更新时,起始点为0即可
CreateHeap(a,i,0);
}
return a;
}

int main(){
DataType a[]={8,64,2,20,34,54,23,54,14,98};
DataType* aa= HeapSort(a,sizeof(a)/sizeof(int));
display(aa,sizeof(a)/sizeof(DataType));
}

 

分享到:更多 ()