选择排序(Selection Sort )分为两种 简单选择排序(Simple Selection Sort) 和树形选择排序。
简单选择排序(Simple Selection Sort):
简单选择排序类似于冒泡排序(Bubble Sort) ,每次都会在剩下的元素集合中选择出一个最值出来填充到当前位置。唯一的区别是,冒泡排序在每次发现比当前值小于(或大于)时,都会交换元素的位置, 而 简单选择排序是选择剩余元素中的最值和当前位置交换数据。
比如对于元素集合R={37, 40, 38, 42, 461, 5, 7, 9, 12}
在第一趟排序中:37直接和5交换, 形成新的序列 R1={5,40,38,42,461,37,7,9,12}
在第二趟排序中:40直接和7交换, 形成新的序列 R2={5,7,38,42,461,37,40,9,12}
以此类推,直到最后一个元素(注意:在第二趟排序中,38比42小,但是他们并没有交换数据)。
以下是简单选择排序的一个Java实现版本:
public static void selectionSort(int[] data) { if (data == null || data.length <= 1) return; int i, j, value, minPos, len = data.length; int outer = len - 1, tmp; for (i = 0; i < outer; i++) { value = data[i]; minPos = -1; for (j = i + 1; j < len; j++) { if (data[j] < value) { minPos = j; value = data[j]; } } if (minPos != -1) { tmp = data[i]; data[i] = value; data[minPos] = tmp; } // for (int k = 0; k < len; k++) { // System.out.print(data[k] + " , "); // } // System.out.println(); } } public static void main(String[] args) { int[] coll = { 37, 40, 38, 42, 461, 5, 7, 9, 12 }; selectionSort(coll); for (int i = 0; i < coll.length; i++) { System.out.print(coll[i] + " , "); } } |