数据结构_排序③选择排序

2019-08-15 0 条评论 40 次阅读 0 人点赞

三.选择排序

每一次从待排序的数据元素中选出最小(或最大)的一个元素,存放在序列的起始位置,直到全部待排序的数据元素排完
时间复杂度: O(N^2)
空间复杂度: O(1)
稳定性: 可以稳定

void Swap(int* x, int* y){
    int tmp = *x;
    *x = *y;
    *y = tmp;
}

void SelectSort(int* a, int n){
    int begin = 0 , end = n-1;
    while(begin < end){
        //每次选一个最大的和最小的, 放到对应位置
        int i, max, min;
        max = min = begin;
        //小的选第一个, 大的选最后一个
        for(i = begin; i <= end; ++i){
            if(a[i] < a[min])
                min = i;
            if(a[i] >= a[max])//>=就稳定
                max = i;
        }
        //min --> begin   max -->end
        Swap(&a[begin], &a[min]);
        //判断最大元素位置是否发生变化
        if(max == begin)
            max = min;
        Swap(&a[end] , &a[max]);
        ++begin;
        --end;
    }

}

L_KingMing

这个人太懒什么东西都没留下

文章评论(0)