1. /*
  2. * 所有排序皆为升序
  3. */

1. 插入排序

1.1 直接插入排序

直接插入排序(Straight Insertion Sort)的基本思想是：

把n个待排序的元素分为有序和无序两个集合.起初有序集合只有1个元素,无序集合有n-1个.排序过程中每次从无序集合中取出第一个元素,将它插入到有序集合中的适当位置,使之成为新的有序集合,重复n-1次可完成排序过程.

思路:

  • 将区间[0,n]分为两部分,[0,end]有序,[end+1, n]无序.则end+1是要插入的元素x下标.
  • 插入的位置有两种:
    1. 在中间:把比x大的元素都往后挪动一个位置,插入
    2. 在两端:遍历完无序集合后插入
  • 尽管插入的位置有两种,但它们都要插入,不妨把在两端插入当做在中间插入的一种特殊情况,即判断是否符合在中间插入的条件,符合则挪动,否则跳过判断,直接在两端插入.

代码:

  1. // 插入排序
  2. //将区间[0，n]分为两部分
  3. //将[0，end]看作有序，end+1是要插入的元素下标
  4. void InsertSort(int* a, int n)
  5. {
  6.     for (int i = 0; i < n - 1; i++)
  7.     {
  8.         int end = i;
  9.         //int tmpi = end + 1;//保存下标不可行
  10.         int tmp = a[end + 1];
  11.         while (end >= 0)
  12.         {
  13.             if (tmp < a[end])//原值大于要插入的数
  14.             {
  15.                 a[end + 1] = a[end];//往后挪动
  16.                 end--;//向前比较
  17.             }
  18.             else
  19.             {
  20.                 break;
  21.             }
  22.         }
  23.         //循环终止（插入位置）有两种情况
  24.         //此时end在空出来的前一个位置
  25.         a[end + 1] = tmp;
  26.     }
  27. }

注意事项:

  1. 如何将[end+1, n]无序集合中的第一个元素插入[0,end]有序集合?
    • 用循环控制有序集合的[0,end],那么无序集合第一个元素就是有序集合的下一个元素,即end+1.注意end范围[0,n-1].
  2. 挪动必须从有序集合的的尾部挪动一个位置,避免有序集合的数据被覆盖.但这样会造成无序集合的第一个元素被覆盖,所以需要提前保存该元素,但不能使用下标保存.

    特点

  • 当数据接近有序,直接插入效率越高.时间复杂度接近O(N).所以插入排序适合处理接近有序的数据.
  • 时间复杂度:O(N2)
  • 空间复杂度:O(1)
  • 稳定性:稳定

    关于各排序算法的稳定性,将会在总结时介绍.

1.2 希尔排序

希尔排序(Shellsort),也称递减增量排序算法,是插入排序的一种更高效的改进版本.

希尔排序通过全部元素分为长度相同几个区域来提升插入排序的性能.这样可以让一个元素可以一次性地朝最终位置前进一大步.然后再取越来越小的步长进行排序,步长为1时就是普通的插入排序,但是到了这步,数据已经是接近有序的了. 也就是说,希尔排序是有步长(>=1)的插入排序. 而步长的选择是希尔排序中的重要部分.

思路:

  1. 预排序(gap>1):刚开始以一个较大的gap(步长)值对数据进行预排序,每预排序一次,gap按某种规则减小
  2. 直接插入排序(gap=1):当gap(步长)值为1时,数据已经接近有序,对其进行直接插入排序.

image.png
通过对上图中最后的四组数据中各个数字(尤其是两端的数字)的位置的分析,我们可以知道:6和1从一端走到另一端仅仅用了两次!而中间的其他数字从原始位置走到正确位置也仅仅用了2~3次,这极大地提高了排序的效率.试想6和1在插入排序中走的次数可是数组长度,而实际上数组的长度往往不会很小.
通过动手实现部分预排序,可以知道实际上这就是步长为gap步的插入排序,插入排序的gap为1.
先写出gap=3的一次预排序.

  1. // 希尔排序
  2. void ShellSort(int* a, int n)
  3. {
  4.     int gap = 3;
  5.     //保证不越界
  6.     //因为要拿无序集合的下一个和第一个比较
  7.     for (int i = 0; i < n - gap; i += gap)
  8.     {
  9.         int end = i;
  10.         int tmp = a[end + gap];
  11.         //挪动数据
  12.         while (end >= 0)
  13.         {
  14.             if (tmp < a[end])
  15.             {
  16.                 a[end + gap] = a[end];
  17.                 end -= gap;
  18.             }
  19.             else
  20.             {
  21.                 break;
  22.             }
  23.         }
  24.         a[end + gap] = tmp;
  25.     }
  26.     //最后一次插入排序
  27.     InsertSort(a, n);
  28. }

被大多数人所接受的gap的上限以及递减的方式:gap = gap / 3 + 1,后面的+1的作用是确保gap最后能取到1.假如gap = gap / 2,则不用+1.
简化代码:之前是按gap分组,一组一组地插入排序,而现在遍历数据的步长不是gap而是1,且保持插入排序的步长为gap,最终也能达到相同的效果.

即前者为红红红,蓝蓝蓝,紫紫紫;后者为红蓝紫,红蓝紫,红蓝紫,gap组数据交替地做插入排序.

  1. // 希尔排序
  2. void ShellSort(int* a, int n)
  3. {
  4.     int gap = n;
  5.     while (gap > 1)
  6.     {
  7.         gap = gap / 3 + 1;
  8.         for (int i = 0; i < n - gap; i++)
  9.         {
  10.             int end = i;
  11.             int tmp = a[end + gap];
  13.             while (end >= 0)
  14.             {
  15.                 if (tmp < a[end])
  16.                 {
  17.                     a[end + gap] = a[end];
  18.                     end -= gap;
  19.                 }
  20.                 else
  21.                 {
  22.                     break;
  23.                 }
  24.             }
  25.             a[end + gap] = tmp;
  26.         }
  27.     }
  29. }

注意事项:

  1. 同插入排序
  2. 注意循环的边界是[0,n-gap],原因同插入排序.是为了避免越界,因为是用有序区间的下一个元素(它属于无序区间)和有序区间的第一个元素比较的.

小结:

  1. 步长>1,预排序:gap起初较大,能让极端数据以更大的步长到达两端,也就是更快地到达正确位置,但是这会让数据偏离有序.让gap以很快的速度(所以不是递减某个数)减小,依次来优化下一次的插入排序,因为前面的[排序已经让极端数据接近或已经到达正确位置了,所以接下来就是让gap减小,让数据接近有序.因此它的时间复杂度不会很大.
  2. 步长=1,直接插入排序.充分发挥插入排序的优势.

以自己的理解,得出希尔排序的时间复杂度的近似值:

实际上,希尔排序的时间复杂度涉及一些未解决的数学难题,因此只能近似估算其时间复杂度. 对于N个数据,如果gap很大很大,N次;而第一个循环为O(log3N),则时间复杂度近似值为O(N*logN). 官方时间复杂度近似值为O(N1.3)

特点

  • 希尔排序的思想十分巧妙,从纵向看:前面的每次预排序都是让极端数据以更大的步长更快速的到达正确位置,下一次的预排序都是上一次的优化,使得每次排序都更接近有序.其每一次的排序都是有正向关联的.
  • 时间复杂度:O(N1.3)
  • 空间复杂度:O(1)
  • 稳定性:不稳定

    2. 选择排序

    2.1 选择排序

    选择排序(Selection sort)的基本思想是:

    首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置,然后,再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾.以此类推,直到所有元素均排序完毕.

[优化]思路:

  1. 每次遍历数组找到最小值和最大值,通过和首尾部元素交换的方式分别放在数组的首部和尾部
  2. 每找到一对,都要放在之前找到的最值的后面
  3. 直到只剩一个数据
  1. // 选择排序
  2. void SelectSort(int* a, int n)
  3. {
  4.     //确定边界
  5.     int begin = 0;
  6.     int end = n - 1;
  7.     while (begin < end)
  8.     {
  9.         //寻找每次遍历的最值
  10.         int maxi = begin, mini = begin;
  11.         for (int i = begin + 1; i <= end; i++)
  12.         {
  13.             if (a[maxi] < a[i])
  14.             {
  15.                 maxi = i;
  16.             }
  17.             if (a[mini] > a[i])
  18.             {  
  19.                 mini = i;
  20.             }
  21.         }
  22.         Swap(&(a[begin]), &(a[mini]));
  23.         if (begin == maxi)
  24.         {
  25.             maxi = mini;
  26.         }
  27.         Swap(&(a[end]), &(a[maxi]));
  28.         //更新边界
  29.         begin++;
  30.         end--;
  31.     }
  32. }

注意事项:

  1. 寻找最值和交换位置都是通过控制下标完成的.
  2. 在两个交换函数中间需要修正maxi(最大值的下标)的值.因为begin有可能等于maxi.试想:54321要排成12345,第一轮:begin=0,end=4,maxi=1,mini=4.第一个交换函数将1(下标为mini)放在首部(下标为begin)的位置上,第二次交换把5(下标为maxi)放在尾部(下标为end)的位置上,但是上一次已经把1和5的位置换了,它们的下标也交换了,所以要修正下标.

    特点

  • 选择排序的优点是容易理解,缺点是不论数据的形式如何,选择排序的算法都要对其遍历,也就是说,它在任何时候都没有优势,因而没有被人广泛使用.
  • 时间复杂度:O(N2)
  • 空间复杂度:O(1)

  • 稳定性:不稳定

    2.2 堆排序

    个人认为这里已经讲的很详细了,欢迎交流.

    特点

  • 堆排序利用二叉树,达到二分数据的效果.虽然不受数据形式影响,但因其算法的优越性,数据形式不会对效率产生太大影响.

  • 时间复杂度:O(N*logN)
  • 空间复杂度:O(1)
  • 稳定性:不稳定

3. 交换排序

3.1 冒泡排序

冒泡排序(Bubble Sort)又称为泡式排序,是一种简单的排序算法.

它重复地遍历要排序的数列,一次比较两个元素,如果它们的顺序错误就交换它们的位置.直到该数列有序.之所以被称之为冒泡排序,是因为这个算法让越小的数字像泡泡一样”浮”到数列一端.

思路:

  1. 比较相邻元素.如果第一个比第二个大,就交换它们两个.
  2. 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对.每遍历一遍,最后的元素会是最大的数,而下一次遍历元素将会少一个.
  3. 对所有的元素重复以上的步骤,除了最后一个.
  4. 每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较,即为有序.
    // 冒泡排序
void BubbleSort(int* a, int n)
{
 for (int i = 0; i < n; i++)
 {
     int exchange = 0;
     //or j<-[1, n - i)
     for (int j = 0; j < n - i - 1; j++)
     {
         if (a[j + 1] < a[j])
         {
             Swap(&(a[j + 1]), &(a[j]));
             exchange = 1;
         }
     }
     if (exchange == 0)
         break;
 }
}
    优化:
    冒泡排序的效率不被数据顺序影响,所以即使数据原本是有序或者遍历几次就有序,剩下的元素则无需再遍历,所以程序中使用了标记变量exchange,以示数据是否被处理过.

    特点

  • 冒泡排序因为其算法的形象,是初学者最先接触的排序算法之一
  • 时间复杂度:O(N2).等差数列求和
  • 空间复杂度:O(1)
  • 稳定性:稳定

    3.2 快速排序

4. 归并排序