数据结构与算法简记：选择排序

不念不忘少年蓝@ 2022-09-21 15:27 210阅读 0赞

最近把数据结构与算法方面的书又温习了一遍，觉得有必要在这里做个备忘记录，以后就算是生疏了，也可以很方便查阅。

今天就来简明扼要地总结一下选择排序的要点，拿n个元素的数组升序排列举例：

1.  先以数组第一个位置做参照，然后遍历后续元素，遍历过程中会跟第一个的元素进行比较，如果其值小于第一个元素，则交换；
2.  一趟下来，最小值被交换到了第一个位置，然后，数组的第二个位置将作为新的参照，开始新一轮的比较和交换。
3.  排序将会持续n-1轮，也就是说，最后一趟排序，将会是倒数第二个元素和最后一个元素进行比较。

以上过程在每轮比较中，存在多次交换，比较高效的做法是，在每一轮比较中，找到这一轮中最小的那个元素，然后与此轮参照元素进行交换，只执行一次交换即可。

下面是实现代码：

JS版：

//交换数组元素
    function swap(array, i, j) {
        
      var temp = array[i];
      array[i] = array[j];
      array[j] = temp;
    } 
    
    //选择排序
    function selectSort(array) {
        
      var i, j;
      var indexOfMin;       //用于标识每趟比较中最小值的索引
      var size = array.length;
    
      for (i = 0; i < size - 1; i++) {
        indexOfMin = i;     //每次初始化最小值的索引为第一个
    
        for (j = i + 1; j < size; j++) {
          if (array[j] < array[indexOfMin]) {
            indexOfMin = j; //如果找到更小的值则更新indexOfMin
          }
        }
    
        //交换
        if (i != indexOfMin) {
          swap(array, i, indexOfMin);
        }
      }
    }
    
    var array = [39, 28, 57, 12, 95, 45, 10, 73];
    
    selectSort(array);
    
    console.log(array);

Java版：

package algorithm;
    
    public class Sorting {
        
    
        private static void swap(int[] array, int i, int j) {
            int temp = array[i];
            array[i] = array[j];
            array[j] = temp;
        }
    
        public static void selectSort(int[] array) {
            int i, j, indexOfMin;
            int size = array.length;
    
            for (i = 0; i < size - 1; i++) {
                indexOfMin = i;
    
                for (j = i + 1; j < size; j++) {
                    if (array[j] < array[indexOfMin]) {
                        indexOfMin = j;
                    }
                }
    
                if (i != indexOfMin) {
                    swap(array, i, indexOfMin);
                }
            }
        }
    
        public static void main(String[] args) {
            int[] array = {
       39, 28, 57, 12, 95, 45, 10, 73};
    
            Sorting.selectSort(array);
    
            for (int i = 0; i < array.length; i++) {
                System.out.print(array[i] + " ");
            }
        }
    }

C语言版：

#include <stdio.h>
    
    void selectSort(int *array, int size);
    void swap(int *array, int i, int j);
    
    int main(int argc, const char * argv[]) {
    
        int array[] = {
       39, 28, 57, 12, 95, 45, 10, 73};
    
        int size = sizeof(array) / sizeof(array[0]);
    
        selectSort(array, size);
    
        for (int i = 0; i < size; i++) {
            printf("%d ", array[i]);
        }
    
        return 0;
    }
    
    void selectSort(int *array, int size) {
    
        int i, j;
        int indexOfMin;
    
        for (i = 0; i < size - 1; i++) {
    
            indexOfMin = i;
    
            for (j = i + 1; j < size; j++) {
    
                if (array[j] < array[indexOfMin]) {
                    indexOfMin = j;
                }
            }
    
            if (i != indexOfMin) {
                swap(array, i, indexOfMin);
            }
        }
    }
    
    void swap(int *array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }