一. 冒泡排序(BubbleSort)

1. 根本思想：两个数比较巨细，较大的数下沉，较小的数冒起来。

2. 进程：

   • 比较相邻的两个数据，假如第二个数小，就交流方位。
   • 从后向前两两比较，一直到比较最前两个数据。终究最小数被交流到开端的方位，这样***个最小数的方位就排好了。
   • 持续重复上述进程，顺次将第2.3...n-1个最小数排好方位。
     

     

     冒泡排序

3. 均匀时刻复杂度：O(n2)

4. java代码完结：

   publicstaticvoidBubbleSort(int[]arr){
   inttemp;//暂时变量
   for(inti=0;i<arr.length-1;i++){//表明趟数，总共arr.length-1次。
   for(intj=arr.length-1;j>i;j--){
   if(arr[j]<arr[j-1]){
   temp=arr[j];
   arr[j]=arr[j-1];
   arr[j-1]=temp;
   }
   }
   }
   }

5. 优化：

   • 针对问题：
     数据的次序排好之后，冒泡算法仍然会持续进行下一轮的比较，直到arr.length-1次，后边的比较没有意义的。

   • 计划：
     设置标志位flag，假如发生了交流flag设置为true；假如没有交流就设置为false。
     这样当一轮比较完毕后假如flag仍为false，即：这一轮没有发生交流，阐明数据的次序现已排好，没有必要持续进行下去。

     publicstaticvoidBubbleSort1(int[]arr){
     inttemp;//暂时变量
     booleanflag;//是否交流的标志
     for(inti=0;i<arr.length-1;i++){//表明趟数，总共arr.length-1次。
     flag=false;
     for(intj=arr.length-1;j>i;j--){
     if(arr[j]<arr[j-1]){
     temp=arr[j];
     arr[j]=arr[j-1];
     arr[j-1]=temp;
     flag=true;
     }
     }
     if(!flag)break;
     }
     }

二. 挑选排序(SelctionSort)

1. 根本思想：
   在长度为N的无序数组中，***次遍历n-1个数，找到最小的数值与***个元素交流；
   第2次遍历n-2个数，找到最小的数值与第二个元素交流；
   。。。
   第n-1次遍历，找到最小的数值与第n-1个元素交流，排序完结。

2. 进程：

   

   挑选排序

3. 均匀时刻复杂度：O(n2)

4. java代码完结：

   publicstaticvoidselect_sort(intarray[],intlenth){
   for(inti=0;i<lenth-1;i++){
   intminIndex=i;
   for(intj=i+1;j<lenth;j++){
   if(array[j]<array[minIndex]){
   minIndex=j;
   }
   }
   if(minIndex!=i){
   inttemp=array[i];
   array[i]=array[minIndex];
   array[minIndex]=temp;
   }
   }
   }

三. 插入排序(Insertion Sort)

1. 根本思想：
   在要排序的一组数中，假定前n-1个数现已排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好次序的。如此重复循环，直到悉数排好次序。

2. 进程：

   

   插入排序

   

   相同的场景

3. 均匀时刻复杂度：O(n2)

4. java代码完结：

   publicstaticvoidinsert_sort(intarray[],intlenth){
   inttemp;
   for(inti=0;i<lenth-1;i++){
   for(intj=i+1;j>0;j--){
   if(array[j]<array[j-1]){
   temp=array[j-1];
   array[j-1]=array[j];
   array[j]=temp;
   }else{//不需要交流
   break;
   }
   }
   }
   }

四. 希尔排序(Shell Sort)

1. 前语：
   数据序列1： 13-17-20-42-28 运用插入排序，13-17-20-28-42. Number of swap:1;
   数据序列2： 13-17-20-42-14 运用插入排序，13-14-17-20-42. Number of swap:3;
   假如数据序列根本有序，运用插入排序会愈加高效。

2. 根本思想：
   在要排序的一组数中，依据某一增量分为若干子序列，并对子序列别离进行插入排序。
   然后逐步将增量减小,并重复上述进程。直至增量为1,此刻数据序列根本有序,***进行插入排序。

3. 进程：

   

   希尔排序

4. 均匀时刻复杂度：

5. java代码完结：

   publicstaticvoidshell_sort(intarray[],intlenth){
   inttemp=0;
   intincre=lenth;
   while(true){
   incre=incre/2;
   for(intk=0;k<incre;k++){//依据增量分为若干子序列
   for(inti=k+incre;i<lenth;i+=incre){
   for(intj=i;j>k;j-=incre){
   if(array[j]<array[j-incre]){
   temp=array[j-incre];
   array[j-incre]=array[j];
   array[j]=temp;
   }else{
   break;
   }
   }
   }
   }
   if(incre==1){
   break;
   }
   }
   }

五. 快速排序(Quicksort)

1. 根本思想：（分治）

   • 先从数列中取出一个数作为key值；
   • 将比这个数小的数悉数放在它的左面，大于或等于它的数悉数放在它的右边；
   • 对左右两个小数列重复第二步，直至各区间只要1个数。

2. 辅佐了解：挖坑填数

   • 初始时 i = 0; j = 9; key=72
     因为现已将a[0]中的数保存到key中，能够了解成在数组a[0]上挖了个坑，能够将其它数据填充到这来。
     从j开端向前找一个比key小的数。当j=8，契合条件，a[0] = a[8] ; i++ ;将a[8]挖出再填到上一个坑a[0]中。
     这样一个坑a[0]就被搞定了，但又形成了一个新坑a[8]，这怎样办了？简略，再找数字来填a[8]这个坑。
     这次从i开端向后找一个大于key的数，当i=3，契合条件，a[8] = a[3] ; j-- ;将a[3]挖出再填到上一个坑中。

     数组：72 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 48 - 85
      0   1   2    3    4    5    6    7    8    9

   • 此刻 i = 3; j = 7; key=72
     再重复上面的过程，先从后向前找，再早年向后找。
     从j开端向前找，当j=5，契合条件，将a[5]挖出填到上一个坑中，a[3] = a[5]; i++;
     从i开端向后找，当i=5时，因为i==j退出。
     此刻，i = j = 5，而a[5]刚好又是前次挖的坑，因而将key填入a[5]。

     数组：48 - 6 - 57 - 88 - 60 - 42 - 83 - 73 - 88 - 85
      0   1   2    3    4    5    6    7    8    9

   • 能够看出a[5]前面的数字都小于它，a[5]后边的数字都大于它。因而再对a[0…4]和a[6…9]这二个子区间重复上述过程就能够了。

     数组：48 - 6 - 57 - 42 - 60 - 72 - 83 - 73 - 88 - 85
      0   1   2    3    4    5    6    7    8    9

3. 均匀时刻复杂度：O(N*logN)

4. 代码完结：

   publicstaticvoidquickSort(inta[],intl,intr){
   if(l>=r)