算法解析之选择排序

选择排序

算法思路：
1、整个序列分为待排序部分和已排序部分
2、遍历待排序部分找到最小值，与待排序部分的第一个值交换
3、重复2直到整个序列有序

C++：

//交换值
void swap(int *a,int *b){
    int temp = *a;
    *a = *b;
    *b = temp;
}
//选择排序
void selectionSort(int arr[],int n){
//重复2步骤，重复n-1，交换n-1次
    for (int i = 0; i < n-1; i++) {
        //需要先用一个变量记录最小值索引，初始值为重复次数i（未排序部分的第一个值）
        int minIndex = i;
        //2步骤，从待排序部分找出最小值的序列
        for (int j = i; j < n; j++) {
            if (arr[j]<arr[minIndex]) {
                minIndex = j;
            }
        }
        //交换
        swap(&arr[i], &arr[minIndex]);
    }
    //整个序列有序
}

加入模板函数（泛型）更加C++：

template <typename T>
void swap(T *a,T *b){
    T temp = *a;
    *a = *b;
    *b = temp;
}

template <typename T>
void selectionSort(T arr[],int n){
    for (int i = 0; i < n; i++) {
        int minIndex = i;
        for (int j = i; j < n; j++) {
            if (arr[j]<arr[minIndex]) {
                minIndex = j;
            }
        }
        swap(&arr[i], &arr[minIndex]);
    }
}

如果要排序自定义类型，必须重载比较操作符<，>