选择排序过程详解

刺骨的言语ヽ痛彻心扉 2022-09-12 04:40 181阅读 0赞

## 选择排序过程详解 ##

### 1，引入 ###

*  和插入排序的**插入**一样，**选择**更多的是一种思路，使用这种思路排序的算法也有多种：  
    ![几种选择排序算法][5816372c3692409aa452ad8f96041799.png_pic_center]
 *  这篇文章要梳理的是其中最基础的一种——**简单选择排序**
 *  的确足够简单，以至于我写完本篇的大纲就觉得差不多讲完了。
 *  原因在于，简单选择排序太符和我们人的做法了，让我们手动排序也莫过如此~  
    ![手动对一组数排序][eedb685047b642d58ac58d2707cd3d0a.png_pic_center]
 *  和上面手动排稍稍有点不同，为了减少空间开销，在下面的代码中使用了交换位置，来代替另开辟一个新的数组。

### 2，对于升序排序，选出最小值放在第一个位置，再选出第二小的放在第二个位置…选出第n-1小的放在第n-1个位置，最大值(第n小的)自然在最后一个位置(第n个位置)。 ###

*  思路如题目
 *  根据这个思路可以想想代码怎么写（伪码）：

for (int i = 0; i < n - 1; ++i) {
        			// 每次向下取一位置
    		int min_pos = i;						// 假设当前这个位置的值就是剩余值里最小的
    		for (int j = i + 1; j < n; ++j) {
        		// 在剩余值里找有没有更小的
    			if (array[j] < array[min_pos])		
    				min_pos = j;					// 有就把min_pos更新成更小的位置处
    		}
    		array[min_pos] <-> array[i];			// 把剩余值里最小的放到最前面
    	}

*  可能用另一种理解方式，更容易理解和写出算法的实现代码。
 *  **比如：我们把最小值挑到最前面之后，就不再考虑这个值，把剩余的数看成一个新的序列重复这个过程，也就是挑出剩余序列中的最小值（相对于整个序列是第二小的）放到剩余序列的最前面，到最后是两个数组成的序列，继续把这两个数中的最小值（相对于整个序列是第n-1小的）放到前面，最后一个数（最大值）也自然被放到了末尾。**
 *  考虑一下简单选择排序的效率，主要的操作在于比较，第一次从n个数中找出最小值得比较n-1次，然后是n-2次。。。最后从一个数中找出最小值不用比：

(n-1) + (n-2) + ... + 1 + 0
    -> (n-1) * n/2
    -> n(n-1)/2
    ->O(n^2)

*  简单选择排序不算快，很多比较结果被浪费了，**锦标赛排序**和**堆排序**试图减少比较次数，来提高排序速度。
 *  依旧有个图解：  
    ![整个过程图解][60f7bb417507426fa7de17fd56ff93f0.png_pic_center]

### 3，实现 ###

#### 3，1 C++ ####

*  C++实现

void selection_sort(vector<int>& ivec) {
        
    	for (int i = 0; i < ivec.size() - 1; ++i) {
        
    		auto least = i;
    		for (int j = i + 1; j < ivec.size(); ++j) {
        
    			if (ivec.at(j) < ivec.at(least)) 
    				least = j;
    		}
    		// swap
    		auto tmp = ivec.at(i);
    		ivec[i] = ivec.at(least);
    		ivec[least] = tmp;
    	}
    }

*  C++调用

int main() {
        
    	vector<int> ivec = {
         3, 6, 1, 4, 8, 2 };
    	selection_sort(ivec);
    	for (auto i : ivec)
    		cout << i << " ";
    }
    
    // 输出：1 2 3 4 6 8

#### 3，2 Python ####

*  Python实现

def selection_sort(collection):
        length = len(collection)
        for i in range(length - 1):
            least = i
            for k in range(i + 1, length):
                if collection[k] < collection[least]:
                    least = k
            if least != i:
                collection[least], collection[i] = (collection[i], collection[least])
        return collection

*  Python调用

if __name__ == "__main__":
        seq = [3, 6, 1, 4, 8, 2]
        print(*test_ss(seq))
        
        # 输出：1 2 3 4 6 8

### 4，参考 ###

*  [Selection Sort - GeeksforGeeks][]
 *  [All Algorithms implemented in Python][]

[5816372c3692409aa452ad8f96041799.png_pic_center]: /images/20220828/7b88acb5701643f3b9d36b09d4b9c62c.png
[eedb685047b642d58ac58d2707cd3d0a.png_pic_center]: /images/20220828/77d694f7e31b40cb93220ed0bf4d2d87.png
[60f7bb417507426fa7de17fd56ff93f0.png_pic_center]: /images/20220828/f072d1cfd008423fa684c5321579e8e0.png
[Selection Sort - GeeksforGeeks]: https://www.geeksforgeeks.org/selection-sort/
[All Algorithms implemented in Python]: https://github.com/TheAlgorithms/Python