数据结构中的七大排序算法—1

       今天我们来讲解有关数据结构的知识，首先我们讲解数据结构的语言是C语言，使用的是vs2013编译器进行测试代码。

       在我们的生活中，很多东西都是有排序的，就比如下图，我们在逛淘宝时会先搜索我们想要的东西接着在通过不同的排序方式找到自己心仪的物品。那么，什么是排序呢？？

       我们给出定义：假设含有r个记录的序列为{},其对应的关键字分别为{}，需确定的一种排列，使其相应的关键字满足（非递减或非递增）关系，即使得序列成为一个按关键字有序的序列{}，这样的操作就叫做排序。

       那么现在，我们就可以将排序理解为，具有某种特征的序列，且特征以关键字的形式呈现。这是也就相当于我们排序的方式不同，比如：淘宝上的商品排序，可以按照价格的高低，商品的综合评价，商品的销量等等排序。那么，在我们数据结构中，排序也有很多种类。本次我将为大家带来其中的七种主要的排序。

冒泡排序

       本章我们要讲的是冒泡排序，简单选择排序和直接插入排序。由于我所讲述的知识不会涉及到C语言的解释，本章节并不适合零基础的小白观看。

       冒泡排序，一种最基础的排序算法。无论我们是以哪种编程语言开始学习的，在学习到循环和数组时，都会介绍这种最基础，最容易理解的排序算法，今天我们也将从此开始。

      冒泡排序：一种交换排序，它的基本思想是：两两比较相邻记录的关键字，如果与我们给定的关键字相反，则交换顺序，直到没有反序的记录为止。

       我想大家都比较好理解冒泡排序的实现方法，这里我们直接上一种比较简单的代码（升序排列）

void Bubblesort（slist *L)//对顺序表进行交换
{
  int len=L->Length;
  for(int i=0;i<len;i++)
  {
    for(int j=i+1;j<len;j++)
    {
      if(L.val[i]>L.val[j])
      {
        swap(l.val[i],l.val[j]);//满足交换条件,交换顺序表中数据
      }
    }
  }

       以上代码严格意义上不算冒泡排序的算法思想，只能算是最贱的交换排序。它的思路主要是固定左边的值，移动右边，直到找到比左边小的元素进行交换。

       这是最简单的，也是最容易理解的一种算法，但是我们会发现一个很致命的缺点：在排序1，3的顺序后，4的顺序并没有跟着往前走。这时，我们就可以想到，如果4在最前面而3在最后面，那么在3的排序完成后，很有可能4的位置就会到顺序表的末尾。由此可见这种算法的效率十分低。

现在，让我们来看真正的冒泡排序如何书写。

void Bubblesort（slist *L)
{
  int len=L->Length;
  for(int i=0;i<len;i++)
  {
    for(int j=len-1;j>=i;j--)
    {
      if(L.val[i]>L.val[j])//条件变更为j的前者和j相比较
      {
        swap(l.val[j],l.val[j+1]);//交换顺序表中数据
      }
    }
  }

       这里我们简单的讲解一下，我们将顺序表中最后一个元素和它的前一个元素做对比，如果最后一个元素大，那么它俩就会交换元素；最后一个元素往上走，直到出现比它还小的元素，接力！！让新的元素再往上走，这里注意：开始往上走的元素相当于离自己原本的位置更近了！！！这里的冒泡，就是指元素向上移动的过程很像水底向上冒得泡泡一样。

上图就是一趟冒泡排序的大致过程。

       那么，上述冒泡排序是否还能优化，当然是可以的。我们可以先假设，当我们的待排序列是{}，我们只需要交换2和1的元素即可；但是，如果使用上述代码，我们在交换玩2和1的为之后，还回去遍历后边的元素，这样就非常的浪费时间，这里我们只需要给冒泡的地方加一把锁，当我们在第二次遍历时，就可以判断之后的都是有序的，不需要遍历。

优化后的代码如下：

void Bubblesort（slist *l)
{
  bool flag=true;//加锁，用来判断之后是否需要交换元素
  int len=l->Length;
  for(int i=0;i<len&&flag;i++)//不满足条件，退出循环
  {
    flag=false;//初始为false
    for(int j=len-1;j>=i;j--)
    {
      if(L.val[i]>L.val[j])
      {
        swap(l.val[j],l.val[j+1]);
        flag=true;
      }
    }
  }

       现在，我们来分析一下冒泡排序的时间复杂度。在最好的情况，就是序列排序正确，我们只需要遍历一次就可以完成，即。在最坏的情况下，就是整个序列逆置，正好与我们想要的结果完全相反，此时我们需要比较次，并作等级数量级的记录移动。由此可见，冒泡排序的时间复杂度为

简单选择排序

       接下来我们来说点易懂的，对于我们普通人，肯定不喜欢上述的上述的冒泡排序，通过不断地交换，从而得到最终的排列顺序；我们肯定更喜欢那种一次就能定位好一个元素的排序方式，这样就有人研究出了基于这种思想的简单选择排序。

简单选择排序：通过次关键字间的比较，从个记录中选出关键字最小的记录，并和第个记录交换。基本思想是每一趟在个记录中选取关键词最小的记录作为有序序列的第个记录。

排序的基本思想我们都了解了，接下来我们开始看代码

void *SelectSort(SqList *l)//对顺序表l进行简单选择排序
{
  for(int i=0;i<l.length;i++)
  {
    int min=i;//开始min标记最左边的元素为最小值
    for(int j=i+1;j<l.length;j++)
    {
      if(l.val[min]>l.val[j])
      { 
        min=j;//表示后面有元素小于最小值，替换最小值下标
      }
    }
    if(i!=min)//防止重复交换
    {
      swap(l.val[min],l.val[i]);
    }
  }
]

       代码非常好理解，如果大家还是不能很好的理解，那么我们画图做出解释：

       现在，我们来分析一下简单选择排序的时间复杂度。从简单选择排序的过程来看，它最大的特点就是交换数据次数较少，这样节约了不少时间；但同时它的缺点是很明显的，无论序列的排序如何改变，简单选择排序都会进行次的比较。所以，最终是时间复杂程度为。

直接插入排序

       大家都应该玩过麻将吧，当我们首先拿到13张牌，在我们有三条和五条时，如果我们再摸一张为四条，我们一定会插入三五条中；假设我们运气很好，每次都能插入对应的位置，那么我们牌的顺序会越来越好，这就是我们要将到直接插入发的思想。

直接插入法排序法：将一个记录插入到已经排序好的有序列表中，从而得到一个新的序列，记录数增1的有序列表。

我们先来使用图片来为大家讲解直接插入排序法的思想：

       上述两步直接交代了直接插入法的过程步骤，重复上述步骤就能得到一个递增的排序序列。接下来我们来书写相关代码：

void InsertSort(Sqlist *l)//对顺序表l进行排序
{
  for(int i=2;i<l.length;i++)
  {
    if(l.val[i]<l.val[i-1])
    {
      l.val[0]=l.val[i];//储存i处的元素
      for(int j=i-1;l.val[j]>l.val[0];j--)
      {
        l.val[j+1]=l.val[j];//找到对应的插入位置
      }
      l.val[j+1]=l.val[0];//插入
    }
  }
}

       上方的代码希望大家可以动手自己打几遍，或者我们可以手写几遍；多过几遍代码流程，我们会对代码的思想理解更透彻。

       现在，我们来分析一下直接插入排序法的复杂程度。从空间复杂程度来看，它不同于前两个算法，不需要辅助空间；直接插入排序需要一个空间用来保存我们要插入的元素。从时间复杂程度来看，最好的情况就是完全递增数列，我们只需要比较次，时间复杂度为;最坏的情况就是完全逆置，这时我们需要比较次，时间复杂程度就变为。因此，根据时间复杂度计算规则，最终的时间复杂程度为。

       今天的内容就到这里，希望可以给你带来收获，给个三连支持一下萌新吧，感谢感谢！！！！