18.1.选择排序

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

\(18.1\)Selection Sort

1.The step of Selection sort

  In selection sort, we basically do these three things:

  1. Find the smallest item.
  2. Move it to the front.
  3. Selection sort the rest(using recursion).

  For each step, we can design an individual method to implement it.

2.Step implementation

  As the moving step requires the index of the to-moving element, the value we return should be index of elements, too.

  \(a.\)Find

1
2
3
4
5
6
7
8
9
10
private static int Find(int[] arr) {
    int minIndex = 0;
    for (int i = 1; i < arr.length; i += 1) {
        if (arr[i] < arr[minIndex]) {
            i = minIndex;
        }
    }

    return minIndex;
}

  Given that we may need to Find the minimun in asked range, we may improve our method by passing an extra parameter which point to the start index(We'll use it in the following procedure)： 

1
2
3
4
5
6
7
8
9
10
11
12
13
private static int Find(int[] arr, int st) {
    if (st >= arr.length) {
        throw new IndexOutOfBoundsException();
    }
    int minIndex = st;
    for (int i = 1; i < arr.length; i += 1) {
        if (arr[i] < arr[minIndex]) {
            i = minIndex;
        }
    }

    return minIndex;
}

  \(b.\)swap

  We are going to implement the method by manipulating the index of the elements: 

1
2
3
4
5
private static void swap(int[] arr, int x, int y) {
    int tmp = arr[x];
    arr[x] = arr[y];
    arr[y] = tmp;
}

  \(c.\)Main method

  Since we would like to do the sorting recursively, we may introduce a helper method and invoke it recursively: 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Sort {
    public static void sort(int[] arr) {
        sortHelper(arr, index);
    }

    private void sortHelper(int[] arr, int index) {
        //basic situation
        if (index == arr.length()) return;
        //find the smallest item
        int minIndex = find(arr, index);
        //Move it to the front
        swap(arr, index, minIndex);
        //Recursively call the method
        sortHelper(arr, index + 1);
    }
}