当前位置：首页 -> 基础 -> c++编程基础

c/c++常用算法(10) -- 基本排序算法(选择排序)

2014-11-24 07:16:23 · 作者: · 浏览: 0
标签: c/c 常用 算法 基本 排序 选择

选择排序


选择排序(SelectionSort)的基本思想是：每次从当前待排序的记录中选取关键字最小的记录表，然后与待排序的记录序列中的第一个记录进行交换，直到整个记录序列有序为止。


1.简单选择排序


简单选择排序(Simple Selection Sort，又称为直接选择排序)的基本操作是：通过n-i次关键字间的比较，从n-i+1个记录中选取关键字最小的记录，然后和第i个记录进行交换，i=1,2, …n-1 。


1 .1 排序示例


例：设有关键字序列为：7,4, -2, 19, 13, 6，直接选择排序的过程如下图10-8所示。


\


1.2 算法实例


//选择排序
#include 
  
   
#include 
   
     #define SIZE 10 void SelectionSort(int *a,int len) { int i,j,k,h; int temp; for (i=0; i
    
     
 运行结果如图：
     
 
     
 \
 
 
     

 
 
     
2.堆排序
 
     

 <  http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+PC9wPgo8aDI+Mi4xICC20bXEtqjS5TwvaDI+CjxwPjwvcD4KPHA+PGJyPgo8L3A+CjxwPiAgICAgICAgysduuPbUqsvYtcTQ8sHQSD17azEsIGsyICwgoa1rbn0go6zC+tfjo7o8L3A+CjxwPjxicj4KPC9wPgo8cD48aW1nIHNyYz0="https://www.cppentry.com/upload_files/article/49/1_p8n1k__.jpg" alt="\">
 
 
     

 
 
     
 
     
 由堆的定义知，堆是一棵以k1为根的完全二叉树。若对该二叉树的结点进行编号(从上到下，从左到右)，得到的序列就是将二叉树的结点以顺序结构存放，堆的结构正好和该序列结构完全一致。
 
     

 
 
     
2.2 堆的性质
 
     

 
 
     
 ① 堆是一棵采用顺序存储结构的完全二叉树，k1是根结点；
 
     
 ② 堆的根结点是关键字序列中的最小(或最大)值，分别称为小(或大)根堆；






 
     
 ③ 从根结点到每一叶子结点路径上的元素组成的序列都是按元素值(或关键字值)非递减(或非递增)的；
 ④堆中的任一子树也是堆。 
     
 利用堆顶记录的关键字值最小(或最大)的性质，从当前待排序的记录中依次选取关键字最小(或最大)的记录，就可以实现对数据记录的排序，这种排序方法称为堆排序。
 
     

 
 
     
2.3 堆排序思想
 
     

 
 
     
 ① 对一组待排序的记录，按堆的定义建立堆；
 
     
 ② 将堆顶记录和最后一个记录交换位置，则前n-1个记录是无序的，而最后一个记录是有序的；
 
     
 ③ 堆顶记录被交换后，前n-1个记录不再是堆，需将前n-1个待排序记录重新组织成为一个堆，然后将堆顶记录和倒数第二个记录交换位置，即将整个序列中次小关键字值的记录调整(排除)出无序区；
 
     
 ④ 重复上述步骤，直到全部记录排好序为止。
 
     

 
 结论：排序过程中，若采用小根堆，排序后得到的是非递减序列；若采用大根堆，排序后得到的是非递增序列。
     
 
     
 
     
 
     
4.4 堆的调整――筛选
 
     
 
     

 
 
     
⑴ 堆的调整思想
 
     
 输出堆顶元素之后，以堆中最后一个元素替代之；然后将根结点值与左、右子树的根结点值进行比较，并与其中小者进行交换；重复上述操作，直到是叶子结点或其关键字值小于等于左、右子树的关键字的值，将得到新的堆。称这个从堆顶至叶子的调整过程为“筛选”，如图10-10所示。
 
     
 
     
注意：筛选过程中，根结点的左、右子树都是堆，因此，筛选是从根结点到某个叶子结点的一次调整过程。
 
     

 
 
     \ 
     
 
     
 
     
2.5 代码实现：
 
     

     
//堆排序
#include 
      
       
#include 
       
         #define SIZE 10 void HeapSort(int a[],int n) { int i,j,h,k; int t; for (i = n/2-1; i >= 0; i--) { while (2*i + 1 < n) { j = 2*i + 1; if ((j+1) < n) { if (a[j] < a[j+1]) { j++; } } if (a[i]
        
         0; i--) { t = a[0]; a[0] = a[i]; a[i] = t; k =0; while (2*k+1
         
          运行结果:
          
 
          

 
 
          

 
 
          

 
 
          
参考书籍:《C/C++常用算法手册》 《数据结构-清华大学严蔚敏》