C语言选择排序详解

minoz

选择排序

选择排序(Selection Sort)的基本思想是：每一趟从待排序的记录中选出关键字最小的记录，顺序放在已排好序的子文件的最后，直到全部记录排序完毕。

常用的选择排序方法有简单选择排序和堆排序。

简单选择排序

在介绍选择排序算法前，我们再回顾下冒泡算法。

冒泡算法是通过两两比较，不断交换,逐个推进的方式，来进行排序的。

一次遍历，得到一个最值。

冒泡算法最费时的是什么？

一是两两比较

一是两两交换， 交换要比比较费时多了。

在冒泡算法一篇中，介绍了几种改进方法，那几种改进方法为什么放在冒泡算法中一篇中，而不另一一篇介绍？

原因就是：无论那几种方法怎么改进，都还是基于两两交换不断推进的冒泡算法。从广义上说，都是属于冒泡算法。

那还有没有其它改进的余地呢？

冒泡算法两两交换的目的是什么？-------找出最值。

而通过这种方式取得最值得代价是很大的，因为，每次遍历，可能需要很多次交换才能找到最值，而这些交换都是很浪费时间的。

如果能减少交换次数，同时又能取得最值，那么这就是一种改进。

因此问题便转换为：如何求最值？求最值得方法有几种？

正所谓条条大路通罗马All RoadsLead to Rome，做成一件事的方法不只一种，人生的路也不只一条。

因此，除了使用两两交换的算法找出最值外，或许还有其它方式。

如果有的话，就是通过另外的思路求得最值，于是便跳出了冒泡的思维模式。

好了，大家想想有没有其他的方法遍历一次就可求出最值？

求最值，需要比较，但不一定非得通过不断推进的方式。

那如何能更好的求得最值呢？

很自然的一种想法便是：

每次遍历，只选择最值元素进行交换，这样一次遍历，只需进行一次交换即可，从而避免了其它无价值的交换操作。

如何求得最值元素所在位置呢？

这还得通过遍历比较。

具体方法为：

遍历一次，记录下最值元素所在位置，遍历结束后，将此最值元素调整到合适的位置

这样一次遍历，只需一次交换，便可将最值放置到合适位置

这便是 简单选择排序算法。

[cpp] view plain copy

template

1. void SelectSort(T a[], int len)  
   
2. 
   
3. {  
   
4. 
   
5.     T temp;  
   
6. 
   
7.     int nIndex=0;  
   
8. 
   
9.     //每次循环只进行一次交换 最多进行len-1次循环，因此总体上，比冒泡进行交换的次数少  
   
10. 
    
11.     for (int i=0;i<="" p="" style="box-sizing: border-box;">
    
12. 
    
13.     {  
    
14. 
    
15.         //第i次排序时，已经进行了i次大循环，因此已经排好了i个元素  
    
16. 
    
17.         //已排好序的元素0，,...,i-2,i-1  
    
18. 
    
19.         //    待排元素为i,i+1,...,len-1  
    
20. 
    
21.      nIndex=i;  
    
22. 
    
23.         for (int j=i+1;j<="" p="" style="box-sizing: border-box;">
    
24. 
    
25.         {  
    
26. 
    
27.             if (a[j]<="" p="" style="box-sizing: border-box;">
    
28. 
    
29.             {  
    
30. 
    
31.                 nIndex=j;         
    
32. 
    
33.             }  
    
34. 
    
35.         }  
    
36. 
    
37.         //交换  
    
38. 
    
39.         if (nIndex!=i)  
    
40. 
    
41.         {  
    
42. 
    
43.             temp=a;  
    
44. 
    
45.             a=a[nIndex];  
    
46. 
    
47.             a[nIndex]=temp;  
    
48. 
    
49.         }   
    
50. 
    
51.     }   
    
52. 
    
53. }

复制代码

转自：http://blog.sina.com.cn/s/blog_67a8b77e0102w3n3.html