净水器压力桶打气视频:【排序结构3】 选择排序
来源:百度文库 编辑:中财网 时间:2024/04/29 05:58:32
(1) 简单选择排序 O(N^2)
一趟简单选择排序的操作为:通过n-i 次关键字间的比较,从n-i+1 个记录中选择出关键字最小的记录,并和第 i (i<=i<=n)个记录交换之。
Cpp代码- #include
- /***************************************
- * 简单选择排序 Simple Selection Sort *
- ***************************************/
- class SimpleSelectSort{
- public:
- //递增排序
- static void inc_sort(int keys[],int size);
- };
- void SimpleSelectSort :: inc_sort(int keys[], int size){
- for(int i=0;i
- int min_key=keys[i]; //存储每一趟排序的最小值
- int min_key_pos=i; //存储最小值的位置
- for(int j=i+1;j
- if(min_key>keys[j]){ //定位最小值
- min_key=keys[j];
- min_key_pos=j;
- }
- }
- keys[min_key_pos]=keys[i]; //将选择的最小值交换位置
- keys[i]=min_key;
- }
- for(int k=0;k
- cout<
- cout<
- }
- //Test SimpleSelectSort
- void main(){
- int raw[]={49,38,65,97,76,13,27,49};
- int size=sizeof(raw)/sizeof(int);
- SimpleSelectSort::inc_sort(raw,size);
- }
#include/*************************************** * 简单选择排序 Simple Selection Sort * ***************************************/ class SimpleSelectSort{public://递增排序static void inc_sort(int keys[],int size);};void SimpleSelectSort :: inc_sort(int keys[], int size){for(int i=0;i keys[j]){ //定位最小值min_key=keys[j];min_key_pos=j;}}keys[min_key_pos]=keys[i]; //将选择的最小值交换位置keys[i]=min_key;}for(int k=0;k 简单选择排序的时间复杂度为O(N^2),空间复杂度为O(1),排序方法是稳定的。这种排序方法在n个关键字中选出最小值,至少进行n-1次比较,然而,继续在剩余的n-1个关键字中选择次小值就并非一定要进行n-2次比较了。下面的树形选择排序后一轮比较可以利用前一轮的比较结果,从而大大减少比较的次数。
(2) 树形选择排序 O(N * logN)
树形选择排序(Tree Selection Sort),又称竞标赛排序(Tournament Sort),是一种按照竞标赛思想进行的选择排序方法。首先对n个记录的关键字两两比较,然后在其中[n/2]个较小者之间在进行两两比较,如此重复,直至选出最小关键字的记录为止。这个过程可用一颗有n个叶子结点的完全二叉树表示。 下图展示了树形选择排序的过程:
(a)图选择出最小值13需要7次比较,但是(b)图选择第二小的27就只需要3次了。应为(a)图中的最小值13已经找到,只需要在(b)图中将13的位置赋值为无穷大,这样,就只需要再次比较树的一部分就可以找到第二小的值。Java代码
- #include
- #include
- #define MAX_INT 32767;
- typedef struct sort_node{
- int key; //待排关键字
- int pos; //此关键字在待排序列中的位置
- }SortNode;
- int level=1;
- SortNode **level_point;
- //记录每一层的关键字容量的连续空间
- int *level_count;
- //记录已经排序号的关键字序列
- int *sorted_keys;
- //释放多维指针
- void freeAll(SortNode ** deleted, int size){
- for(int i=0;i
- free(deleted[i]);
- }
- //递增排序
- void inc_sort(int keys[],int size){
- //开辟存储排序序列的容量
- sorted_keys=(int *)malloc(size*sizeof(int));
- //根据待排序列的数量确定排序树的层次
- int a_size=size;
- bool isPower=true;
- if(a_size>1){
- while(a_size!=1){
- if(a_size%2==1)
- isPower=false;
- level++;
- a_size/=2;
- }
- }
- if(isPower==false) level++;
- //够着排序树的内存结构,为每一层开辟可以容纳一定数量关键字的内存空间
- level_point=(SortNode **)malloc(level*sizeof(SortNode *));
- level_count=(int *)malloc(level*sizeof(int));
- int level_size=size;
- for(int l=0;l
- level_count[l]=level_size;
- level_point[l]=(SortNode *)malloc(level_size*sizeof(SortNode));
- level_size=level_size/2+level_size%2;
- }
- //为第0层赋值待排序列,并建立排序树,找到第一次最小的关键字
- for(int i=0;i
- level_point[0][i].key=keys[i];
- level_point[0][i].pos=i;
- }
- int cur_level=1;
- while(cur_level
- for(int j=0;j
- int left_child=level_point[cur_level-1][j*2].key;
- //没有右孩子
- if((j*2+1)>=level_count[cur_level-1]){
- level_point[cur_level][j].key=left_child;
- level_point[cur_level][j].pos=level_point[cur_level-1][j*2].pos;
- }else{
- int right_child=level_point[cur_level-1][j*2+1].key;
- level_point[cur_level][j].key=left_child<=right_child ? left_child : right_child;
- level_point[cur_level][j].pos=left_child<=right_child ? level_point[cur_level-1][j*2].pos : level_point[cur_level-1][j*2+1].pos;
- }
- }
- cur_level++;
- }
- //打印第一次的树形选择排序:
- cout<<"第1次树形选择排序 (关键字 - 关键字在待排表中的位置):"<
- for(int u=level-1;u>=0;u--){
- for(int i=0;i
- cout<<"("<
- cout<
- }
- //第一次树形排序的最小值和最小位置
- int cur_min_key=level_point[level-1][0].key;
- int cur_min_pos=level_point[level-1][0].pos;
- sorted_keys[0]=cur_min_key;
- //输出剩下size-1个最小的数
- for(int count=1;count<=size-1;count++){
- level_point[0][cur_min_pos].key=MAX_INT;
- //找到需要重新比较的两个位置
- int a_pos=cur_min_pos;
- int b_pos=a_pos%2==0 ? a_pos+1 : a_pos-1;
- for(int m=1;m
- if(b_pos>=level_count[m-1]){
- level_point[m][a_pos/2].key=level_point[m-1][a_pos].key;
- level_point[m][a_pos/2].pos=level_point[m-1][a_pos].pos;
- }else{
- level_point[m][a_pos/2].key=level_point[m-1][a_pos].key<=level_point[m-1][b_pos].key ? level_point[m-1][a_pos].key : level_point[m-1][b_pos].key;
- level_point[m][a_pos/2].pos=level_point[m-1][a_pos].key<=level_point[m-1][b_pos].key ? level_point[m-1][a_pos].pos : level_point[m-1][b_pos].pos;
- }
- a_pos=a_pos/2;
- b_pos=a_pos%2==0 ? a_pos+1 : a_pos-1;
- }
- //记录每一次树形排序的最小值和对应的位置
- cur_min_key=level_point[level-1][0].key;
- cur_min_pos=level_point[level-1][0].pos;
- sorted_keys[count]=cur_min_key;
- //打印第count次的树形选择排序:
- cout<<"第"<<(count+1)<<"次树形选择排序 (关键字 - 关键字在待排表中的位置):"<
- for(int u=level-1;u>=0;u--){
- for(int i=0;i
- cout<<"("<
- cout<
- }
- }
- //打印排序好的序列
- cout<
- for(int k=0;k
- cout<
- cout<
- free(level_count);
- free(sorted_keys);
- freeAll(level_point,level);
- }
- //Test
- void main(){
- int raw[]={49,38,65,97,76,13,27,49};
- int size=sizeof(raw)/sizeof(int);
- inc_sort(raw,size);
- }
#include#include #define MAX_INT 32767;typedef struct sort_node{int key; //待排关键字int pos; //此关键字在待排序列中的位置}SortNode;int level=1;SortNode **level_point;//记录每一层的关键字容量的连续空间int *level_count;//记录已经排序号的关键字序列int *sorted_keys;//释放多维指针void freeAll(SortNode ** deleted, int size){for(int i=0;i 1){while(a_size!=1){if(a_size%2==1)isPower=false;level++;a_size/=2;}}if(isPower==false) level++;//够着排序树的内存结构,为每一层开辟可以容纳一定数量关键字的内存空间level_point=(SortNode **)malloc(level*sizeof(SortNode *));level_count=(int *)malloc(level*sizeof(int));int level_size=size;for(int l=0;l =level_count[cur_level-1]){level_point[cur_level][j].key=left_child;level_point[cur_level][j].pos=level_point[cur_level-1][j*2].pos;}else{int right_child=level_point[cur_level-1][j*2+1].key;level_point[cur_level][j].key=left_child<=right_child ? left_child : right_child;level_point[cur_level][j].pos=left_child<=right_child ? level_point[cur_level-1][j*2].pos : level_point[cur_level-1][j*2+1].pos;}}cur_level++;}//打印第一次的树形选择排序:cout<<"第1次树形选择排序 (关键字 - 关键字在待排表中的位置):"< =0;u--){for(int i=0;i =level_count[m-1]){level_point[m][a_pos/2].key=level_point[m-1][a_pos].key;level_point[m][a_pos/2].pos=level_point[m-1][a_pos].pos;}else{level_point[m][a_pos/2].key=level_point[m-1][a_pos].key<=level_point[m-1][b_pos].key ? level_point[m-1][a_pos].key : level_point[m-1][b_pos].key;level_point[m][a_pos/2].pos=level_point[m-1][a_pos].key<=level_point[m-1][b_pos].key ? level_point[m-1][a_pos].pos : level_point[m-1][b_pos].pos;}a_pos=a_pos/2;b_pos=a_pos%2==0 ? a_pos+1 : a_pos-1;}//记录每一次树形排序的最小值和对应的位置cur_min_key=level_point[level-1][0].key;cur_min_pos=level_point[level-1][0].pos;sorted_keys[count]=cur_min_key;//打印第count次的树形选择排序:cout<<"第"<<(count+1)<<"次树形选择排序 (关键字 - 关键字在待排表中的位置):"< =0;u--){for(int i=0;i 树形选择排序需要建立一棵含n个叶子结点的完全二叉树,其深度为[logN]+1。因此,除第一次排序需要比较n次以外,其余每一次树形选择排序都只需要比较logN次。因此树形选择排序的时间复杂度为O(N*logN)。但是这种排序方法大量额外的空间,一棵n个叶子结点的满二叉树有2n-1个结点。则对N个关键字的树形选择排序需要近2N左右的结点。空间复杂度为O(2N)。该方法也是稳定的排序。
树形选择排序仍然有很多缺点,比如空间代价高,需要和无穷大关键字做比较等。为了弥补,J.willioms在1964年提出了下面的另一种选择排序——堆排序。
(3) 堆排序
堆的定义如如下:n个元素的序列{K0 ... K(n-1)},当且仅当满足下关系时,称之为堆。(注: 序列从下标0作为第一个元素开始)
ki <= k(2i+1) && ki <= k(2i+2) —— 小顶堆
ki >= k(2i+1) && ki >= k(2i+2) —— 大顶堆
若将此序列对应的一维数组(序列的内存结构)看成是一个完全二叉树,即Ki 的左孩子是K(2i+1),右孩子是K(2i+2)。则堆的含义就是,完全二叉树中所有非终结点的值均不大于(不小于)其左、右孩子结点的值。因此,堆顶元素K0就是整个序列的最小值了。
堆排序的算法流程:
首先,将待排序列整理成堆。即从序列的第[n/2]-1个元素(完全二叉树最后一个非终结点)开始,到第0个结点为止调整堆。具体过程见下图:
然后,输出堆顶元素K0后,用当前堆中最后一个元素K(n-1)代替堆顶。并将待排序列减少一个(最后一个元素已经移到了第0号位置),接着调整堆,即将移动后的堆顶元素向下调整(保证小顶堆)。具体过程如下图:
最后,依次循环下去,直到输出序列的全部元素为止。Java代码
- #include
- /*********************
- * 堆排序 Heap Sort *
- *********************/
- class HeapSort{
- public:
- //递增排序
- static void inc_sort(int keys[], int size);
- private:
- //创建堆
- static void create(int keys[],int size);
- //调整堆
- static void adjust(int keys[],int var_size);
- //交换
- static void swap(int keys[],int pos_a,int pos_b);
- };
- //创建堆
- void HeapSort :: create(int keys[],int size){
- for(int i=(size-1)/2;i>=0;i--){
- int lchild=i*2+1;
- int rchild=i*2+2;
- while(lchild
- int next_pos=-1;
- if(rchild>=size&&keys[i]>keys[lchild]){
- HeapSort ::swap(keys,i,lchild);
- next_pos=lchild;
- }
- if(rchild
- int min_temp=keys[lchild]<=keys[rchild] ? keys[lchild] : keys[rchild];
- int min_pos=keys[lchild]<=keys[rchild] ? lchild : rchild;
- if(keys[i]>keys[min_pos]){
- swap(keys,i,min_pos);
- next_pos=min_pos;
- }
- }
- if(next_pos==-1) break;
- lchild=next_pos*2+1;
- rchild=next_pos*2+2;
- }
- }
- }
- //调整堆
- void HeapSort :: adjust(int keys[],int var_size){
- int pos=0;
- while((pos*2+1)
- int next_pos=-1;
- if((pos*2+2)>=var_size&&keys[pos]>keys[pos*2+1]){
- swap(keys,pos,pos*2+1);
- next_pos=pos*2+1;
- }
- if((pos*2+2)
- int min_keys=keys[pos*2+1]<=keys[pos*2+2] ? keys[pos*2+1] : keys[pos*2+2];
- int min_pos=keys[pos*2+1]<=keys[pos*2+2] ? (pos*2+1) : (pos*2+2);
- if(keys[pos]>min_keys){
- swap(keys,pos,min_pos);
- next_pos=min_pos;
- }
- }
- if(next_pos==-1) break;
- pos=next_pos;
- }
- }
- //递增排序
- void HeapSort :: inc_sort(int keys[], int size){
- HeapSort::create(keys,size);
- int var_size=size;
- while(var_size>0){
- cout<
- keys[0]=keys[var_size-1];
- --var_size;
- adjust(keys,var_size);
- }
- }
- //keys[pos_a] <-> keys[pos_b]
- void HeapSort :: swap(int keys[],int pos_a,int pos_b){
- int temp=keys[pos_a];
- keys[pos_a]=keys[pos_b];
- keys[pos_b]=temp;
- }
- //Test HeapSort
- void main(){
- int raw[]={49,38,65,97,76,13,27,49};
- int size=sizeof(raw)/sizeof(int);
- HeapSort::inc_sort(raw,size);
- }
#include/********************* * 堆排序 Heap Sort * *********************/ class HeapSort{public://递增排序static void inc_sort(int keys[], int size);private://创建堆static void create(int keys[],int size);//调整堆static void adjust(int keys[],int var_size);//交换static void swap(int keys[],int pos_a,int pos_b);};//创建堆void HeapSort :: create(int keys[],int size){for(int i=(size-1)/2;i>=0;i--){int lchild=i*2+1;int rchild=i*2+2;while(lchild =size&&keys[i]>keys[lchild]){HeapSort ::swap(keys,i,lchild);next_pos=lchild;}if(rchild keys[min_pos]){swap(keys,i,min_pos);next_pos=min_pos;}}if(next_pos==-1) break;lchild=next_pos*2+1;rchild=next_pos*2+2;}}}//调整堆void HeapSort :: adjust(int keys[],int var_size){int pos=0;while((pos*2+1) =var_size&&keys[pos]>keys[pos*2+1]){swap(keys,pos,pos*2+1);next_pos=pos*2+1;}if((pos*2+2) min_keys){swap(keys,pos,min_pos);next_pos=min_pos;}}if(next_pos==-1) break;pos=next_pos;}}//递增排序void HeapSort :: inc_sort(int keys[], int size){HeapSort::create(keys,size);int var_size=size;while(var_size>0){cout< keys[pos_b]void HeapSort :: swap(int keys[],int pos_a,int pos_b){int temp=keys[pos_a];keys[pos_a]=keys[pos_b];keys[pos_b]=temp;}//Test HeapSortvoid main(){int raw[]={49,38,65,97,76,13,27,49}; int size=sizeof(raw)/sizeof(int); HeapSort::inc_sort(raw,size); } 堆排序方法对记录较少的文件效果一般,但对于记录较多的文件还是很有效的。其运行时间主要耗费在创建堆和反复调整堆上。堆排序即使在最坏情况下,其时间复杂度也为O(N*logN)。这一点比快速排序要好。另外,堆排序所需要的空间复杂度为O(1)。但却是不稳定排序。