常见算法

 1.插入排序法  插入到有序数组中合适的位置

    思想:插入排序法的排序思想就是从数组的第二个元素开始,将数组中的每一个元素按照规则插入到已排好序的数组中以达到排序的目的.一般情况下将数组的第一个元素作为启始元素,从第二个元素开始依次插入.由于要插入到的数组是已经排好序的,所以只是要从右向左找到比插入点(下面程序中的insertNote)小(对升序而言)的第一个数组元素就插入到其后面.直到将最后一个数组元素插入到数组中,整个排序过程就算完成.
    稳定性:稳定的.
    时间复杂度:O(n2)
    空间复杂度：O（1）
 2.冒泡算法   最大的冒泡到最后位置
 
  思想:冒泡排序是一种简单的交换类排序。其基本思路是，从头开始扫描待排序的元素，在扫描过程中依次对相邻元素进行比较，将关键字值大的元素后移。每经过一趟排序后，关键字值最大的元素将移到末尾，此时记下该元素的位置，下一趟排序只需要比较到此位置为止，直到所有元素都已有序排列。
  稳定性:稳定的.
  时间复杂度:O(n2)
  空间复杂度：O（1）
 
 3.选择排序  每次选择最小的放到i位置上
 
  思想：每一趟在n-i+1（i=1，2，…n-1）个记录中选取关键字最小的记录作为有序序列中第i个记录
  稳定性:不稳定.
  时间复杂度:O(n2)
  空间复杂度：O（1）
 
 4.快速排序  分两部分  一部分比这个值大，一部分比这个值小   然后递归
 
 思想：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
  稳定性:不稳定.
  时间复杂度: O(nlog2n)     最坏O(n2)  平均O(nlog2n)
  空间复杂度：O（nlog2n）
 
  5.希尔排序 插入排序的一种  比较 A[i] A[i+d]  大小替换   直至d=1
 
  先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为d1的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d2<d1重复上述的分组和排序，直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。
   稳定性:不稳定.
  时间复杂度: O(n1.3)     最坏O(n2)  O(n)
  空间复杂度：O（1）

  6.堆排序
 
  初始时把要排序的数的序列看作是一棵顺序存储的二叉树，调整它们的存储序，使之成为一个 堆，这时堆的根节点的数最大。然后将根节点与堆的最后一个节点交换。然后对前面(n-1)个数重新调整使之成为堆。依此类推，直到只有两个节点的堆，并对 它们作交换，最后得到有n个节点的有序序列。从算法描述来看，堆排序需要两个过程，一是建立堆，二是堆顶与堆的最后一个元素交换位置。所以堆排序有两个函数组成。一是建堆的渗透函数，二是反复调用渗透函数实现排序的函数。
  稳定性:不稳定.
  时间复杂度: O(nlog2n)
  空间复杂度：O（1）
 
  7.归并排序   一个数组分成多个  然后多个之间合并
 
  思想：原理,把原始数组分成若干子数组,对每一个子数组进行排序,继续把子数组与子数组合并,合并后仍然有序,直到全部合并完,形成有序的数组
 
  稳定性:稳定.
  时间复杂度: O(nlog2n)
  空间复杂度：O（1）
 
  8.基数排序
  思想：它是一种非比较排序。它是根据位的高低进行排序的，也就是先按个位排序，然后依据十位排序……以此类推。
   稳定性:稳定.
  时间复杂度: O(d(n+r))
  空间复杂度：O（n+r）