简单选择排序（数据结构）

Dear 丶 2024-04-23 20:12 71阅读 0赞

![在这里插入图片描述][e79d5843b9044c7dbd0cd9b6a25d79d7.png]  
选择排序可分为简单选择排序和堆排序。

#### 简单选择排序 ####

![在这里插入图片描述][6085ef0f3fe84763b3a1e7de3af69655.png]

#### C++代码实现 ####

#include <iostream>
    #include <stdlib.h>
    
    using namespace std;
    
    void swap(int &a, int &b) {
        
        int temp = a;
        a = b;
        b = temp;
    }
    
    void SelectSort(int A[], int n) {
        
        for(int i = 0;i < n-1;i++) {
         // 必须要进行n-1趟
            int min = i; // 记录最小元素的位置
            for(int j = i+1;j < n;j++) {
        
                if(A[j] < A[min]) {
        
                    min = j; // 更新最小元素位置
                }
            }
            if(min != i) {
        
                swap(A[i], A[min]);
            }
        }
    }
    
    void PrintArray(int A[], int n) {
        
        for(int i = 0;i < n;i++) {
        
            cout << A[i] << " ";
        }
        cout << endl;
    }
    
    int main() {
        
        int A[] = {
        1,8,9,7,6,5,4,3,2};
        cout << "排序前：";
        PrintArray(A, 9);
    
        SelectSort(A, 9);
        cout << "排序后：";
        PrintArray(A, 9);
    }

#### 复杂度分析 ####

![在这里插入图片描述][b996750efa2b400eb6ca78734f90d8b2.png]  
![在这里插入图片描述][f323ebf563fe4d98ab3d9de4f6e06ac5.png]

> 注：以上图片来自B站王道数据结构截图

[e79d5843b9044c7dbd0cd9b6a25d79d7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/fd874021e20c46ed80fb3fba47a4add7.png
[6085ef0f3fe84763b3a1e7de3af69655.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/511c77e46c9d4118bcb0678e2956e53b.png
[b996750efa2b400eb6ca78734f90d8b2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/87e791cc2a484948a90442a4a382be84.png
[f323ebf563fe4d98ab3d9de4f6e06ac5.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/23/ae598de431b846b19fb50580042c4274.png