基础的排序算法

算法复杂度

• 一个算法是由控制结构（顺序、分支和循环3种）和原操作（指固有数据类型的操作）构成的
• 同一问题可用不同算法解决，而一个算法的质量优劣将影响到算法乃至程序的效率。
• 算法分析的目的在于选择合适算法和改进算法。一个算法的评价主要从时间复杂度和空间复杂度来考虑。

时间复杂度

• 一个算法中的语句执行次数。记为T(n),n称为问题的规模;
  若存在某个函数f(n)，当 n –> ∞时，T(n) / f(n) 为不等于0的常数，则称f(n)是T(n)的同数量级函数。记为T(n) = O(f(n))；称O(f(n))为算法的渐进时间复杂度，简称时间复杂度。
• 常见的时间复杂度

常数阶	对数阶	线性阶	线性对数阶	平方阶	立方阶	K次方阶	指数阶
O(1)	O(log2^n)	O(n)	O(nlog2^n)	O(n^2)	O(n^3)	O(n^k)	O(2^n)

随着问题规模n的不断增大，上述时间复杂度不断增大，算法的执行效率越低。

空间复杂度

一个算法的空间复杂度S(n)定义为该算法所耗费的存储空间，它也是问题规模n的函数。空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度。

• 存储算法本身所占用的存储空间
• 算法的输入输出数据所占用的存储空间
• 算法在运行过程中临时占用的存储空间

冒泡排序

冒泡排序是最基础的一种排序算法，让序列元素像汽泡一样”浮”上来
冒泡排序本质在于交换元素，每次判断两个相邻元素的大小交换位置，直到剩余元素为0时。

算法步骤

• 比较相邻的元素。如果第一个比第二个大，则交换
• 整个过程进行n个元素-1次

  代码示例

  int main(){
  //定义一个数组
  int a[10] = {2,0,1,9,4,3,0};
  //遍历n-1数组
  for (int i =0;i<=6;i++){< span>    //第i次从a[0]~a[n-i]与他们下一个数比较    for(int j=0;j<6-i;j++){< span>        //判断相邻大小进行交换        if(a[j]>a[j+1]){            //中间变量temp            int temp = a[j];            a[j] = a[j+1];            a[j+1] = temp;        }    }}//打印输出for(int i=0;i<7;i++){< span>    printf("%d",a[i]);}return 0;}
      //第i次从a[0]~a[n-i]与他们下一个数比较
      for(int j=0;j<6-i;j++){< span>        //判断相邻大小进行交换        if(a[j]>a[j+1]){            //中间变量temp            int temp = a[j];            a[j] = a[j+1];            a[j+1] = temp;        }    }}//打印输出for(int i=0;i<7;i++){< span>    printf("%d",a[i]);}return 0;}
          //判断相邻大小进行交换
          if(a[j]>a[j+1]){
              //中间变量temp
              int temp = a[j];
              a[j] = a[j+1];
              a[j+1] = temp;
          }
      }
  }
  //打印输出
  for(int i=0;i<7;i++){< span>    printf("%d",a[i]);}return 0;}
      printf("%d",a[i]);
  }
  
  return 0;
  }

输出结果：0 0 1 2 3 4 9

性能分析

• “正序”排列时，比较次数为n-1，所以最好情况下的时间复杂度为O(n)；
• “逆序”排序时，比较次数为n(n-1)/2，所以冒泡排序在最坏情况下的时间复杂度为O(n^2)

• 过程中需要一个临时变量temp，所需要的额外空间为1，空间复杂度则为O(1)。
• 元素交换时，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。

时间复杂度	最好情况	最坏情况	平均复杂度	空间复杂度	稳定性
冒泡排序	O(n)	O(n^2)	O(n^2)	O(1)	稳定

---

---

选择排序

简单选择排序就是选择元素放置
选择无序序列中最小（大）的元素放入有序序列中，进行n个元素次数的操作

算法步骤

• 初始有序区和无序区
• 从a[0]开始判断无序序列中最小的元素
• 与a[0]交换，记录为有序序列
• 进行n个元素次，直到全部有序

代码示例

int main(){
    //定义一个数组
    int a[10] = {2,0,1,9,4,3,0};
    //进行n次操作
    for(int i = 0;i<=6;i++){< span>        //k为最小值数组下标        int k = i;        //遍历无序序列        for(int j = i;j<=6;j++){< span>            //选择最大元素            if(a[j]                //交换i和j的下标                k=j;            }        }        //中间变量temp        int temp = a[i];        a[i] = a[k];        a[k] = temp;    }    //打印输出    for(int i=0;i<7;i++){< span>        printf("%d",a[i]);    }    return 0;}
        //k为最小值数组下标
        int k = i;
        //遍历无序序列
        for(int j = i;j<=6;j++){< span>            //选择最大元素            if(a[j]                //交换i和j的下标                k=j;            }        }        //中间变量temp        int temp = a[i];        a[i] = a[k];        a[k] = temp;    }    //打印输出    for(int i=0;i<7;i++){< span>        printf("%d",a[i]);    }    return 0;}
            //选择最大元素
            if(a[j]                //交换i和j的下标                k=j;            }        }        //中间变量temp        int temp = a[i];        a[i] = a[k];        a[k] = temp;    }    //打印输出    for(int i=0;i<7;i++){< span>        printf("%d",a[i]);    }    return 0;}
                //交换i和j的下标
                k=j;
            }
        }
        //中间变量temp
        int temp = a[i];
        a[i] = a[k];
        a[k] = temp;
    }
    //打印输出
    for(int i=0;i<7;i++){< span>        printf("%d",a[i]);    }    return 0;}
        printf("%d",a[i]);
    }
    return 0;
}

输出结果：9 4 3 2 1 0 0

性能分析

• 简单选择排序表现最稳定的排序算法之一，无论正序倒序无序数据进去都是O(n2)的时间复杂度
• 过程中需要一个临时变量temp，所需要的额外空间为1，空间复杂度则为O(1)。
• 元素交换时，相同元素的前后顺序发生改变，所以冒泡排序是一种不稳定的排序算法。

时间复杂度	最好情况	最坏情况	平均复杂度	空间复杂度	稳定性
选择排序	O(n^2)	O(n^2)	O(n^2)	O(1)	不稳定

---

---

直接插入排序

通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

算法步骤

• 序列第一个元素已经有序
• 取未排序数据为新元素
• 从后向前比较是否比新元素大
• 在其后插入新元素
• 反复n-1趟排序

  代码示例

  int main(){
      int a[10] = {2,0,1,9,4,3,0};
      //进行n-1趟排序
      for(int i=1;i<=6;i++){< span>        //temp存放        int temp = a[i];        //j        int j = i-1;        //temp小于前一个元素        while(j>=0&&temp            //把序列后移一位            a[j] = a[j-1];            j--;        }        //插入位置为j        a[j] = temp;    }     //打印输出    for(int i=0;i<7;i++){< span>        printf("%d",a[i]);    }    return 0;}```  > 输出结果：0 0 1 2 3 4 9## 性能分析 - 简单插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n)。  - 在最坏情况下，时间复杂度依然为O(n2)。  - 但是在数组元素随机排列的情况下，插入排序还是要优于上面两种排序的。  - 过程中需要一个临时变量temp，所需要的额外空间为1，空间复杂度则为O(1)。  - 元素交换时，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。  | 时间复杂度 | 最好情况 | 最坏情况 | 平均复杂度 | 空间复杂度 | 稳定性 || :-: | :-: | :-: | :-: | :-: ||简单插入排序|O(n)|O(n^2)|O(n^2)|O(1)|稳定|    # **希尔排序** shellSort，又称“缩小增量排序”，是1959年D.L.shell提出的。## 算法步骤 - 先将整个待排序列分割成若干个子序列分别进行直接插入排序  - 然后依次缩减增量再进行排序  - 待整个序列中的元素基本有序时- 在对全体元素进行一次直接插入排序    ## 代码示例
          //temp存放
          int temp = a[i];
          //j
          int j = i-1;
          //temp小于前一个元素
          while(j>=0&&temp            //把序列后移一位            a[j] = a[j-1];            j--;        }        //插入位置为j        a[j] = temp;    }     //打印输出    for(int i=0;i<7;i++){< span>        printf("%d",a[i]);    }    return 0;}```  > 输出结果：0 0 1 2 3 4 9## 性能分析 - 简单插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n)。  - 在最坏情况下，时间复杂度依然为O(n2)。  - 但是在数组元素随机排列的情况下，插入排序还是要优于上面两种排序的。  - 过程中需要一个临时变量temp，所需要的额外空间为1，空间复杂度则为O(1)。  - 元素交换时，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。  | 时间复杂度 | 最好情况 | 最坏情况 | 平均复杂度 | 空间复杂度 | 稳定性 || :-: | :-: | :-: | :-: | :-: ||简单插入排序|O(n)|O(n^2)|O(n^2)|O(1)|稳定|    # **希尔排序** shellSort，又称“缩小增量排序”，是1959年D.L.shell提出的。## 算法步骤 - 先将整个待排序列分割成若干个子序列分别进行直接插入排序  - 然后依次缩减增量再进行排序  - 待整个序列中的元素基本有序时- 在对全体元素进行一次直接插入排序    ## 代码示例
              //把序列后移一位
              a[j] = a[j-1];
              j--;
          }
          //插入位置为j
          a[j] = temp;
      }
  
       //打印输出
      for(int i=0;i<7;i++){< span>        printf("%d",a[i]);    }    return 0;}```  > 输出结果：0 0 1 2 3 4 9## 性能分析 - 简单插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n)。  - 在最坏情况下，时间复杂度依然为O(n2)。  - 但是在数组元素随机排列的情况下，插入排序还是要优于上面两种排序的。  - 过程中需要一个临时变量temp，所需要的额外空间为1，空间复杂度则为O(1)。  - 元素交换时，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。  | 时间复杂度 | 最好情况 | 最坏情况 | 平均复杂度 | 空间复杂度 | 稳定性 || :-: | :-: | :-: | :-: | :-: ||简单插入排序|O(n)|O(n^2)|O(n^2)|O(1)|稳定|    # **希尔排序** shellSort，又称“缩小增量排序”，是1959年D.L.shell提出的。## 算法步骤 - 先将整个待排序列分割成若干个子序列分别进行直接插入排序  - 然后依次缩减增量再进行排序  - 待整个序列中的元素基本有序时- 在对全体元素进行一次直接插入排序    ## 代码示例
          printf("%d",a[i]);
      }
      return 0;
  }
  ```  
  > 输出结果：0 0 1 2 3 4 9
  ## 性能分析 
  - 简单插入排序在最好情况下，需要比较n-1次，无需交换元素，时间复杂度为O(n)。  
  - 在最坏情况下，时间复杂度依然为O(n2)。  
  - 但是在数组元素随机排列的情况下，插入排序还是要优于上面两种排序的。  
  - 过程中需要一个临时变量temp，所需要的额外空间为1，空间复杂度则为O(1)。  
  - 元素交换时，相同元素的前后顺序并没有改变，所以冒泡排序是一种稳定排序算法。  
  
  | 时间复杂度 | 最好情况 | 最坏情况 | 平均复杂度 | 空间复杂度 | 稳定性 |
  | :-: | :-: | :-: | :-: | :-: |
  |简单插入排序|O(n)|O(n^2)|O(n^2)|O(1)|稳定|  
    
  
  # **希尔排序** 
  shellSort，又称“缩小增量排序”，是1959年D.L.shell提出的。
  ## 算法步骤 
  - 先将整个待排序列分割成若干个子序列分别进行直接插入排序  
  - 然后依次缩减增量再进行排序  
  - 待整个序列中的元素基本有序时
  - 在对全体元素进行一次直接插入排序    
  
  ## 代码示例

//从第一个子序列的第二条记录开始顺序扫描待排序列
void ShellInsert(RecordList L, int dk){
for(i=dk+1;i<=l.length;i++)
//属于哪一子序列
if(L.r[i].key L.r[0] = L.r[i];
//子序列增量减少
for(j=i-dk;j>0 && (L.r[0].key L.r[j+dk] = L.r[j];
L.r[j+dk] = L.r[0];
}
}
//直接插入
void ShellSort(RecordList L,int dlta[],int t){
for(k=0;k ShellInsert(L,dlta[k]);
}
`

输出结果：无

性能分析

• 序列越有序，排序越快
• 一个好的希尔排序执行时间大程度依赖于增量的选取
• 大多情况下选用“增量每次除以2递减” ，其时间复杂度为O(n^2)
• 新的增量序列（2k-1，2k-1-1,2k-1-1-1，……7,3,1），其复杂度可以到达O(n^3/2)效率更好
• 序列中相同的关键字其排序先后位置发生了改变，故希尔排序是不稳定的算法

时间复杂度	最好情况	最坏情况	平均复杂度	空间复杂度	稳定性
希尔排序	O(n^3/2)	O(n^2)	O(n^2)	O(1)	不稳定