七种排序算法（冒泡排序，选择排序，插入排序，堆排序，希尔排序，归并排序，快速排序）

•         冒泡排序是一种最简单的排序算法，叫冒泡：其实它真的就像从水底冒出水泡一样，随着水泡的位置越来越接近水面，它那个水泡就会越变越大。而冒泡排序也就是将一串无序的数字通过相互比较，将最大的数字放在这传数字的最后，然后依次进行这样的比较，然后就可以将一串无序的数字做出排序。
•         算法描述：
  •        比较相邻的元素的大小，如果前一个比后一个大，就交换他们两个。
  •       对以上所有的元素重复以上步骤，直到无序的数字变得有序。
  •       对每一对相邻元素做相同的工作，从开始第一对到结尾最后一对。这样在最后的元素 就是最大的数。
•        冒泡排序算法的算法分析
  • 时间复杂度的分析：
    • 最优时间复杂度：O(n) ；
    • 最差时间复杂度：O(n^2);
    • 平均时间复杂度：O(n^2);    
  • 空间复杂度的分析：
    • 平均复杂度：O(1);
  • 稳定性：稳定

    paivate staticvoid swap(int[] arr,int index1,int index2){
        T temp=arr[index1];
        arr[index1]=arr[index2];
        arr[index2]=temp;
    }
    
    public static> void bubbleSort(int[] arr){
        boolean flag;
        for(int i=0;i0){
                    swap(arr,j,j+1);
                }    
    }
            if(flag){
                break;
                }
            
    
        }
    
    }

•         选择排序的思想：
  • 首先在所要排序的序列中找到最小（最大）的元素，存放在排序序列的起始位置，然后，再从剩余的元素中继续寻找最大的元素，和已经排序好的队列末尾进行交换，以此类推，直到所有的元素都变得有序。
  • 使用选择排序的时候，数据规模越小越好。
•       选择排序算法的算法分析：
  • 时间复杂度的分析：
    • 最优时间复杂度：O(n^2);
    • 平均时间复杂度：O(n^2);
    • 最坏时间复杂度：O(n^2);
  •         稳定性：不稳定（有数据元素的跳转）

private static void swap(int[] arr,int index1,int index2){
    T temp=arr[index1];
    arr[index1]=arr[index2];
    arr[index2]=temp;
}
public static>void selectSort(int[] arr){
    if(arr==null||arr.length==1）{
        reurn;
    }
    for(int i=0;i

• 插入排序算法描述：
  • 插入排序的算法是通过构建有序序列，对于未排列的数据，在已排列的序列中从后向前进行查找操作，找到满足条件的元素之后进行位置插入操作。
  • 从第一个元素开始，该元素可以认为是已经排好序的元素。
  • 取出下一个元素，在已经排序好的元素中从后向前进行查找；
  • 如果已经排好序的元素大于新元素，将该元素移动到下一个位置；
  • 重复上一个操作，直到找到已经排序好的元素小于或等于新元素，进行元素的插入操作。
• 插入序列的算法分析：
  • 时间复杂度的分析：
    • 最优时间复杂度：O(n);
    • 平均时间复杂度：O(n^2);
    • 最差时间复杂度：O(n^2);
  • 平均空间复杂度：O(1);
  • 稳定性：稳定

public static>void InsertSort(T[] arr){
    if(arr==null||arr.length==1){

         retuurn;
    }
//先找位置
for(int i=0;ii;z--){
    arr[z]=arr[z-1];

    }
arr[z-1]=temp;
    }
}

• 堆排序的思想：
  • 堆是一棵顺序存储的完全二叉树，完全二叉树所有非终端节点的值均不大于（或不小于）其左、右孩子节点的值。其中每个节点的值小于或等于其左、右孩子的值，这样的堆称为小根堆；其中每个节点的值大于等于其左右孩子的值，这样的堆称为大根堆。
  • 堆排序是指利用堆这种数据结构进行设计的一种排序算法。堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，是的当前无序区中选取最大（或最小）关键字的记录变得简单。
  • 用大根堆排序的基本思想：
    • 先将初始数组组建成一个大根堆，此堆为初始的无序；
    • 再将关键字最大的记录R（1）（及堆顶）和无序区的最后一个记录R（n）交换，由此得到新的无需区R(1...n-1)和有序区R(n)。由于交换后新的根R(1)和该区的最后一个记录R(n-1)交换，由此等到新的无序区R（1...n-2）和有序区R(n-1...n),同样要将R(1...n-2)调整为堆。
    • 直到无序区只有一个元素为止。
  •         堆排序首先是根据元素构建堆，然后将堆节点取出（一般是与最后一个节点进行交换）

，将前面的len-1个节点继续进行堆调整的过程，然后再将根节点取出，这样一直到所有节点都取出。

private staticvoid swap(T[] arr,int index1,int index2){
    T temp=arr[index1];
    arr[index1]=arr[index2];
    arr[index2]=temp;
}
private static>void adjust(T []arr,int start,int end){
    T temp=arr[start];
for(int i=2*start+1;i<=end;i=2i+1){
    if(i+1<=end&&arr[i].compareTo(arr[i+1])<0){
        i++;//保存左右孩子较大值的下标
        }
    if(temp.compareTo(arr[i])<0){
        arr[start]=arr[i];
        start=arre[i];

        }else{
        break;        
        }
    }
        arr[start]=temp;

}

public static>void heapSort(T[] arr){
    int i=0;
    for(i=(arr.length-1-1)/2;i>=0;i--){//代表要调整根节点的下标
        adjust(arr,i,arr.length-1);//最大堆建好了
        }
     int temp=0;
    for(i=0;i

• 希尔排序的思想：
  • 希尔排序就是一种插入排序，他是简单的插入排序的一种算法改进方式，也称为见效增量排序，希尔排序的时复杂度相比直接插入排序的时间复杂度要小，它与直接插入排序的不同在于他会优先距离较远的元素，希尔排序是按照一定的增量进行分组排序，对每一组进行直接插入排序，随着分组个数的减少，每组中的元素就会越来越多，当增量减少到1时，排序结束。
  • 选择增量的gap=length/2,缩小增量以gap=gap/2的方式进行分组，{n/2,(n/2)/2,(n/2)/4...1};
  • 选择一个增量序列，按照增量序列的个数m,进行m趟排序；
  • 每趟排序根据相应的增量次数分别进行元素的分组操作，队组内进行直接插入操作；
  • 继续下一个增量，分别进行分组直接插入排序
  • 重复第三个步骤，直到增量变为1，所有元素在一个分组内，希尔排序结束。
• 希尔排序算法分析：
  • 实际按复杂度分析：
    • 平均实际按复杂度：O(n~1.3-1.5)
  • 空间复杂度：
    • O(1)
• 稳定性分析：不稳定

  pubLic staticvoid shellSort(T[] arr,int gap){
      int i=0;
      int j=0;
      for(int i=gap;i=0;j-=gap){
          if(temp.comparableTo(arr[j])<0){
              arr[j+gap]=arr[j];
              }else{
                  break;
              }
          }
          arr[j+gap]=temp;
      }
  
  }
  public static>void shell(T[] arr){
  
      int[] partition={5,3,1};
      for(int i=0;i 
   

• 归并排序的思想及算法描述：
  • 归并排序建立在归并的优先操作上进行排序，主要采用分治法将已有序的序列合并，得到完全有序的序列，即先让每一小段有序，再让小段之间变得有序，若将两个有序合成一个有序段，这又称为二路归并。
  • 排序的开始是以间隔为1的进行归并，也就是说，第一个元素跟第二个元素归并，第三个与第四个归并；
  • 然后再以间隔为1的进行归并，1-4进行归并，5-8进行归并；
  • 再以2*2的间隔进行归并，同理，超过2*k的数组长度为止。
  • 当不够两组进行归并时，如果超过k个元素，仍然进行归并，如果剩余元素不超过k个元素，那么直接复制给中间数组，
• 归并算法分析：
  • 实际按复杂度的分析：
    • 平均实际按复杂度：O(n)
    • 最坏实际按复杂度：O()
  • 空间时间复杂度的分析：
    • O(n)
• 稳定性分析:不稳定

  public static>void merge(T[] arr,int len,int gap){
      int low1=0;//定义第一个归并段的起始下标
      int high1=low1+gap-1;//第一个归并段的结束下标
      int high2=low2+gap-1>len-1?len-1:low2+gap-1;
      T[] brr=(T[])new Comparable(arr.length);
      int i=0;
  
  while(low2len-1?len-1:low2+gap-1;
      }
  
          //若没有两个归并段，单的直接拷贝下来
          while(low1<=len-1){
              brr[i++]=arr[low1++];
          }
      for(i=0;i>void merageSort(T[] arr){
      for(int i=1;i

• 快速排序的思想即算法描述：
  • 快速排序通过选择一个关键值作为基础值，比基准值小的都在左边序列（一般时无序的），比基准值大的都在右边（一般也无序）。依次递归，达到总体待排序列都变得有序。
  • 选择基准：在待排序列中，按照某种方式挑出一个元素，作为基准。
  • 分割操作：以该基准在序列中的实际位置，把序列分成两个子序列。此时，在基准左边的元素都比基准小，在基准右边的元素都比基准大。
  • 递归的对连个序列进行快速排序，直到序列为空或者只有一个元素。
• 快速排序的算法分析：
  • 时间复杂度分析：
    • 最优时间复杂度：O();
    • 平均时间复杂度：O();
    • 最坏时间复杂度：O(n^2); 

  • 空间复杂度分析：

    • O(1);

• 稳定性分析：不稳定

public static>int partition(T[] arr,int low,int high){
    T temp=arr[low];
    while(low>void quick(T[] arr,int low,int high){
    int part=partition(arr,low,high);
    if(low+1>void quickSort(T[] arr){
    quick(arr,0,arr.length-1);

}

• 快排的优化算法：
  • 选择基准的方式：
    • 对于分治算法，当每次划分时，算法若都能分成两个等长的子序列时，那么分治算法的算法效率就会达到最大。也就是说，基准的选择是很重要的，选择基准的方式决定了两个分割后的子序列的长度，进而对整个算法的效率产生决定性的影响。最理想的 方式就是选择基准的时候恰好能把待排序列分成两个等长的子序列。
    • 固定位置：
      • 取序列的第一个或最后一个元素作为基准：基本的快速排序：public staticT selectPivot(T[] arr,int low,int high){return arr[low];}
      • 基本的快速排序选取第一个或最后一个元素作为基准。
    •  三数取中
      • 引入的原因：
        • 虽然随机选取枢轴时，减少出现不好分割的几率，但是还是最坏的情况下还是O(n^2),要缓解这种情况，就引入了三叔取中选取枢轴。
        • 最佳的划分是将待排序的序列分成等长的子序列，最佳的状态我们可以使用序列的中间的值，也就是N/2个数。可是，这很难算出来，并且会明显减慢快速排序的速度。这样的中值的估计可以通过随机选取三个元素并用它们的中值作为枢纽元而得到。事实上，随机性并没有多大的帮助，因此一般的做法是使用左端、右端和中心位置上的三个元素的中值作为枢纽元。显然使用三数种植分割法消除了预排序输入的不好情形，并且减少快排大约14%的比较次数。
        • 在选取中轴值时，可以由左中右三个中选取扩大到五个元素中或者更多元素中选取，一般的，会有（2t+1）平均分区法（median-of-(2t+1)）,三个平均分区法英文为（median-of-three）.
        • 具体思想：对待排序序列中low，mid，high三个位置上数据进行排序，取它们中间的那个数据作为枢轴，并用0下标元素存储枢轴，即采用三数取中，并用0下标元素存储枢轴。

private staticvoid swap(T[] arr,int index1,int index2){
    T temp=arr[index1];
    arr[index1]=arr[index2];
    arr[index2]=temp;
}

//函数作用：取待排序列中low，mid，high三个位置上数据，选取他们中间的那个数据作为枢轴
pubic static>T selectPivotMedianOfThree(T[] arr,int low,int high){
    int mid=low+((high-low)>>1);//计算数组中间的元素的下标
    //使用三数取中法选择枢轴
    if(arr[mid].compareTo(arr[high])>0){//目标：arr[low]<=arr[high]
        swap(arr,mid,high);
    }
    if(arr[low].compareTo(arr[high])>0){//目标：arr[low]<=arr[high]
        swap(arr,low,high);
    }
    if(arr[mid].compareTo(arr[low])>0){//arr[low>=arr[mid]]
        swap(arr,mid,low);
    }
        //此时，arr[mid]<=arr[low]<=arr[high];
        return arr[low];//low的位置上保存这三个位置中间的值
//分割时可以直接使用low位置的元素作为枢轴，而不用改变分割函数了