排序方法	平均情况	最好情况	最坏情况	辅助空间	稳定性
冒泡排序	O(n2)	O(n)	O(n2)	O(1)	稳定
简单选择排序	O(n2)	O(n2)	O(n2)	O(1)	不稳定
直接插入排序	O(n2)	O(n)	O(n2)	O(1)	稳定
希尔排序	O(nlogn)~ O(n2)	O(n1,3)	O(n2)	O(1)	不稳定
堆排序	O(nlogn)	O(nlogn)	O(nlogn)	O(1)	不稳定
归并排序	O(nlogn)	O(nlogn)	O(nlogn)	O(n)	稳定
快速排序	O(nlogn)	O(nlogn)	O(n2)	O(nlogn)~ O(n)	不稳定

1.排序算法

　　链接：

1.1选择排序

　　步骤：

    　　1、初始状态：无序区为R[1..n]，有序区为空。

    　　2、第i趟排序(i=1,2,3...n-1)

      　　   第i趟排序开始时，当前有序区和无序区分别为R[1..i-1]和R(i..n）。

              该趟排序从当前无序区中选出关键字最小的记录 R[k]，将它与无序区的第1个记录R交换，

              使R[1..i]和R分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区。

    　　3、前n-1趟结束，数组有序化了

　　代码：

1 public void selectSort(List
     
       as,int left,int right){ 2         int N = right-left+1; 3         for(int i=left;i
      
       as.get(j)){ 7 temp=j; 8  } 9  } 10 if(temp!=i){ 11 int t = as.get(i) ; 12  as.set(i,as.get(temp)); 13  as.set(temp, t); 14  } 15  } 16 17 }
      
     

　　分析：

    　　复杂度：最优：O(n^2)，最差：O(n^2),平均：O(n^2)

    　　额外空间：O(1)

    　　稳定性：不稳定

1.2 插入排序

步骤：

    1、从第一个元素开始，该元素可以认为已经被排序

    2、取出下一个元素，在已经排序的元素序列中从后向前扫描

    3、如果该元素（已排序）大于新元素，将该元素移到下一位置

    4、重复步骤3，直到找到已排序的元素小于或者等于新元素的位置

    5、将新元素插入到该位置后

    6、重复步骤2~5

代码：

1 private void insertSort(List
     
       as,int left,int right){   2         int N = right-left+1; 3         for(int i=left;i
      
       left;j--){ 7 if(temp
      
     

　　分析：

   　　复杂度：最优：O(n)，最差：O(n^2),平均：O(n^2)

   　　额外空间：O(1)

   　　稳定性：稳定

1.3 希尔排序

描述：

    1、先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。

    2、所有距离为d1的倍数的记录放在同一个组中，在各组内进行直接插入排序。

    3、取第二个增量d2<d1重复上述的分组和排序，

    4、直至所取的增量dt=1(dt<dt-l<…<d2<d1)，即所有记录放在同一组中进行直接插入排序为止。

增量序列：

    1.希尔增量：ht=[n/2] hk=[hk+1/2]

    2.Knuth增量

    3.Hibbard增量

    4.Sedgewick增量

1.4 堆排序

步骤：

      数组储存成堆的形式之后，第一次将A[0]与A[n - 1]交换，

      再对A[0…n-2]重新恢复堆。第二次将A[0]与A[n-2]交换，

      再对A[0…n-3]重新恢复堆，重复这样的操作直到A[0]与A[1]交换。

      由于每次都是将最小的数据并入到后面的有序区间，

      故操作完成后整个数组就有序了

代码：

1 private  void duiSort(List
     
       as){ 2 　　for(int i=as.size()-1;i>0;i--){ 3        int  tmp = as.get(i); 4        as.set(i, as.get(0)); 5        as.set(0, tmp); 6        perDown(as ,0,i); 7  } 8 } 9 //建堆 10 private void buildDui(List
      
        as){ 11 for(int i = as.size()/2;i>=0;i--){ 12  perDown(as ,i,as.size()) ; 13  } 14 } 15 //下沉 16 private void perDown(List
       
         as ,int i,int n){ 17 int child; 18 int tmp; 19 for(tmp=as.get(i);2*i+1
       
      
     

　　分析：

    　　复杂度：最优：O(nlogn)，最差：O(nlogn),平均：O(nlogn)

    　　额外空间：O(n)

1.5 归并排序

　　描述：

    　　1、Divide: 把长度为n的输入序列分成两个长度为n/2的子序列。

    　　2、Conquer: 对这两个子序列分别采用归并排序。

    　　3、Combine: 将两个排序好的子序列合并成一个最终的排序序列。

　　代码：

1 /** 2 *归并排序，将输入数组array从start到end的数值进行排序 3 *@param array 输入数值数组 4 *@param start 须排序的起始位置 5 *@param end 须排序的结束位置 6 */ 7 /** 8 *把长度为n的输入序列分成两个长度为n/2的子序列 9 *对这两个子序列分别分割成两个一半的子序列，依次递归分割10 *当出现有序子序列时进行回溯，将两个分别有序的子序列进行合并11 **/12 public static void mergeSorting(int[] array , int start,int end){13     if(start

1.6 快速排序

　　基本思想：

         通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，

         则可分别对这两部分记录继续进行排序，以达到整个序列有序

　　步骤：

        1、从数列中挑出一个元素，称为 "基准"（pivot），

        2、重新排序数列，所有元素比基准值小的摆放在基准前面，所有元素比基准值大的摆在基准的后面（相同的数可以到任一边）。

             在这个分区退出之后，该基准就处于数列的中间位置。这个称为分区（partition）操作。

        3、递归地（recursive）把小于基准值元素的子数列和大于基准值元素的子数列排序。

　　代码：

1 　　private void swapArray(List
     
       as,int i,int j){ 2         int tmp = as.get(i); 3         as.set(i, as.get(j)); 4         as.set(j, tmp); 5     } 6     //枢纽元的选择：（三数中值分割法）左端、右端、中心位置三个元素的中值 7     //(1):选取a[left]、a[right]、a[center]进行比较； 8     //(2):最大者放到a[right],最小者放到a[left],中间值放到a[right-1],a[right-1]的值放到a[center] 9     //(3):i初始为left，j初始为right-110     private Integer Median3(List
      
        as,int left,int right){ 11 12 int center= (left+right)/2; 13 if(as.get(center)
       
         as,int left,int right){ 21 int DING =10; 22 if(left+DING<=right){ 23 int key = Median3( as,left,right); 24 25 int i =left,j=right-1; 26 27 while(true){ 28 while(as.get(++i)
        
         key){} 30 if(i
        
       
      
     

1.7 桶排序

　　描述：

        1、设置一个定量的数组当作空桶子。

        2、寻访串行，并且把项目一个一个放到对应的桶子去。

        3、对每个不是空的桶子进行排序。

        4、从不是空的桶子里把项目再放回原来的串行中。

2.最长公共子序列

　　    

　　

（1）子序列不见得一定是连续的，子串要求一定是连续的；

动态规划：

    第一步：先计算最长公共子序列的长度。

    第二步：根据长度，然后通过回溯求出最长公共子序列。

    现有两个序列X={x1,x2,x3，...xi}，Y={y1,y2,y3，....，yi}，

    设一个C[i,j]: 保存Xi与Yj的LCS的长度。    

    递推方程为：

        1. 当i=0||j=0，则C[i][j]=0;

        2. 当i,j>0&Xi=Yi，则C[i][j]=C[i-1][j-1]+1；

        3. 当i,j>0&Xi!=Yi，则C[i][j]=C[i-1][j]>C[i][j-1]?C[i-1][j]:C[i][j-1];

    采用一个标记函数Flag[i,j]，当

        ①：C[i,j]=C[i-1,j-1]+1  时 标记Flag[i,j]="left_up";    （左上方箭头）

        ②：C[i-1,j]>=C[i,j-1]   时 标记Flag[i,j]="left";       （左箭头）

        ③: C[i-1,j]<C[i,j-1]    时 标记Flag[i,j]="up";         （上箭头）

代码：

1 /** 2   *   3   * @param str1  4   * @param n1 5   * @param str2 6   * @param n2 7   * @return 8   */ 9   int[][] LCS;10   String[][] Flag;11   ArrayList
     
       WN = new ArrayList
      
       ();12   ArrayList
       
         WM= new ArrayList
        
         ();13   14   public void getLCS(String str1,int n1,String str2,int n2){15       char[] ctr1 = str1.toCharArray(); 16 char[] ctr2 = str2.toCharArray(); 17 LCS=new int[n1+1][n2+1]; 18 Flag=new String[n1+1][n2+1]; 19 for(int i=0;i<=n1;i++){ 20 for(int j=0;j<=n2;j++){ 21 if(i==0||j==0){ 22 LCS[i][j]=0; 23 24 }else{ 25 if(ctr1[i-1]==ctr2[j-1]){ 26 LCS[i][j]=LCS[i-1][j-1]+1; 27 Flag[i][j] = "left_up"; 28  } 29 else{ 30 if(LCS[i-1][j]>=LCS[i][j-1]){ 31 LCS[i][j]=LCS[i-1][j]; 32 Flag[i][j] = "left"; 33 }else{ 34 LCS[i][j]=LCS[i][j-1]; 35 Flag[i][j] = "up"; 36  } 37  } 38  } 39  } 40  } 41  } 42 43 public void SubSequence(int i, int j){ 44 45 if(i==0||j==0){ 46 return ; 47  } 48 if("left_up".equals(Flag[i][j])){ 49 WN.add(i-1); 50 WM.add(j-1); 51 SubSequence(i - 1, j - 1); 52 }else{ 53 if("up".equals(Flag[i][j])){ 54 SubSequence(i, j - 1); 55 }else{ 56 SubSequence(i - 1, j); 57  } 58  } 59  } 60 public String getSubString(String str1,String str2){ 61 String str =""; 62 for(int i=0;i
        
       
      
     

3.字符串相似度

　　

　　跟“最长公共子序列”一样，我们采用一个二维数组来保存字符串X和Y当前的位置的最小编辑距离。

　　现有两个序列X={x1,x2,x3，...xi}，Y={y1,y2,y3，....，yi}，

　　设一个C[i,j]: 保存Xi与Yj的当前最小的LD。

    　　①： 当 Xi = Yi 时，则C[i,j]=C[i-1,j-1]；

    　　②：当 Xi != Yi 时， 则C[i,j]=Min{C[i-1,j-1],C[i-1,j],C[i,j-1]}+1；

　　最终我们的C[i,j]一直保存着最小的LD

　　代码：

1 public static int getLCS(String str1,int n1,String str2,int n2){ 2       char[] ctr1 = str1.toCharArray(); 3       char[] ctr2 = str2.toCharArray(); 4       int[][] LCS=new int[n1+1][n2+1]; 5       for(int i=0;i<=n1;i++){ 6           for(int j=0;j<=n2;j++){ 7 if(i==0||j==0){ 8 LCS[i][j]=0; 9 }else{ 10 if(ctr1[i-1]==ctr2[j-1]){ 11 LCS[i][j]=LCS[i-1][j-1]; 12  } 13 else{ 14 int tmp = LCS[i-1][j]>LCS[i][j-1]?LCS[i][j-1]:LCS[i-1][j]; 15 LCS[i][j] = (tmp>LCS[i-1][j-1]?LCS[i-1][j-1]:tmp) +1; 16  } 17  } 18  } 19  } 20 return LCS[n1][n2]; 21 }

4.数组分割

　　问题：无序、元素2N的正整数数组，将数组分割为两个元素个数为N的数组，使两个数组的和接近

1.元素有负数；

2.分割的数组不是N个而是任意个；

3.两个数组：

　　a.和接近；

　　b.接近总和的一半；

　　c.两个数组和的差为一定值。

4.两个数组a、b，大小都为n,数组元素的值任意整形数，无序；

   要求：通过交换a、b数组中的元素，使[数组a元素的和]与[数组b元素的和]之间的差最小

1 void shuzudis(int[] arry){ 2         int N = arry.length; 3         int sum =0; 4         int min=arry[0]; 5         //找出最小值 6         for(int i=0;i
     
      arry[i]?arry[i]:min; 8  } 9 //如果有负值，则整体都加上减去最小值，进行正数化 10 if(min<0){ 11 for(int i=0;i
      
       0;j--){ 28 for(int v=0;v
       
        =arry[i]&&isOK[j-1][v-arry[i]]){ 30 isOK[j][v]=true; 31  } 32  } 33  } 34  } 35 //显示 36 for(int i=0;i
       
      
     

5.5/3数组分割

　　问题：编写一个函数，传入一个int型数组，返回该数组能否分成两组，

     　　 使得两组中各元素加起来的和相等，并且，所有5的倍数必须在

      　　其中一个组中，所有3的倍数在另一个组中（不包括5的倍数），

      　　能满足以上条件，返回true；不满足时返回fals

1 import java.util.*; 2  3 public class Main {   4     public static void main(String[] args) { 5         Scanner sc = new Scanner(System.in); 6         while(sc.hasNext()){ 7             int n = sc.nextInt(); 8 int sum1 = 0, sum2 = 0; 9 int[] a = new int[n]; 10 int count = 0; 11 for(int i =0;i