排序算法 – 选择排序(selection sort)

选择排序(Selection sort)跟插入排序一样,也是O(n^2)的复杂度,这个排序方式也可以用我们的扑克牌来解释。

概念

桌面上有一堆牌,也是杂乱无章的,现在我们想将牌由小到大排序,如果使用选择排序来做,应该是这样来做。
1. 遍历桌面牌堆里的牌,从第一张牌到最后一张,找到牌面最小的一张,然后将抽出,并扣在手上。
2. 第二次遍历桌面牌堆里的牌,从第一张牌到最后一张,仍然去找现在桌面上牌面最小的一张,找出来,还是扣在手上。
3. 第三次遍历……重复步骤。虽然桌面上的牌是无序的,但是我们扣在手上的牌是有序的。
4. 第N次遍历……重复直到结束,现在桌面上没有牌,所有的牌都抓在手里,而且手上的牌全是排序排好的。
这个过程就是选择排序。

伪代码 – SelectionSort(seq)

n = seq.length
for j=1 to n-1
    smallest = j
    for i = j+1 to n
        if seq[i] < seq[smallest]
            smallest = i
    exchange seq[j] with seq[smallest]

注:
j=1指的是第一个元素,即我们常常的seq[0]。
套用一种语言来实现算法。

Python版

def sort(seq):
    n = len(seq)
    for j in range(n - 1):
        smallest = j
        for i in range(j + 1, n):
            if seq[i] < seq[smallest]:
                smallest = i
        if smallest != j:
            seq[j], seq[smallest] = seq[smallest], seq[j]
    return seq

Python版源码:Github-Syler-Fun-Selectionsort-Python

Java版

public static int[] sort(int[] seq)
{
 int n = seq.length;
 for(int j = 0; j < n - 1; j++){
   int smallest = j;
   for(int i = j + 1; i < n; i++){
     if(seq[i] < seq[smallest]){
       smallest = i;
     }
     if(smallest !=j) {
       int temp = seq[smallest];
       seq[smallest] = seq[j];
       seq[j] = temp;
     }
   }
 }
 return seq;
}

Java版源码:Github-Syler-Fun-Selectionsort-Java
看起来还是Python写起来比较短一点呢。

发表评论

电子邮件地址不会被公开。 必填项已用*标注