算法练习_选择排序

Posted on | Edited on | Comments: | Views:
选择排序的学习笔记以及代码实现

概念

问题描述

给定无序数组，将数组按从小到大的顺序排列。

算法思想

首先找到数组中最小的元素，其次，将它和数组的第一个元素交换位置（如果第一个元素最小那么它就和自己交换）。接着，在剩下的元素中找出最小元素，将它与数组的第二个元素交换位置。重复上述过程，直到将整个数组排序。

运用递归的思想，核心部分是将数组中最小的元素取出，再把这个元素排除，数组剩余部分进行递归。

图解

代码实现

clojure

1
2
3
4
5
6
(defn selection-sort [items]
  (if (empty? items)
    '()
    (cons (apply min  items) (selection-sort (remove #(= (apply min items)  %) items)))
    )
  )

java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public int[] selectionSort(int[] a) {
    for (int i = 0; i < a.length; i++) {
        int min = i;
        for (int j = i + 1; j < a.length; j++) {
            if (a[min] > a[j]) {
                min = j;
            }
        }
        if (i != min) {
            int x = a[i];
            a[i] = a[min];
            a[min] = x;
        }
    }
    return a;
}

特点

  • 运行时间和输入无关

    无论输入的数组是否有序，选择排序都会一遍一遍遍历数组去选择出最小的元素

  • 数据移动最少

    每次交换都会改变两个位置的值

参考文档

《算法》