技术交流QQ群:1027579432，欢迎你的加入！

一、选择排序算法个人理解

  • 如果有N个元素需要排序，首先从N个元素中找到最小的那个元素，然后与索引ix=0位置上的元素进行交换(如果没有比原来索引ix=0位置上的元素小就不用交换),接着再从剩下的N-1个元素中找出最小的元素，再与索引ix=1位置上的元素进行交换；之后，再从剩下的N-2个元素中找出最小的元素，再与索引ix=2位置上的元素进行交换,.....重复上面的操作，一直到完全排序完成为止。具体排序过程见下图：


    选择排序.jpg

二、选择排序算法代码实现(C++版本)

#include "iostream"

using namespace std;

void printSequence(int a[], int size);
void selectSort(int a[], int size);

/*        选择排序      */
int main(){
    const int SIZE = 7;
    int a[SIZE] = {5, 7, 2, 8, 9, 1, 4};
    cout << "选择排序前: ";
    printSequence(a, SIZE);

    selectSort(a, SIZE);

    cout << "选择排序后: ";
    printSequence(a, SIZE);
    return 0;
}


void printSequence(int a[], int size){
    for (int i = 0; i <= size - 1; i++){
        cout << a[i] << " ";
    }
    cout << endl;
}

// 选择排序
void selectSort(int a[], int size){
    int minIndex, temp;
    for (int ix = 0; ix < size - 1; ix++){  // 通过外层for循环对索引进行遍历，保存最小元素所对应的索引
        minIndex = ix; // 外层for循环开始循环时，将minIndex初始化为数组第一个元素的索引
        for (int jx = ix + 1; jx < size; jx++){ // 通过内层for循环找出最小元素，并把最小元素所对应的索引赋值给minIndex
            if (a[jx] < a[minIndex])
                minIndex = jx;
        }
        temp = a[ix];
        a[ix] = a[minIndex];
        a[minIndex] = temp;
    }
}
  • STL实现 
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;


// 打印元素
void PrintV(vector<int>& v){
    for(auto &e: v){
        cout << e << ' ';
    }
    cout << endl;
}

// 选择排序
void SelectSort(vector<int>& v){
    int n = v.size();
    for(int i=0; i < n-1;++i){
        int min = i;
        for(int j=i+1; j < n; ++j){
            if(v[j] < v[min]){
                min = j;
            }
        }

        if(i != min){
            swap(v[i], v[min]);
        }

    }
}


// 函数模板实现
template <typename T>
void SelectSort1(vector<T>& arr){
    int n = arr.size();
    for(int i=0; i < n-1; ++i){
        int min = i;
        for(int j=i+1; j < n; ++j){
            if(arr[j] < arr[min]){
                min = j;
            }
        }

        if(i != min){
            swap(arr[i], arr[min]);
        }
    }
}


int main(){
    vector<int> v{7, 30, 16, 4, 1, 2, 9};
    cout << "选择排序前: ";
    PrintV(v);
    SelectSort(v);
    cout << "选择排序后: ";
    PrintV(v);
    return 0;
}

三、结果

结果.png

四、选择排序时间复杂度总结：

  • 平均时间复杂度：O(n**2)
  • 最好情况：O(n**2)
  • 最坏情况：O(n**2)
  • 空间复杂度：O(1)
  • 稳定性：不稳定