数据结构 - 简单选择排序法

爱被打了一巴掌 2022-07-11 13:46 167阅读 0赞

# 数据结构 - 简单选择排序法 #

在之前的[博文][Link 1]里已经介绍过排序的两个基本方法：

双重循环法和冒泡排序法。

## 基本思想 ##

其实上面两种方法的基本思想都是一样的：

就是将排序步骤分成两层循环， 在内层的每1个循环中， 找出剩下未排序成员最小（大）的1个， 并将其放到队伍前列。

只不过， 冒泡排序法的元素交换更具效率， 通常情况下会比双重循环法更快完成排序。

这次介绍的简单选择法的本质也和上面两种方法一样的。

冒泡(or 双层循环)排序法每1个内层循环中， 会通过多次元素交换， 最终最小(大)的未排序元素会被移动到队伍前列。

而简单选择法就是定1个最小变量， 在1个内层循环中， 通过比较(而不是元素交换)得到未排序的最小(最大)元素的位置。然后才1次过把这个元素移动到前列。

## 简单选择排序法 代码 ##

如果你看懂上面写的是什么， 代码是很容易写出来的。

int simpleSelectionSort(int * arr, int len){
        int i,j;
        int min;
    
        for (i = 0; i < len -1; i++){
            min = i; //first make the first element to be the min
            for (j = i+1; j < len; j++){
                if (arr[j] < arr[min]){
                    min = j;
                }
            }
    
            //then the arr[j] is the min element in the loop
            if (i != min){
                _swap(arr, i, min);
            }
        }
    
    }

## 代码分析 ##

上面代码很简单， 在每1个内循环中， 我们会用min这个变量来存储最小的元素位置。  
然后用未排序元素来跟min位置元素比较…

debug信息：

4, 1, 5, 8, 0, 3, 7, 9, 6, 2
    step 0: changed: *0, 1, 5, 8, *4, 3, 7, 9, 6, 2
    0, *1, 5, 8, 4, 3, 7, 9, 6, 2
    step 1: changed: 0, 1, *2, 8, 4, 3, 7, 9, 6, *5
    step 2: changed: 0, 1, 2, *3, 4, *8, 7, 9, 6, 5
    0, 1, 2, 3, *4, 8, 7, 9, 6, 5
    step 3: changed: 0, 1, 2, 3, 4, *5, 7, 9, 6, *8
    step 4: changed: 0, 1, 2, 3, 4, 5, *6, 9, *7, 8
    step 5: changed: 0, 1, 2, 3, 4, 5, 6, *7, *9, 8
    step 6: changed: 0, 1, 2, 3, 4, 5, 6, 7, *8, *9
    change count: 7
    compare count: 45
    0, 1, 2, 3, 4, 5, 6, 7, 8, 9

可以见到这个简单选择排序方法不能减少比较次数， 但是大大减少了元素交换的次数。  
简单选择排序法的时间复杂度仍然是O(*n*2)

## 小结 ##

其实本文一开始提到的博文中提到， 冒泡排序法通过优化是能够元素比较次数的。

如果你的排序元素交换的开销比比较开销大得多的话，这个简单排序法是可以考虑的.

[Link 1]: http://blog.csdn.net/nvd11/article/details/54718754