选择排序(Selection Sort)

执行流程
  • 找出数组中最大的那个元素，和数组末尾元素进行叫魂
  • 执行完一轮后，数组末尾的元素就是最大元素
  • 依次找出剩余元素中的最大者，交换

代码如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

    
    /*
    * 交换，array i 和 j位置的元素
    * */
    protected void swap(int i1, int i2){
        swapcount ++;

        int tmp = array[i1];
        array[i1] = array[i2];
        array[i2] = tmp;
    }

    /*
    * 比较两个下标的元素
    * 返回值等于0 , 代表array[i1] == array[i2]
    * 返回值 < 0,  代表array[i1] < array[i2]
    * 返回值 > 0,  代表array[i1] > array[i2]
    * */
    protected int cmp(int i1, int i2){
        cmpcount ++;
        return array[i1] - array[i2];
    }
	
    
    protected void sort() {
        for (int i = array.length - 1; i > 0; i--) {
            int maxIdx = 0;
            for (int j = 1; j <= i; j++) {
                if (cmp(j, maxIdx) > 0){
                    maxIdx = j;
                }
            }
            swap(maxIdx, i);
        }
    }