选择排序
选择排序的思想很简单。
还不懂的附上百度百科选择排序。
稳定性
所以到底是不是稳定的呢？
不稳定解释
看过上面百度百科链接的人就会觉得一定不是稳定的啊。
因为例如如下：
[5 8 5 2 9 4]
这个在第一次选择最小的时候，就把5和2的位置掉换了，变成如下：
[2 8 5 5 9 4] ========= [5 8 5 2 9 4]//这是原始数组，观察数字5的位置。
第一次操作就被放到另外一个5后面了，，已经破坏了稳定性。
那么是不是就是不稳定的呢？
不绝对。
稳定解释
我们观察到，选择排序的不稳定，在于发生了位置交换。
那么不发生位置交换呢？ 直接把最小的放到第一个位置上，把第二小的放到第二个位置上。
那么怎么才能实现呢？
新开辟一个数组O(N)空间 链表
这样我们就不会发生位置交换了！！
那么就是一个稳定的了。
结论
因为2和3虽然发生位置变换，但是没发生位置交换。所以相同的数字不会交换位置。
代码实现
下面我分别实现了上面结论中的1 和 3方法。 2写起来有点麻烦，暂时不想写了。
代码如下：
;//传统的选择排序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;}}}}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) {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;}
测试用例就是随便一串数字就可以了。
[ ]
用最多的梦面对未来
