我的Java开发学习之旅------>Java经典排序算法之选择排序

一、算法原理

对比数组中前一个元素跟后一个元素的大小，如果后面的元素比前面的元素小则用一个变量k来记住他的位置， 接着第二次比较，前面“后一个元素”现变成了“前一个元素”，继续跟他的“后一个元素”进行比较如果后面的元素比 他要小则用变量k记住它在数组中的位置(下标)，等到循环结束的时候，我们应该找到了最小的那个数的下标了， 然后进行判断，如果这个元素的下标不是第一个元素的下标，就让第一个元素跟他交换一下值，这样就找到整 个数组中最小的数了。然后找到数组中第二小的数，让他跟数组中第二个元素交换一下值，以此类推。

二、算法分析

1.时间复杂度选择排序的交换操作介于 0 和 (n - 1） 次之间。选择排序的比较操作为 n (n - 1） / 2 次之间。选择排序的赋值操作介于 0 和 3 (n - 1） 次之间。比较次数O(n^2），比较次数与关键字的初始状态无关，总的比较次数N=(n-1）+(n-2）+...+1=n*(n-1）/2。交换次数O(n），最好情况是，已经有序，交换0次；最坏情况交换n-1次，逆序交换n/2次。交换次数比冒泡排序少多了，由于交换所需CPU时间比比较所需的CPU时间多，n值较小时，选择排序比冒泡排序快。2.稳定性选择排序是给每个位置选择当前元素最小的，比如给第一个位置选择最小的，在剩余元素里面给第二个元素选择第二小的，依次类推，直到第n-1个元素，第n个元素不用选择了，因为只剩下它一个最大的元素了。那么，在一趟选择，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。比较拗口，举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

三 、算法演示

四、代码实现

public class SelectSort {
public static void selectSort(int[] a) {
int minIndex = 0;
int temp = 0;
if ((a == null) || (a.length == 0))
return;
for (int i = 0; i < a.length - 1; i++) {
minIndex = i;// 无序区的最小数据数组下标
for (int j = i + 1; j < a.length; j++) {
// 在无序区中找到最小数据并保存其数组下标
if (a[j] < a[minIndex]) {
minIndex = j;
}
}
if (minIndex != i) {
// 如果不是无序区的最小值位置不是默认的第一个数据，则交换之。
temp = a[i];
a[i] = a[minIndex];
a[minIndex] = temp;
}
System.out.println("第" + (i + 1) + "趟：");
printArray(a);
}
}

private static void printArray(int[] source) {
for (int i = 0; i < source.length; i++) {
System.out.print("\t" + source[i]);
}
System.out.println();
}

public static void main(String[] args) {
int[] source = { 70,30,40,10,80,20,90,100,75,60,45};
System.out.println("初始关键字：");
printArray(source);

selectSort(source);

System.out.println("\n\n排序后：");
printArray(source);
}
}

五、运行结果

初始关键字：
70304010802090100756045
第1趟：
10304070802090100756045
第2趟：
10204070803090100756045
第3趟：
10203070804090100756045
第4趟：
10203040807090100756045
第5趟：
10203040457090100756080
第6趟：
10203040456090100757080
第7趟：
10203040456070100759080
第8趟：
10203040456070751009080
第9趟：
10203040456070758090100
第10趟：
10203040456070758090100


排序后：
10203040456070758090100

==================================================================================================

  作者：欧阳鹏  欢迎转载，与人分享是进步的源泉！

  转载请保留原文地址：http://blog.csdn.net/ouyang_peng

==================================================================================================