数据结构 - 只需选择排序(simple selection sort)

本文地址: http://blog.csdn.net/caroline_wendy/article/details/28601965

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

简单选择排序(simple selection sort) : 通过n-i次keyword之间的比較, 从n-i+1个记录中选出keyword最小的记录, 并和第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