简单排序之选择排序

发表于 | 更新于 | 分类于 | 阅读次数： | 阅读次数：
本文字数： 1k | 阅读时长 ≈ 1 分钟

简单选择排序 T=O(N^2)


　　

基本思想：

第一趟在初始序列A[0]~A[n-1]中找出最小值元素的下标， 然后将该最小元素与A[0]调换位置，
下一趟排序在A[1]~A[n-1]中找出最小值元素的下标， 然后将该最小元素与A[1]调换位置…
经过n-1次调换后可排序完成。 　　

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class ChooseSortTest {

    private static void chooseSort(int[] arr) {
        for (int i = 0; i < arr.length; i++) {
            int least = i; //先假设待排序列中第一个元素最小
            for (int j = i + 1; j < arr.length; j++) { 
                if (arr[j] < arr[least]) { //比对查找待排序列中的最小元素下标
                    least = j;
                }
            }
            //将待排序列中的最小元素调到序列最前端
            Swap(arr,i,least);
        }
    }
    //调换数组中两元素的位置
    private static void Swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

　　

选择排序的效率：

　　选择排序和冒泡排序执行了相同次数的比较：N*(N-1)/2.对于10个数据项，需进行45次比较。

　　然而，10个数据项只需要10次数据交换，而对于100个数据项，需要4950次比较，但只进行不到100次交换。

　　当N值很大时，比较的次数是主要的，所以结论是选择排序和冒泡排序一样运行了O(N^2)时间，但是，选择排序无疑更快，因为它进行的交换少得多。

---------------- The End ----------------
0%