今天利用了一个小时的时间来复习了一下选择排序。

1. 程序模板

 

在开始之前，首先根据 Algorithms 书中的例子写了一个程序的模板。 书中的代码我稍作了修改。如下所示：

1 package com.jacob.demo; 2  3 /** 4  * This is a sample for sort algorithms. 5  * @author jacobqiao 6  * 7  */ 8 public class Example { 9     10     /**11      * The function for sort.12      * @param a13      */14     public static void sort(Comparable
     
      [] a) {15         16     }17     18     /**19      * Compare if v is less than w.20      * @param v21      * @param w22      * @return23      */24     public static boolean less(Comparable
      
        v, Comparable
       
         w) {25         return v.compareTo((String) w) < 0;26     }27     28     /**29      * exchange two elements.30      * @param a31      * @param i32      * @param j33      */34     public static void exch(Comparable
        
         [] a, int i, int j) {35         Comparable
         
           t = a[i];36         a[i] = a[j];37         a[j] = t;38     }39     40     /**41      * Print array.42      * @param a43      */44     private static void show(Comparable
          
           [] a) {45 for (int i= 0; i< a.length; i++) {46 System.out.println(a[i] + " ");47 }48 System.out.println();49 }50 51 /**52 * Judge if array is sorted53 * @param a54 * @return55 */56 public static boolean isSorted(Comparable
           
            [] a) {57 for (int i = 1; i < a.length; i++) {58 if (less(a[i], a[i-1])) {59 return false;60 }61 }62 63 return true;64 }65 66 public static void main(String[] args) {67 String[] a = {};68 sort(a);69 assert isSorted(a);70 show(a);71 }72 }
           
          
         
        
       
      
     

之后所有的排序基本上都会根据这个模板来修改。 该模板中主要包含几个方法：

sort() 用来写排序

less() 用来比较两个元素的大小

exch()用来交换数组中两个元素的位置

show()用来输出当前数组

2.选择排序的步骤

选择排序的步骤相对来说是比较简单的，主要有以下几步来完成：

（1）找到数组中最小的元素

（2）将最小的元素和数组的第一个元素交换位置

（3）在剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。

  如此往复，一直到将数组余下的全部排序完。 

 

例如下面的一组字母：

S O R T E X A M P L E

 

开始排序:

 

A [O R T E X S M P L E]     找出最小的A，与第一位的S交换，然后将第一位指针后移

A E [R T O X S M P L E]     找出最小的E，与第一位的O交换，然后将第一位指针后移

A E E [T O X S M P L R]     找出最小的E，与第一位的R交换，然后将第一位指针后移

A E E L[ O X S M P T R]　  找出最小的L，与第一位的T交换，然后将第一位的指针后移

A E E L M [X S O P T R]      依

A E E L M O [S X P T R]　   次

A E E L M O P [X S T R]　　类

A E E L M O P R [S T X]　　推

A E E L M O P R S [T X]      .

A E E L M O P R S T [X]　　.

A E E L M O P R S T X []　　一直到循环结束。

 

 

3.代码实现（Java）

按照这个步骤，sort方法里面应该这样写：

1 /** 2      * The function for sort with selection. 3      * @param a 4      */ 5     public static void sort(Comparable
      
       [] a) { 6         System.out.println("Before Begin"); 7         show(a);  //显示原始数组 8          9         System.out.println("Begin:");10         11         12         // the first loop level13         for(int i = 0; i < a.length; i++) {14             int min = i;    //每一轮开始， 最开始指针后移15             16             // the second loop, find the smallest element in last array. and let min point to it.17             for (int j = i+1; j < a.length; j++) {18                 if(less(a[j], a[min])) {19                     min = j;20                 }21             }22             23             // change min element's place to last array's first place.24             exch(a, i, min);25             show(a);26         }27     }
      

可以看到，选择排序的逻辑还是比较简单的，就是从前向后，每一轮找出最小的放在最前面，一直到数组循环结束。

因此也决定了，选择排序的特性：数据移动最少。其移动次数是线性级别的。

 

下面是Java版本的全部代码：

package com.jacob.demo;public class Selection {    /**     * The function for sort with selection.     * @param a     */    public static void sort(Comparable
      
       [] a) {        System.out.println("Before Begin");        show(a);                System.out.println("Begin:");                        // the first loop        for(int i = 0; i < a.length; i++) {            int min = i;                        // the second loop, find the smallest element in last array. and let min point to it.            for (int j = i+1; j < a.length; j++) {                if(less(a[j], a[min])) {                    min = j;                }            }                        // change min element's place to last array's first place.            exch(a, i, min);            show(a);        }    }        /**     * Compare if v is less than w.     * @param v     * @param w     * @return     */    public static boolean less(Comparable
       
         v, Comparable
        
          w) {        return v.compareTo((String) w) < 0;    }        /**     * exchange two elements.     * @param a     * @param i     * @param j     */    public static void exch(Comparable
         
          [] a, int i, int j) {        Comparable
          
            t = a[i];        a[i] = a[j];        a[j] = t;    }        /**     * Print array.     * @param a     */    private static void show(Comparable
           
            [] a) { for (int i= 0; i< a.length; i++) { System.out.print(a[i] + " "); } System.out.println(); } /** * Judge if array is sorted * @param a * @return */ public static boolean isSorted(Comparable
            
             [] a) { for (int i = 1; i < a.length; i++) { if (less(a[i], a[i-1])) { return false; } } return true; } public static void main(String[] args) { String[] a = {"S","O","R","T","E","X","A","M","P","L","E"}; sort(a); assert isSorted(a);// show(a); }}
            
           
          
         
        
       
      

 

 

JS代码实现：

由于JS是弱类型的，因此其实现相对更简洁一些，无需再封装比较函数和显示函数。代码如下：

function selection(array) {    let arr = array;    for(i = 0; i < arr.length; i++) {        let min = i;        for (j= i+1; j < arr.length; j++) {            if (arr[j] <= arr[min]) {                min = j;            }        }        exch(arr, i, min);    }}function exch(array, firstIndex, minIndex) {    let temp = array[firstIndex];    array[firstIndex] = array[minIndex];    array[minIndex] = temp;}function main() {    var arr = [5,3,7,1,7,8,1];    console.log(arr);    selection(arr);    console.log("after sort");    console.log(arr);}

 

以上就是今日一个小时左右的时间对选择排序的复习了。至于其性能，和时间以及空间复杂度，到后面再补充吧。希望自己不要忘记了。