欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

算法之路__2、选择排序

程序员文章站 2022-05-12 21:33:46
...

一、解释

选择排序法事实上 是对 定位比较交换法(也就是冒泡排序法) 的一种改进。

基本思想:第1趟,在待排序记录r[1]~r[n]中选出最小的记录,将它与r[1]交换;第2趟,在待排序记录r[2]~r[n]中选出最小的记录,将它与r[2]交换;以此类推,第i趟在待排序记录r[i]~r[n]中选出最小的记录,将它与r[i]交换,使有序序列不断增长直到全部排序完毕。

从以上的 算法思想中可以看出,选择排序是选待排记录中最小的一个放在左侧, 而上一篇博文中写到的冒泡是从待排记录中选择最大的放在右侧。

示例:

初始序列:{49 27 65 97 76 12 38}
  第1趟:12与49交换:12{27 65 97 76 49 38}
  第2趟:27不动 :12 27{65 97 76 49 38}
  第3趟:65与38交换:12 27 38{97 76 49 65}
  第4趟:97与49交换:12 27 38 49{76 97 65}
  第5趟:76与65交换:12 27 38 49 65{97 76}
  第6趟:97与76交换:12 27 38 49 65 76 97 完成

二、代码

	public static void selectionSort(int[] arr) {
		if (arr == null || arr.length < 2) {
			return;
		}
		//确定待排区域
		for (int i = 0; i < arr.length - 1; i++) {
			//指针变量minIndex 表示最小元素下标 以当前位置开始
			int minIndex = i;
			//从当前位置的下一个开始遍历 
			//比minIndex位置元素小则 将小位置元素下标设置为minIndex
			for (int j = i + 1; j < arr.length; j++) {
				minIndex = arr[j] < arr[minIndex] ? j : minIndex;
			}
			//将当前位置元素与最小位置元素交换
        		int tmp = arr[i];
        		arr[i] = arr[minIndex];
        		arr[minIndex] = tmp;
		}
	}

 

相关标签: 选择排序