選擇排序 Selection sort

1、概念

選擇排序是一種簡(jiǎn)單直觀的排序算法。它的工作原理如下。首先在未排序序列中找到最?。ù螅┰?，存放到排序序列的起始位置，然后，再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰兀缓蠓诺揭雅判蛐蛄械哪┪?。以此類推，直到所有元素均排序完畢。

選擇排序的主要優(yōu)點(diǎn)與數(shù)據(jù)移動(dòng)有關(guān)。如果某個(gè)元素位于正確的最終位置上，則它不會(huì)被移動(dòng)。選擇排序每次交換一對(duì)元素，它們當(dāng)中至少有一個(gè)將被移到其最終位置上，因此對(duì) n 個(gè)元素的表進(jìn)行排序總共進(jìn)行至多 n-1 次交換。在所有的完全依靠交換去移動(dòng)元素的排序方法中，選擇排序?qū)儆诜浅：玫囊环N。

2、運(yùn)行過程

1、首先在原始序列中找到最?。ù螅┰兀娣诺脚判蛐蛄械钠鹗嘉恢?/p>

2、再?gòu)氖Ｓ辔磁判蛟刂欣^續(xù)尋找最?。ù螅┰?，然后放到已排序序列的末尾。

3）重復(fù)第二步，直到所有元素均排序完畢。
如圖：（找到最小的元素放在起始位置）

image

3、代碼

java

   public void sort1(Integer[] array){
        for (int end = array.length -1 ; end > 0 ; end--) {
            int max = 0;
            for (int begin = 1; begin <= end; begin++) {
                if (array[max] < array[begin ]){
                   max = begin;
                }
            }
            int tmp = array[max];
            array[max] = array[end];
            array[end] = tmp;
        }
    }

object-c

-(NSArray *)sort:(NSArray *)array{
    if (array.count <= 1) {
        return array;
    }
   NSMutableArray *sortedArray = [array mutableCopy];
    for (NSInteger i = sortedArray.count - 1; i > 0; i--) {
        NSInteger max = 0;
        for (NSInteger j = 1; j <= i ; j++) {
            if ([sortedArray[max] integerValue] < [sortedArray[j] integerValue]) {
                max = j;
            }
        }
        [sortedArray exchangeObjectAtIndex:max withObjectAtIndex:i];
    }
    
    return [sortedArray copy];
    
}

4、性能（算法時(shí)間、空間復(fù)雜度、穩(wěn)定性）分析

選擇排序的交換次數(shù)要遠(yuǎn)遠(yuǎn)少于冒泡排序，平均性能優(yōu)于冒泡排序
最好、最壞、平均時(shí)間復(fù)雜度: 0(n^2)， 空間復(fù)雜度: 0(1), 屬于不穩(wěn)定排序

思考：選擇排序是否還有優(yōu)化空間？

使用堆來選擇最大值