净水器压力桶打气视频:【排序结构3】 选择排序

来源：百度文库 编辑：中财网 时间：2024/05/14 19:57:22

(1) 简单选择排序 O(N^2)

一趟简单选择排序的操作为：通过n-i 次关键字间的比较，从n-i+1 个记录中选择出关键字最小的记录，并和第 i (i<=i<=n)个记录交换之。

Cpp代码
  1. #include
  2. /***************************************
  3. * 简单选择排序 Simple Selection Sort *
  4. ***************************************/
  5. class SimpleSelectSort{
  6. public:
  7. //递增排序
  8. static void inc_sort(int keys[],int size);
  9. };
  10. void SimpleSelectSort :: inc_sort(int keys[], int size){
  11. for(int i=0;i
  12. int min_key=keys[i]; //存储每一趟排序的最小值
  13. int min_key_pos=i; //存储最小值的位置
  14. for(int j=i+1;j
  15. if(min_key>keys[j]){ //定位最小值
  16. min_key=keys[j];
  17. min_key_pos=j;
  18. }
  19. }
  20. keys[min_key_pos]=keys[i]; //将选择的最小值交换位置
  21. keys[i]=min_key;
  22. }
  23. for(int k=0;k
  24. cout<
  25. cout<
  26. }
  27. //Test SimpleSelectSort
  28. void main(){
  29. int raw[]={49,38,65,97,76,13,27,49};
  30. int size=sizeof(raw)/sizeof(int);
  31. SimpleSelectSort::inc_sort(raw,size);
  32. } 
#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;ikeys[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代码 
  1. #include 
  2. #include 
  3. #define MAX_INT 32767; 
  5. typedef struct sort_node{ 
  6. int key; //待排关键字 
  7. int pos; //此关键字在待排序列中的位置 
  8. }SortNode; 
  10. int level=1; 
  11. SortNode **level_point; 
  12. //记录每一层的关键字容量的连续空间 
  13. int *level_count; 
  14. //记录已经排序号的关键字序列 
  15. int *sorted_keys; 
  17. //释放多维指针 
  18. void freeAll(SortNode ** deleted, int size){ 
  19. for(int i=0;i
  20. free(deleted[i]); 
  21. } 
  22. //递增排序 
  23. void inc_sort(int keys[],int size){ 
  25. //开辟存储排序序列的容量 
  26. sorted_keys=(int *)malloc(size*sizeof(int)); 
  28. //根据待排序列的数量确定排序树的层次 
  29. int a_size=size; 
  30. bool isPower=true; 
  31. if(a_size>1){ 
  32. while(a_size!=1){ 
  33. if(a_size%2==1) 
  34. isPower=false; 
  35. level++; 
  36. a_size/=2; 
  37. } 
  38. } 
  39. if(isPower==false) level++; 
  41. //够着排序树的内存结构，为每一层开辟可以容纳一定数量关键字的内存空间 
  42. level_point=(SortNode **)malloc(level*sizeof(SortNode *)); 
  43. level_count=(int *)malloc(level*sizeof(int)); 
  44. int level_size=size; 
  45. for(int l=0;l
  46. level_count[l]=level_size; 
  47. level_point[l]=(SortNode *)malloc(level_size*sizeof(SortNode)); 
  48. level_size=level_size/2+level_size%2; 
  49. } 
  51. //为第0层赋值待排序列，并建立排序树，找到第一次最小的关键字 
  52. for(int i=0;i
  53. level_point[0][i].key=keys[i]; 
  54. level_point[0][i].pos=i; 
  55. } 
  56. int cur_level=1; 
  57. while(cur_level
  58. for(int j=0;j
  59. int left_child=level_point[cur_level-1][j*2].key; 
  60. //没有右孩子 
  61. if((j*2+1)>=level_count[cur_level-1]){ 
  62. level_point[cur_level][j].key=left_child; 
  63. level_point[cur_level][j].pos=level_point[cur_level-1][j*2].pos; 
  64. }else{ 
  65. int right_child=level_point[cur_level-1][j*2+1].key; 
  66. level_point[cur_level][j].key=left_child<=right_child ? left_child : right_child; 
  67. 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; 
  68. } 
  69. } 
  70. cur_level++; 
  71. } 
  73. //打印第一次的树形选择排序： 
  74. cout<<"第1次树形选择排序 (关键字 - 关键字在待排表中的位置)："<
  75. for(int u=level-1;u>=0;u--){ 
  76. for(int i=0;i
  77. cout<<"("<
  78. cout<
  79. } 
  81. //第一次树形排序的最小值和最小位置 
  82. int cur_min_key=level_point[level-1][0].key; 
  83. int cur_min_pos=level_point[level-1][0].pos; 
  84. sorted_keys[0]=cur_min_key; 
  86. //输出剩下size-1个最小的数 
  87. for(int count=1;count<=size-1;count++){ 
  88. level_point[0][cur_min_pos].key=MAX_INT; 
  90. //找到需要重新比较的两个位置 
  91. int a_pos=cur_min_pos; 
  92. int b_pos=a_pos%2==0 ? a_pos+1 : a_pos-1; 
  94. for(int m=1;m
  95. if(b_pos>=level_count[m-1]){ 
  96. level_point[m][a_pos/2].key=level_point[m-1][a_pos].key; 
  97. level_point[m][a_pos/2].pos=level_point[m-1][a_pos].pos; 
  98. }else{ 
  99. 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; 
  100. 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; 
  101. } 
  102. a_pos=a_pos/2; 
  103. b_pos=a_pos%2==0 ? a_pos+1 : a_pos-1; 
  104. } 
  105. //记录每一次树形排序的最小值和对应的位置 
  106. cur_min_key=level_point[level-1][0].key; 
  107. cur_min_pos=level_point[level-1][0].pos; 
  108. sorted_keys[count]=cur_min_key; 
  110. //打印第count次的树形选择排序： 
  111. cout<<"第"<<(count+1)<<"次树形选择排序 (关键字 - 关键字在待排表中的位置)："<
  112. for(int u=level-1;u>=0;u--){ 
  113. for(int i=0;i
  114. cout<<"("<
  115. cout<
  116. } 
  117. } 
  119. //打印排序好的序列 
  120. cout<
  121. for(int k=0;k
  122. cout<
  123. cout<
  125. free(level_count); 
  126. free(sorted_keys); 
  127. freeAll(level_point,level); 
  128. } 
  129. //Test 
  130. void main(){ 
  131. int raw[]={49,38,65,97,76,13,27,49}; 
  132. int size=sizeof(raw)/sizeof(int); 
  133. inc_sort(raw,size); 
  135. } 
#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;i1){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代码    
  1. #include 
  2. /********************* 
  3. * 堆排序 Heap Sort * 
  4. *********************/ 
  5. class HeapSort{ 
  6. public: 
  7. //递增排序 
  8. static void inc_sort(int keys[], int size); 
  9. private: 
  10. //创建堆 
  11. static void create(int keys[],int size); 
  12. //调整堆 
  13. static void adjust(int keys[],int var_size); 
  14. //交换 
  15. static void swap(int keys[],int pos_a,int pos_b); 
  16. }; 
  17. //创建堆 
  18. void HeapSort :: create(int keys[],int size){ 
  19. for(int i=(size-1)/2;i>=0;i--){ 
  20. int lchild=i*2+1; 
  21. int rchild=i*2+2; 
  22. while(lchild
  24. int next_pos=-1; 
  25. if(rchild>=size&&keys[i]>keys[lchild]){ 
  26. HeapSort ::swap(keys,i,lchild); 
  27. next_pos=lchild; 
  28. } 
  29. if(rchild
  30. int min_temp=keys[lchild]<=keys[rchild] ? keys[lchild] : keys[rchild]; 
  31. int min_pos=keys[lchild]<=keys[rchild] ? lchild : rchild; 
  32. if(keys[i]>keys[min_pos]){ 
  33. swap(keys,i,min_pos); 
  34. next_pos=min_pos; 
  35. } 
  36. } 
  37. if(next_pos==-1) break; 
  38. lchild=next_pos*2+1; 
  39. rchild=next_pos*2+2; 
  40. } 
  41. } 
  42. } 
  43. //调整堆 
  44. void HeapSort :: adjust(int keys[],int var_size){ 
  46. int pos=0; 
  47. while((pos*2+1)
  48. int next_pos=-1; 
  49. if((pos*2+2)>=var_size&&keys[pos]>keys[pos*2+1]){ 
  50. swap(keys,pos,pos*2+1); 
  51. next_pos=pos*2+1; 
  52. } 
  53. if((pos*2+2)
  54. int min_keys=keys[pos*2+1]<=keys[pos*2+2] ? keys[pos*2+1] : keys[pos*2+2]; 
  55. int min_pos=keys[pos*2+1]<=keys[pos*2+2] ? (pos*2+1) : (pos*2+2); 
  56. if(keys[pos]>min_keys){ 
  57. swap(keys,pos,min_pos); 
  58. next_pos=min_pos; 
  59. } 
  60. } 
  61. if(next_pos==-1) break; 
  62. pos=next_pos; 
  63. } 
  64. } 
  65. //递增排序 
  66. void HeapSort :: inc_sort(int keys[], int size){ 
  67. HeapSort::create(keys,size); 
  68. int var_size=size; 
  69. while(var_size>0){ 
  70. cout<
  71. keys[0]=keys[var_size-1]; 
  72. --var_size; 
  73. adjust(keys,var_size); 
  74. } 
  75. } 
  76. //keys[pos_a] <-> keys[pos_b] 
  77. void HeapSort :: swap(int keys[],int pos_a,int pos_b){ 
  78. int temp=keys[pos_a]; 
  79. keys[pos_a]=keys[pos_b]; 
  80. keys[pos_b]=temp; 
  81. } 
  82. //Test HeapSort 
  83. void main(){ 
  84. int raw[]={49,38,65,97,76,13,27,49}; 
  85. int size=sizeof(raw)/sizeof(int); 
  86. HeapSort::inc_sort(raw,size); 
  87. } 
#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(rchildkeys[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)。但却是不稳定排序。
选择排序 结构体排序算法 排序。。。。。。。。 直接选择排序 vb选择排序算法 pascal直接选择排序 气泡排序和选择排序用链表实现 怎么对结构体排序 选择法 冒泡法 排序 用选择排序法对10个整数排序 冒泡排序与选择选排序有什么样不同 请问冒泡排序和选择排序哪个效率更高? 3忍强弱排序 二级C公共基础题中的插入排序,选择排序,快速排序,归并排序各有什么特点，具体是怎么回事？ 谁会对C++中的排序算法,比如冒泡排序,插入排序,选择排序,快速排序等的MPI并行实现代码? 3列数字排序问题 关于C语言结构体数据排序问题 请问下述算法是属于选择排序还是冒泡排序，有什么依据吗？ 在excel中排序时，被排序的区域是如何选择的？？ vb中选择排序和冒泡排序的最根本的区别是什么? 排序问题! 输入法排序 冒泡排序 英语排序