数据结构 - 简单选择排序(simple selection sort)

?

?

选择排序(selection sort) : 每一趟在n-i+1个记录中选取关键字最小的记录作为有序序列中第i个记录.

?

简单选择排序(simple selection sort) : 通过n-i次关键字之间的比较, 从n-i+1个记录中选出关键字最小的记录, 并和第i个记录交换.

?

选择排序需要比较n(n-1)/2次, 即(n-1)+(n-2)+...+1 = [(n-1)+1](n-1)/2次, 时间复杂度是O(n^2).

?

简单选择排序的主要步骤是: 1. 选出较小元素的位置. 2. 交换.

?

代码:

?

/*
 * SimpleSelectionSort.cpp
 *
 *  Created on: 2014.6.5
 *      Author: Spike
 */

#include 
  
   
#include 
   
     void print(const std::vector
    
     & L) { for (auto i : L) { std::cout << i << ; } std::cout << std::endl; } int SelectMinKey(std::vector
     
      & L, const size_t p) { int min = p; for (size_t i=p+1; i
      
       & L) { for (size_t i=0; i
       
         L = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4}; SelectSort(L); print(L); } 
       
      
     
    
   
  

?

?

4 38 65 97 76 13 27 49 55 49 
4 13 65 97 76 38 27 49 55 49 
4 13 27 97 76 38 65 49 55 49 
4 13 27 38 76 97 65 49 55 49 
4 13 27 38 49 97 65 76 55 49 
4 13 27 38 49 49 65 76 55 97 
4 13 27 38 49 49 55 76 65 97 
4 13 27 38 49 49 55 65 76 97 
4 13 27 38 49 49 55 65 76 97 
4 13 27 38 49 49 55 65 76 97 
4 13 27 38 49 49 55 65 76 97 

?

?

?