算法學習 - 選擇排序的穩定性討論(C++實現)

選擇排序

選擇排序的思想很簡單。

每次選擇當前的最小數字。 向後移動一位，選擇第二小的數字。 … 移動到倒數第二位，操作後截止。

還不懂的附上百度百科選擇排序。

穩定性

所以到底是不是穩定的呢？

不穩定解釋

看過上面百度百科鏈接的人就會覺得一定不是穩定的啊。

因為例如如下：

[5 8 5 2 9 4]

這個在第一次選擇最小的時候，就把5和2的位置掉換了，變成如下：

[2 8 5 5 9 4]
=========
[5 8 5 2 9 4]//這是原始數組，觀察數字5的位置。

第一次操作就被放到另外一個5後面了，已經破壞了穩定性。

那麼是不是就是不穩定的呢？

不絕對。

穩定解釋

我們觀察到，選擇排序的不穩定，在於發生了位置交換。

那麼不發生位置交換呢？
直接把最小的放到第一個位置上，把第二小的放到第二個位置上。

那麼怎麼才能實現呢？

新開辟一個數組O(N)空間 鏈表

這樣我們就不會發生位置交換了！！

那麼就是一個穩定的了。

結論

當數組實現，O(1)空間復雜度下是不穩定的。 當數組實現，O(n)空間復雜度可以達到穩定。 用鏈表可以實現穩定。

因為2和3雖然發生位置變換，但是沒發生位置交換。所以相同的數字不會交換位置。

代碼實現

下面我分別實現了上面結論中的1 和 3方法。
2寫起來有點麻煩，暫時不想寫了。

代碼如下：

//
//  main.cpp
//  SelectSort
//
//  Created by Alps on 15/4/2.
//  Copyright (c) 2015年 chen. All rights reserved.
//

#include 

using namespace std;
//傳統的選擇排序
void SelectSort(int *arr, int length){
    int temp = 0;
    for (int i = 0; i < length; i++) {
        for (int j = i+1; j < length; j++) {
            if (arr[i] > arr[j]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
        }
    }
}

//////////////////下面是鏈表實現的穩定算法/////////////
typedef struct node{
    int val;
    node *next;
    node(int v): val(v), next(NULL){}
}*list;

list SelectSort_t(list header){
    if (header == NULL && header->next == NULL) {
        return NULL;
    }
    list swap;
    list curtemp = header;
    list temp = curtemp->next;

    while (curtemp && curtemp->next && curtemp->next->next) {
        while (temp && temp->next) {
            if (temp->next->val < curtemp->next->val) {
//                if (curtemp->next == temp) {
//                    curtemp->next = temp->next;
//                    temp->next = temp->next->next;
//                    curtemp->next->next = temp;
//                    continue;
//                }
                swap = temp->next;
                temp->next = swap->next;
                swap->next = curtemp->next;
                curtemp->next = swap;
                continue;
            }
            temp = temp->next;
        }
        curtemp = curtemp->next;
        temp = curtemp->next;
    }
    return header->next;
}



int main(int argc, const char * argv[]) {
    int a[]= {5, 8, 5, 2, 9, 4};
    SelectSort(a, sizeof(a)/sizeof(int));
    for (int i = 0; i < sizeof(a)/sizeof(int); i++) {
        printf("%d ",a[i]);
    }
    printf("\n");
    list header = new node(0);
    list temp;
    for (int j = 0; j < 6; j++) {
        temp = (list)malloc(sizeof(struct node));
        scanf("%d", &temp->val);
        temp->next = header->next;
        header->next = temp;
    }
    header = SelectSort_t(header);
    while (header) {
        printf("%d ",header->val);
        header = header->next;
    }
    return 0;
}

測試用例就是隨便一串數字就可以了。

[ 5 8 5 9 2 4 ]