47_选择排序和插入排序

关键词：选择排序、插入排序

0. 选择排序

每次（例如第i次，i = 0, 1, 2, ..., n-2）从后面n-i个待排的数据元素中选出关键字最小的元素，作为有序元素序列第i个元素。

选择排序原理图

template < typename T >
    static void Select(T array[], int len, bool min2max = true)     // O(n^2)
    {
        for(int i=0; i<len; ++i)
        {
            int min = i;

            for(int j = i+1; j<len; ++j)
            {
                if( min2max ? (array[min] > array[j]) : (array[min] < array[j]) )
                {
                    min = j;
                }
            }

            if( min != i )
            {
                Swap(array[i], array[min]);
            }
        }
    }

1. 插入排序

思想：当插入第i（i>=1）个数据元素时，前面的v[0], v[1], ...,v[i-1]已经排好序，这时，用v[i]的关键字与v[i-1],...,v[0]的关键字进行比较，找到位置后将v[i]插入，原来的位置上的对象向后顺移。

template < typename T >
    static void Insert(T array[], int len, bool min2max = true)
    {
        for(int i=1; i<len; ++i)
        {
            int pos = i;
            T value = array[i];

            for(int j=i-1;
                j>=0 && (min2max ? (array[j]>value) : (array[j]<value));
                --j)
            {
                array[j+1] = array[j];
                pos = j;
            }

            if( pos != i )
            {
                array[pos] = value;
            }
        }
    }

2. 小结

• 选择排序每次选择未排元素中的最小元素
• 插入排序每次将第i个元素插入前面i-1个已排元素中
• 选择排序是不稳定的排序法，插入排序是稳定的排序方法
• 选择排序和插入排序的时间复杂度为O(n^2)

声明：此文章仅是本人在学习狄泰学院《数据结构实战开发教程》所做的笔记，文章中包含狄泰软件资料内容，一切版权归狄泰软件所有！
实验环境：ubuntu10 + Qt Creator2.4.1 + Qt SDK 4.7.4