第47课 选择排序和插入排序

#ifndef SORT_H
#define SORT_H

#include "Object.h"

namespace DTLib
{

class Sort : public Object
{
private:
    //私有化构造函数、赋值、拷贝构造等函数
    Sort();
    Sort(const Sort&);
    Sort& operator=(const Sort&);

    template <typename T>
    static void Swap(T& a, T& b)
    {
        T temp(a);
        a = b;
        b = temp;
    }

public:
    //选择排序（O(n*n),不稳定）
    template <typename T>
    static void Select(T array[], int len, bool min2max = true)
    {
        for(int i=0; i<len-1; i++){

            //第i趟。有序区为[0,i-1],无序区为[i, len-1]
            //1.找到无序区的首元素: array[i]

            //2.从无序区中找到最小值
            int min = i; //假设：无序区中最小元素的为首元素
            for(int j=i+1; j<len; j++){
                if (min2max ? (array[j] < array[min]) : (array[j] > array[min])){
                    min = j;
                }
            }

            //3. 交换无序区中首元素和最小值的位置，将最小值放在无序区的首部
            if(i != min){
                Swap(array[i], array[min]);
            }
        }
    }

    //插入排序（O(n*n), 稳定）
    template <typename T>
    static void Insert(T array[], int len, bool min2max = true)
    {
        //1. 初始状态有序区为[0],无序区为[1..n-1]
        for(int i=1; i<len; i++){ //注意，从1开始，因为要将无序区的每个元素插入到有序区中

            //有序区[0, i-1]，无序区[i, n-1]
            //2. 取出无序区首元素，从有序区后面往前面比较依次与其比较
            T e = array[i]; //无序区首元素
            int k = i; //k记录着e最终应该放置的位置
            for(int j=i-1; (j>=0) && (min2max ? (e<array[j]) : (e>array[j]));j--){
                //3. 边比较边移动元素，e最终的位置记录在k中
                array[j+1] = array[j]; //将a[j]往后移一位
                k = j;
            }

            //4. 将e放置下来
            if(k != i){
                array[k] = e;
            }
        }
    }


};

}

#endif // SORT_H

#include <iostream>
#include "Sort.h"

using namespace std;
using namespace DTLib;

int main()
{

    int array[]={49,38,65,97,76,13,49,27};
    int len = sizeof(array)/sizeof(*array);

    Sort::Insert(array, len,false);//降序排序

    for(int i=0; i<len; i++){
        cout << array[i] << " ";
    }
    cout << endl;


    return 0;
}
/*测试结果
97 76 65 49 49 38 27 13
*/