0


前面在介绍冒泡排序的时候,有提到一种简单排序算法,就是从0开始,每次确定一个位置的元素。假设当前需要确定的位置下标为

i,则将i处的元素与后面的元素逐个比较,并将每次比较结果中较小的元素存放在i处,从而保证i处一直保存着最小元素。


简单的选择排序算法与这种算法思路一样,但是选择排序在比较的过程中,并没有将比较结果存放在i处,而是保存每次比较结果中

较小元素的下标到min中,从而保证min永远指向较小元素,最后将min处元素与i处元素交换。从这里可以看出,选择排序是一种

不稳定的排序。以图来表示:




第一轮确定的是下标为0的位置元素,一轮比较下来,最小元素的下标是min = 1,因此,将min处元素与0处元素互换。


以此类推。


将这个过程量化:假设有n个元素,需要确定的下标有0到n-1。最后一个元素无需比较。假设当前需要确定的下标为i,则将min初

始化为i,然后将min处的元素依次与后面n-1-i个元素相比较,min每次指向较小元素。

代买如下:

  1. void SelectSort(int array[], int arrayCount)  
  2. {  
  3.     int min;  
  4.     for(int i = 0; i < arrayCount - 1; ++i)  
  5.     {  
  6.         min = i;  
  7.         for(int j = i + 1; j < arrayCount; ++j)  
  8.         {  
  9.             if(array[j] < array[min])  //使得min总是指向最小元素  
  10.                 min = j;  
  11.         }  
  12.         if(min != i)  //即min有移动过  
  13.         {  
  14.             int temp = array[i];  
  15.             array[i] = array[min];  
  16.             array[min] = temp;  
  17.         }  
  18.     }     
  19. }  


选择排序与前面的简单排序算法思路一模一样,不同的地方在于,在寻找最小元素的时候,前者是每次都将最小元素存放到目的

地,而后者则只是暂时存放一下其地址,到最后的时候才需要交换。因此,后者省略了很多的交换操作,更优。


转自:http://blog.csdn.net/hulifangjiayou/article/details/47321309

关闭 返回顶部
联系我们
Copyright © 2011. 聚财吧. All rights reserved.