直接插入排序和冒泡排序改进算法

C++

数据结构

Publish Date: 2020-07-05

Word Count: 541

Read Times: 2 Min

直接插入排序

插入排序的基本方法是：每一步都将待排序的元素，插入到前面已经排好序的一组元素的适当位置上去，直到元素全部插入为止。
直接插入排序基本思想：将一个元素插入到已排好序的序列中，从而得到一个新的有序序列（将序列的第一个数据看成是一个有序的子序列，然后从第二个记录逐个向该有序的子序列进行有序的插入，直至整个序列有序）
直接插入排序是由两层嵌套循环组成的。外层循环标识并决定待比较的数值。内层循环为待比较数值确定其最终位置。直接插入排序是将待比较的数值与它的前一个数值进行比较，所以外层循环是从第二个数值开始的。当前一数值比待比较数值大的情况下继续循环比较，直到找到比待比较数值小的并将待比较数值置入其后一位置，结束该次循环。

代码

for(i=0;i<n;i++)
 {
  if(s[i]<s[i-1])
  {
   temp = s[i];
   j = i-1; 
   
   while(j>=0 && s[j]>temp) 
   {
    s[j+1]=s[j];
    j--; 
   }
   s[j+1] = temp; 
  } 
 }

复杂的分析

时间复杂度：O(n^)
空间复杂度：O(1)

改进冒泡排序

如果已经是有序的数列，就不要再进行排序，及时终止，进入下一次排序，可以提高冒泡排序的时间复杂度
用两个循环嵌套进行两两比较，用一个false标记无序，进入一层循环，若标记为true，则表示有序，不用进行比较

代码

bool flag = false;  //用flag标记已经排好的元素 

 for(i=0;(i<n) && (flag == false);i++)
 {
  flag = true;
  for(j=n-1;j>i;j--)
  {
   if(s[j] < s[j-1])
   {
    temp   = s[j];
    s[j]   = s[j-1];
    s[j-1] = temp; 
    flag   = false;
   } 
  } 
 }