选择排序算法(JAVA版)

选择排序和插入排序差不多,交换的次数减少。平均/最好/最坏时间复杂度是O(n2),是不稳定的排序算法。(插入排序是稳定排序算法)

update:以前写错了一个地方,应该每次要把最小值找出来,记下来,每次和最小值去比较,目的就是为了从后面找到最小的值。

public class Test {
	/*
	 * 选择排序:选择最小/大的放在前面,每一趟前几个按序排列
	 */
	static int[] selectSort(int[] arr) {
		for (int i = 0; i < arr.length - 1; i++) {
			int k = i;
			int min = arr[i];
			// 和i后面的每一个比较,如果有比i小的记下下标k
			for (int j = i + 1; j < arr.length; j++) {
				if (arr[j] < min) {
					k = j;
					min = arr[j];
				}
			}
			if (k != i) {// 交换
				int temp = arr[i];
				arr[i] = arr[k];
				arr[k] = temp;
			}
		}
		return arr;
	}
 
	public static void main(String[] args) {
		int arr[] = new int[] { 1, 5, 7, 2, 6, 0 };
		int newarr[] = selectSort(arr);
 
		System.out.println("----------------------");
 
		for (int i : newarr) {
			System.out.println(i);
		}
	}
}



fatkun

11条评论

这个算法是错误的,随便写段测试下就知道if (arr < arr ) 这里不对, 应该是 arr > arr 是和选定的最小的基准比较

果然是写错了。。谢谢提醒。但错误不在于>和<的问题,这个只是你想要从小到大排序还是逆转过来。错误在于我没把最小值存下来,每次比较的值错了。

发表评论

电子邮件地址不会被公开。