选择排序

选择排序的思想很简单。

每次选择当前的最小数字。向后移动一位，选择第二小的数字。 … 移动到倒数第二位，操作后截止。

还不懂的附上百度百科选择排序。

稳定性

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

不稳定解释

看过上面百度百科链接的人就会觉得一定不是稳定的啊。

因为例如如下：

[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 ]

算法学习 - 选择排序的稳定性讨论(C++实现)

选择排序

稳定性

不稳定解释

稳定解释

结论

代码实现