选择排序——直接选择排序

on October 10, 2016 under jekyll

1 minute read

算法描述：

基本思想是：每一趟选出最小或最大的值放在最前或最后的位置。经过n-1趟完成排序。

稳定性：不稳定。

时间复杂度：

直接选择排序的比较次数与数据序列初始排序无关。第i趟比较次数为n-i次，总比较次数为n*（n-1）/2，大约等于（n^2）/2.

最好情况（已排序）：比较n-1次，移动0次。

最坏情况（逆序）：比较n-1次，移动3（n-1）。

一次直接选择排序的时间复杂度为O（n^2）。

空间复杂度：O（1）。

Java实现：

//选择排序——直接选择排序
public class M005 {
	public static void main(String[] args) {
		int[] number = { 21, 32, 2, 4, 2, 65, 90, 54 };
		int[] result = selectSort(number);
		for (int i : result) {
			System.out.print(i + " ");
		}
	}

	private static int[] selectSort(int[] number) {
		for (int i = 0; i < number.length - 1; i++) {
			int min = i;
			for (int j = i + 1; j < number.length; j++) {
				if (number[j] < number[min]) {
					min = j;
				}
			}
			if (min != i) {
				int temp = number[i];
				number[i] = number[min];
				number[min] = temp;
			}
		}
		return number;
	}
}

学习笔记, 数据结构, Java, 排序

I feedback.
Let me know what you think of this article on twitter @Yanlei_Hello or leave a comment below!