排序算法:选择排序之直接选择排序
直接选择排序是选择排序算法的基本实现,也是一种经典的排序算法,理解起来也简单。

选择排序基本思想:每次从待排序的数据元素中选取关键字最小(或最大)的元素放到数据元素集合的最前面(或最后面),数据元素集合不断缩小,当数据元素集合为空时,排序完成。常用的选择排序算法有直接选择排序和堆排序两种。【堆排序是一种基于完全二叉树的排序】

直接选择排序的基本思想:从待排序的数据元素集合中选取关键字最小的元素并将其与原始数据集合中的第一个元素互换;然后从不包括第一个元素的数据集中选取关键字最小的数据元素,将其与集合中第二个元素互换;....... 如此重复,直到数据元素集合中只剩一个元素时【也可以说进行下一次操作数据集合为空时】,排序完成。

C语言实现及测试:
#include <stdio.h>

/**
 * 直接选择排序:升序
 * @param data  待排序集合
 * @param len   集合大小
 *
 * 注: 此处为方便演示,依旧只是进行简单的 int数组 排序
 */
void selectSortAsc(int data[], int len){
    int i = 0, j = 0;
    int smallIndex = 0, temp = 0;
    for(i = 0; i < len - 1; i++){
        smallIndex = i;
        for(j = i+1; j < len; j++){
            if(data[smallIndex] > data[j]){
                smallIndex = j;  //记录最小元素的下标
            }
        }
        if(smallIndex != i){   //最小元素下标不是 i 时交换,即不是本身时执行交换
            temp = data[i];
            data[i] = data[smallIndex];
            data[smallIndex] = temp;
        }
    }
}

/**
 * 测试
 */
int main(int argc, char const *argv[]){
    
    int i = 0;
    int a[] = {65, 34, 25, 87, 12, 38, 56, 46, 14, 77, 92, 23};
    int n = 12;
    selectSortAsc(a, n);

    for(i = 0; i < n; i++){
        printf("%d ", a[i]);
    }

    return 0;
}

复杂度分析
在直接选择排序中,第 1 次比较需进行 n-1 次比较,第 2 次需要进行 n-2 次比较... ... 第 n-1 次需要进行 1 次比较,所以可以得出总的比较次数:(n-1)+(n-2)+(n-3)+ ... ... +1;也就是n(n-1)/2。所以时间复杂度为 O(n2)。空间复杂度,在待排序元素本身就有序的情况下,即最好情况下,空间复杂度为 O(0),最坏情况下为 O(n), 平均空间复杂度为 O(1)

总结
选择排序是很好理解的,因为其实现过程比较贴近生活(暂且这么说),选择大小的过程是排序的关键。值得注意的是该算法是不稳定的算法,因为每次丛无序区选取元素与无序区第一个元素交换时可能导致关键字相同的元素位置发生变化。如果在选出最小(或最大)元素后将它前面的无需元素依次向后移动一个单元,然后再将最小(或最大)元素放到有序区之后,这样就能保证稳定性,所以说也可以实现稳定,但是这样做也就比之前多了额外的开销。

以上只是个人看法,欢迎留言补充。
It's
欢迎访问本站,欢迎留言、分享、点赞。愿您阅读愉快!
*转载请注明出处,严禁非法转载。
https://www.devsong.org
QQ留言 邮箱留言
头像
引用:
取消回复
提交
涂鸦
涂鸦
热门