选择排序

2016年05月19日

概述

• 走访列表长度次，每次选出最小（或最大）的元素，重新排顺序

步骤

• 第一次选出最小（或最大）的元素，放在列表的起始位置，即与开头元素交换
• 接下来每次选出最小（或最大）的元素，与索引等于当前的循环次数的元素进行交换
• 将列表分为已选择出来的有序区，等待选择的无序区

代码实现

Python 选择排序

def sort_xz_1(v_list):
    for i in range(len(v_list)-1):
        min = i
        for j in range(i+1,len(v_list)):
            if v_list[min] > v_list[j]:
                min = j
        v_list[min],v_list[i] = v_list[i],v_list[min]
    return v_list

C选择排序

void swap(int*a,int*b)
{
    int temp;
    temp=*a;
    *a=*b;
    *b=temp;
}
void select_sort(int A[],int n)
{
    register int i,j,min,m;
    for(i=0;i<n-1;i++)
    {
        min=i;//查找最小值
        for(j=i+1;j<n;j++)
        {
            if(A[min]>A[j])
            {
                min=j;
            }
        }
        if(min!=i)
        {
            swap(&A[min],&A[i]);
            printf("第%d趟排序结果为:\n",i+1);
            for(m=0;m<n;m++)
            {
                if(m>0)
                {
                    printf("");
                }
                printf("%d",A[m]);
            }
            printf("\n");
        }
    }
}

性能分析

时间复杂度

比较时间复杂度为O(n^2)
交换时间复杂度未O(n)

算法稳定性

• 在一趟选择中，如果一个元素比当前元素小，而该小的元素又出现在一个和当前元素相等的元素后面，那么交换后稳定性就被破坏了。
• 举个例子，序列5 8 5 2 9，我们知道第一遍选择第1个元素5会和2交换，那么原序列中两个5的相对前后顺序就被破坏了，所以选择排序是一个不稳定的排序算法。

算法

阅读全文