上篇文章中我們分析了冒泡排序,我們知道了冒泡排序可能需要N次交換和N次比較。
N次比較在所難免,但N次交換是必須的么?
今天我們介紹的選擇排序方法只需要一次交換。
思路也很簡單:每趟從待排序的序列中選擇最小的元素,放到已排序序列末尾;
這里通過交換實現原地排序。
我們對該序列進行排序:
是不是和冒泡排序很相似,左邊橙色部分是已排序序列,右邊是待排序序列,且右邊必不小于左邊。
并且,可以看到:2、3、7趟并沒有發生交換。
/*** 每趟排序從i右邊找到最小的元素,和i交換(選擇)* @param a* @param <E>*/
public static <E extends Comparable<? super E>> void selectionSort(E[] a) {for (int i = 0; i < a.length; i++) {int minIndex = i;for (int j = i + 1; j < a.length ; j++) {//找到右邊最小元素索引if (a[j].compareTo(a[minIndex]) < 0) {minIndex = j;}}swap(a,i,minIndex);//System.out.println("i=" + i + Arrays.toString(a));}
}private static <E> void swap(E[] array, int i, int j) {if (i == j) return;E tmp = array[i];array[i] = array[j];array[j] = tmp;
}
共N次迭代,在第k次迭代中,找到最小元素O(N?k)O(N-k)O(N?k)
因此總體復雜度為 O(N2)O(N^2)O(N2)
簡單選擇排序由于選出最小值后需要交換位置,位置一變就會變得不穩定。
例如序列5 8 5 2 9, 我們知道第一遍,第一個元素5會和2交換,那么原序列中2個5的相對前后順序就被破壞了,所以選擇排序不是一個穩定的排序算法
版权声明:本站所有资料均为网友推荐收集整理而来,仅供学习和研究交流使用。
工作时间:8:00-18:00
客服电话
电子邮件
admin@qq.com
扫码二维码
获取最新动态