选择、插入排序、sort

#音视频开发之旅（26) 算法系列## 目录

选择排序
插入排序
STL中sort的实现
资料
收获

这一篇我们一起来学习实践下选择排序和插入排序，然后再一起分析下CPP的STL中排序算法的实现，结束排序算法的阶段。

一、选择排序

假设一个下标对应的数组内容值为最小值（一般使用未确定的第一个），然后依次用这个值和后面的所有值进行对比大小，如果后面的值小于该值，先记录最小值的位置以及值，在不断后后续值进行比较，一次循环遍历后，根据最小值和初始最小值相比十分有变化，如果有则进行交换。
下标加1，重复第一步

实现比较简单，我们就不画图，分析了，代码中加了详细的注释

代码语言：txt复制

#include <iostream>

代码语言：txt复制

#include<array>

代码语言：txt复制

#include<algorithm>

代码语言：txt复制

using namespace std;

代码语言：txt复制

void printSortArray(int myarray[],int size){

代码语言：txt复制

        for(int k=0; k<size; k  )

代码语言：txt复制

            cout<<myarray[k]<<" ";

代码语言：txt复制

        cout<<endl;

代码语言：txt复制

void swap(int *a,int i,int j)

代码语言：txt复制

    int tmp = a[i];

代码语言：txt复制

    a[i] = a[j];

代码语言：txt复制

    a[j]=tmp;

代码语言：txt复制

void selectSort(int *a,int length)

代码语言：txt复制

    for(int i = 0;i<length;i  )

代码语言：txt复制

        //先假设第一个元素为最小值，通过外部遍历记录

代码语言：txt复制

        int min = a[i];

代码语言：txt复制

        int minPos = i;

代码语言：txt复制

        for(int j =i 1;j<length;j  )

代码语言：txt复制

            //进行一轮的和上述假设的最小值进行大小对比。如果出现后续的值比假定的最小值还小，则把该值赋值给最小值，

代码语言：txt复制

            if(min>a[j])

代码语言：txt复制

                min =a[j];

代码语言：txt复制

                minPos = j;

代码语言：txt复制

        //一轮对比完成之后，检查最小值的下标是否发生变化，如果是则进行交换

代码语言：txt复制

        if(i !=minPos)

代码语言：txt复制

            swap(a,i,minPos);

代码语言：txt复制

        //一轮过后，最右侧的坑位被当轮的最小值只用，然后再循环确定后续的坑位的值

代码语言：txt复制

int main(void) {

代码语言：txt复制

    //用一位数组，表示一个完全二叉树，可以从任意节点拿到它的父节点 和它的左右子节点

代码语言：txt复制

   int myarray[] ={6,7,1,2,10,5,8,3,4};

代码语言：txt复制

   int size = sizeof(myarray)/sizeof(myarray[0]) ;

代码语言：txt复制

   cout<<"size="<<size<<endl;

代码语言：txt复制

   selectSort(myarray,size);

代码语言：txt复制

   printSortArray(myarray,size);

代码语言：txt复制

    return 0;

代码语言：txt复制

看到选择排序，很容易想到我们前面学习实践的冒泡排序，他们之间有什么区别呐？

冒泡排序事两两相邻对比，每次对比都可能触发交互，冒泡排序是通过数找位置。

选择排序则是先假设一个为最小值，然后用这个值和后面所有的内容一一进行比较大小，每轮进行一次交换。选择排序是先确定位置，在找值。

他们的优点都是比较简单，但是缺点也都很明显，时间复杂度是O(n^2)。选择排序还会破环原来顺序的稳定性（即

有相同值时，通过选择排序相同值的前后顺序会被破坏）。

二、插入排序

插入排序就像我们打打牌时，手里的牌是已经排序好的，起一张新的牌插入到已有的有序牌中的适当位置，为了给要插入的元素腾出空间，需要讲其余大于要插入值的元素，在插入前都向右移动一个位置。

插入适合的应用场景：对非随机的（即有序的）队列进行插入，效率非常高。

下面我们通过画图一步步的开下插入排序的过程

实现如下

代码语言：txt复制

#include <iostream>

代码语言：txt复制

#include<array>

代码语言：txt复制

#include<algorithm>

代码语言：txt复制

using namespace std;

代码语言：txt复制

void printSortArray(int myarray[],int size){

代码语言：txt复制

        for(int k=0; k<size; k  )

代码语言：txt复制

            cout<<myarray[k]<<" ";

代码语言：txt复制

        cout<<endl;

代码语言：txt复制

void swap(int *a,int i,int j)

代码语言：txt复制

    int tmp = a[i];

代码语言：txt复制

    a[i] = a[j];

代码语言：txt复制

    a[j]=tmp;

代码语言：txt复制

void insertSort(int *a,int length)

代码语言：txt复制

    //数组下标从1开始和前面的值进行对比大小

代码语言：txt复制

    int i,j,tmp;

代码语言：txt复制

    for(i=1;i<length;i  ){

代码语言：txt复制

        int tmp= a[i];

代码语言：txt复制

        for (j = i-1; j>=0; j--)

代码语言：txt复制

            //如果后面的小于前面的有序列表中的某位置的值，则把当前位的值向后移动一位，依次循环

代码语言：txt复制

            if(tmp< a[j]){

代码语言：txt复制

                a[j 1] = a[j];

代码语言：txt复制

            } else {

代码语言：txt复制

                break;

代码语言：txt复制

       //跳出循环后，把tmp在赋值给要插入的地方

代码语言：txt复制

       a[j 1] = tmp;

代码语言：txt复制

int main(void) {

代码语言：txt复制

    //用一位数组，表示一个完全二叉树，可以从任意节点拿到它的父节点 和它的左右子节点

代码语言：txt复制

   int myarray[] ={6,7,1,2,10,5,8,3,4};

代码语言：txt复制

   int size = sizeof(myarray)/sizeof(myarray[0]) ;

代码语言：txt复制

   cout<<"size="<<size<<endl;

代码语言：txt复制

   insertSort(myarray,size);

代码语言：txt复制

   printSortArray(myarray,size);

代码语言：txt复制

    return 0;

代码语言：txt复制

三、STL中排序算法的实现

通过这四篇关于排序算法的的学习，我们理解了基础的选择排序、插入排序、冒泡排序、快速排序以及堆排序的原理和实现。下面我们来看下CPP中STL的排序算法的具体实现

源码地址：[https://gcc.gnu.org/onlinedocs/libstdc /libstdc -html-

USERS-4.4/a01347.html](https://links.jianshu.com/go?to=https://gcc.gnu.org/onlinedocs/libstdc++/libstdc++-html-

USERS-4.4/a01347.html)

代码语言：txt复制

template<typename _RandomAccessIterator>

代码语言：txt复制

05206     inline void

代码语言：txt复制

05207     sort(_RandomAccessIterator __first, _RandomAccessIterator __last)

代码语言：txt复制

05208     {

代码语言：txt复制

05209       typedef typename iterator_traits<_RandomAccessIterator>::value_type

代码语言：txt复制

05210     _ValueType;

代码语言：txt复制

05212       // concept requirements

代码语言：txt复制

05213       __glibcxx_function_requires(_Mutable_RandomAccessIteratorConcept<

代码语言：txt复制

05214         _RandomAccessIterator>)

代码语言：txt复制

05215       __glibcxx_function_requires(_LessThanComparableConcept<_ValueType>)

代码语言：txt复制

05216       __glibcxx_requires_valid_range(__first, __last);

代码语言：txt复制

05218       if (__first != __last)

代码语言：txt复制

05219     {

代码语言：txt复制

05220       std::__introsort_loop(__first, __last,

代码语言：txt复制

05221                 std::__lg(__last - __first) * 2);

代码语言：txt复制

05222       std::__final_insertion_sort(__first, __last);

代码语言：txt复制

05223     }

代码语言：txt复制

05224     }

__lg函数是计算递归深度，用来控制分割恶化，当递归深度达到该值改用堆排序，因为堆排序是时间复杂度恒定为nlogn

代码语言：txt复制

/// This is a helper function for the sort routines.  Precondition: __n > 0.

代码语言：txt复制

02308   template<typename _Size>

代码语言：txt复制

02309     inline _Size

代码语言：txt复制

02310     __lg(_Size __n)

代码语言：txt复制

02311     {

代码语言：txt复制

02312       _Size __k;

代码语言：txt复制

02313       for (__k = 0; __n != 0; __n >>= 1)

代码语言：txt复制

02314       __k;

代码语言：txt复制

02315       return __k - 1;

代码语言：txt复制

02316     }

快速排序的实现如下：

代码语言：txt复制

02242   /// This is a helper function for the sort routine.

代码语言：txt复制

02243   template<typename _RandomAccessIterator, typename _Size>

代码语言：txt复制

02244     void

代码语言：txt复制

02245     __introsort_loop(_RandomAccessIterator __first,

代码语言：txt复制

02246              _RandomAccessIterator __last,

代码语言：txt复制

02247              _Size __depth_limit)

代码语言：txt复制

02248     {

代码语言：txt复制

02249       typedef typename iterator_traits<_RandomAccessIterator>::value_type

代码语言：txt复制

02250     _ValueType;

代码语言：txt复制

      //区间数目大于_S_threshold采用快速排序

代码语言：txt复制

02252       while (__last - __first > int(_S_threshold))

代码语言：txt复制

02253     {

代码语言：txt复制

           //达到指定递归深度，改用堆排序

代码语言：txt复制

02254       if (__depth_limit == 0)

代码语言：txt复制

02255         {

代码语言：txt复制

02256           _GLIBCXX_STD_P::partial_sort(__first, __last, __last);

代码语言：txt复制

02257           return;

代码语言：txt复制

02258         }

代码语言：txt复制

02259       --__depth_limit;

代码语言：txt复制

02260       _RandomAccessIterator __cut =

代码语言：txt复制

02261         std::__unguarded_partition(__first, __last,

代码语言：txt复制

02262                        _ValueType(std::__median(*__first,

代码语言：txt复制

02263                                 *(__first

代码语言：txt复制

02264                                     (__last

代码语言：txt复制

02265                                      - __first)

代码语言：txt复制

02266                                   / 2),

代码语言：txt复制

02267                                 *(__last

代码语言：txt复制

02268                                   - 1))));

代码语言：txt复制

02269       std::__introsort_loop(__cut, __last, __depth_limit);

代码语言：txt复制

02270       __last = __cut;

代码语言：txt复制

02271     }

代码语言：txt复制

02272     }

插入排序部分的实现：

代码语言：txt复制

/// This is a helper function for the sort routine.

代码语言：txt复制

02171   template<typename _RandomAccessIterator>

代码语言：txt复制

02172     void

代码语言：txt复制

02173     __final_insertion_sort(_RandomAccessIterator __first,

代码语言：txt复制

02174                _RandomAccessIterator __last)

代码语言：txt复制

02175     {

代码语言：txt复制

02176       if (__last - __first > int(_S_threshold))

代码语言：txt复制

02177     {

代码语言：txt复制

02178       std::__insertion_sort(__first, __first   int(_S_threshold));

代码语言：txt复制

02179       std::__unguarded_insertion_sort(__first   int(_S_threshold), __last);

代码语言：txt复制

02180     }

代码语言：txt复制

02181       else

代码语言：txt复制

02182     std::__insertion_sort(__first, __last);

代码语言：txt复制

02183     }

代码语言：txt复制

02093   /// This is a helper function for the sort routine.

代码语言：txt复制

02094   template<typename _RandomAccessIterator>

代码语言：txt复制

02095     void

代码语言：txt复制

02096     __insertion_sort(_RandomAccessIterator __first,

代码语言：txt复制

02097              _RandomAccessIterator __last)

代码语言：txt复制

02098     {

代码语言：txt复制

02099       if (__first == __last)

代码语言：txt复制

02100     return;

代码语言：txt复制

02102       for (_RandomAccessIterator __i = __first   1; __i != __last;   __i)

代码语言：txt复制

02103     {

代码语言：txt复制

02104       typename iterator_traits<_RandomAccessIterator>::value_type

代码语言：txt复制

02105         __val = *__i;

代码语言：txt复制

02106       if (__val < *__first)

代码语言：txt复制

02107         {

代码语言：txt复制

02108           std::copy_backward(__first, __i, __i   1);

代码语言：txt复制

02109           *__first = __val;

代码语言：txt复制

02110         }

代码语言：txt复制

02111       else

代码语言：txt复制

02112         std::__unguarded_linear_insert(__i, __val);

代码语言：txt复制

02113     }

代码语言：txt复制

02114     }

gcc https c++ html 编程算法

0 人点赞