C++排序算法练习(冒泡排序,选择排序,插入排序)

针对排序算法的一次练习,包含冒泡排序,选择排序,插入排序,修正了上一次的冒泡排序算法,并针对自己有疑问的地方增加了详细的注解;

#include <iostream>
using namespace std;
template <typename T>
/*冒泡排序算法步骤
比较相邻的元素。如果第一个比第二个大，就交换他们两个。
对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这步做完后，最后的元素会是最大的数。
针对所有的元素重复以上的步骤，除了最后一个。持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。*/
void bubble_sort(T arr[],size_t n)
{
    int cnt=0;
    for(auto i=0;i<n-1;i++) //在这里,遍历次数为什么是n-1次?而不是n次呢?因为n个元素,其实只需要比较n-1次,而又从0开始索引.这里决定比较次数.
    {
        for(auto j=0;j<n-1-i;j++)//在这里,为什么要-i呢,因为每一轮比较,最后都会有一个值在末尾,这个值是所有元素中的最大值,所以无需再参与比较.去掉后可减少重复带来的效率损耗.
        {
            cnt++;
            if(arr[j]>arr[j+1])
            {
                swap(arr[j],arr[j+1]);
            }
        }
    }
    cout<<"times:"<<cnt<<endl;
    for(auto s=0;s<n;++s)
        cout<<arr[s]<<" "<<endl;
    cout<<endl;
}
/*选择算法步骤
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
重复第二步，直到所有元素均排序完毕.*/
template <typename T>
void select_sort(T*arr,size_t sz)
{
    int cnt=0;//打印比较次数,用于比较算法
    for(auto i=0;i<sz-1;++i) //在这里,遍历次数为什么是n-1次?而不是n次呢?因为n个元素,其实只需要比较n-1次,而又从0开始索引.这里决定比较次数.
    {
        int min =i;//记录比较后的最小值的索引,初始值默认为第一个元素对应的索引[0];
        for(auto j=i+1;j<sz;++j)//这里为什么用j=i+1?这是因为第一个位置已经用来存放最小值,j<sz表示遍历到最后一个元素.
        {
            cnt++;
            if(arr[j]<arr[min])//用当前元素和最小元素进行比较,如果小于最小元素,则将此元素的索引赋给记录最小值索引的变量;
                min=j;
        }
        swap(arr[i],arr[min]);//遍历一次,更新最小值(将遍历得到的最小值传给保存最小值的元素,这里是进行交换,一个意思).
    }
    cout<<"times:"<<cnt<<endl;
    for(auto s=0;s<sz;++s)
        cout<<arr[s]<<" "<<endl;
    cout<<endl;
}
/*插入算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）*/
template<typename T>
void insert_sort(T*arr,size_t sz)
{
    for(auto i=1;i<sz;++i){//第一个元素保留下来,从第二个元素进行遍历,所以遍历总数应该是sz-1;
        T key=arr[i];//用来拿出来和已排序的有序数列进行比较的值,在这里,这个值是每次遍历时,待排序元素的第一个值.
        auto j=i-1;//确定已排序序列的最后一个元素,它是遍历的起始位置;
        for(;j>=0,key<arr[j];j--) //从后面向前遍历,如果索引>=0,并且当前遍历的元素大于从待排序的无序序列中拿过来的元素,则继续遍历.
        {
            arr[j+1]=arr[j];//将当前遍历的元素值向后退,给需要插入的元素留一个位置.
        }
        arr[j+1]=key;//将待排序的元素放在待排序第一个位置.
    }
    for(auto s=0;s<sz;++s)
        cout<<arr[s]<<" "<<endl;
    cout<<endl;
}

int main()
{
    int arr[] {4,1,3,2,5,6,7,3,5,12,33,54};
    size_t sz=sizeof (arr)/sizeof(int);
    bubble_sort(arr,sz);
    select_sort(arr,sz);
    insert_sort(arr,sz);

    return 0;
}