算法可视化系列——排序算法——选择排序

排序算法可视化系列——篇二“选择排序”

 

选择排序

 

基本思想分析：

同样是我们在书架上将书的顺序从大到小排列好的事情，今天我们采用不同于上

次的插入排序，我们这次使用选择排序。首先我们先分析选择排序的思想，在书架上

有一排高低错落的书，我们需要把这些书排成从低到高的顺序，我们从第一本书的位

置开始，找出这一排书中最矮的，放到第一个位置，将第一本书再放到被取出的那本

书的位置，然后不管第一本书，我们再从第二本书开始，找出剩余书中最矮的，然后

再和第二本书交换位置，以此类推，直到所有的书都有序了，OK!我们的书架整齐了。

这就是选择排序的基本思想。

 

     算法描述：

     //假设是对一个n维整型数组进行排序

     for(进行循环，直到前n-1个元素被排有序){

          for(进行循环，寻找从此刻为止到数组最后一位最小的数){

                   进行大小判断，记录到此刻为止最小的数值及位置索引

          }

          将i位置元素与从i~n最小的元素进行交换

     }

 

    从上面的算法描述可以看出，外层循环会执行n-1次，内层循环会执行n-i次，并且每

次在最坏情况下都会进行2次赋值，那么我们知道总共执行次数

是n + (n - 1) + ... + 2 + 1 + 2 * n = (n^2 + 5n)/2，则我们知道时间复杂度为O(n^2)

 

算法Java语言的简单实现:

 

 

/**
* 选择排序的Java简单实现
* 排序目标是整形数组
*/

public void selectSort(int[] a){
	/**
	* 外部循环，只需要到a.length - 1，因为当
	* 前n-1个元素排好序时，最后一个必然有序
	*/
	for(int i = 0; i < a.length - 1; i++){
		/**
		* 用于记录当前位置元素，以及索引
		* 用于存储从i~n最小元素的值与索引
		*/
		int temp_data = a[i];
		int index = i;

		/** 
		* 循环找出从i~n的的最小元素及索引
		*/
		for(int j = i; j < a.length; j++){
			if(a[j] < temp_data){
				temp_data = a[j];
				index = j;
			}
		}

		/**
		* 元素进行交换
		*/
		a[j] = a[i];
		a[i] = temp_data;
	}
}

 

上面是对选择排序的一个基本实现，主要是用来体会选择排序的基本思想，下面是关于选择排序的动态演示，具体如下：

 

一、 排序中......

 二、 排序中和后面最矮的交换......

 三、排好序......

 程序源代码附加在下（只是其中实现选择排序的一部分，其余在上一个已经给出）：

 

评论

1 楼 消失的气泡 2013-05-23  

a[j] = a[i];  
a[i] = temp_data;

博主，这个应该是

a[index] = a[i];  
a[i] = temp_data;

，这里已经出循环了，那个j应该属于未定义的变量~
就算j在前边定义了，循环结束后，j跟index也不一定是相等的