八大排序-01

1.选择排序（Selection Sort）

基本思想：每一次从待排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完。
时间复杂度：O(n^2)。
空间复杂度：O(1)。
稳定性：不稳定。

 public static void xz(int[] arr){
    int n=arr.length;
     for(int i=0;i<n;i++){
        int min=arr[i];
        int index=i;

       //找到最小的
       for(int j=i+1;j<n;j++){
             if(arr[j]<min){
                min=arr[j];
               index=j;
             }
      }
         arr[index]=arr[i];
         arr[i]=min;
     }
 }

2. 冒泡排序（Bubble Sort）

基本思想：重复地遍历要排序的数列，一次比较两个元素（挨着的），如果它们的顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
时间复杂度：O(n^2)。
空间复杂度：O(1)。
稳定性：稳定。

 public class mp {
    /**
     * 冒泡排序
     * 每次比较相邻的两个数，前者比后者大，两两交换，第一次排序进行n次
     * 第二次排序进行n-1次，以此类推，直到排序完成
     * 时间复杂度o(n^2 ) 空间复杂度o(1)
     */
    public static void main(String[] args) {
        int arr ={2,4,3,1,6,2,9,8};
        mp(arr);
        System.out.println(Arrays.toString(arr));
    }
   public static void mp(intarr){
        int n=arr.length;
        for(int i=0;i<n;i++){
            for(int j=0;j<n-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int tmp=arr[j];
                    arr[j]=arr[j+1];
                    arr[j+1]=tmp;
                }
            }
        }
   }
}

3. 快速排序（Quick Sort）

基本思想：通过一趟排序将待排记录分隔成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
时间复杂度：平均时间复杂度为O(nlogn)，最坏情况下为O(n^2)。
空间复杂度：取决于递归的深度，平均情况下为O(logn)，最坏情况下为O(n)。
稳定性：不稳定。

public static void kp(intarr,int left,int right){
    if(left>=right)
        return ;
    int t=arr[left];
    int i=left;
    int j=right;
    while(i!=j){
        while (arr[j]>=t&&i<j){
            j--;
        }
        while(arr[i]<=t&&i<j){
            i++;
        }
        int tmp=arr[i];
        arr[i]=arr[j];
        arr[j]=tmp;
    }
    //交换两者位置
    arr[left]=arr[i];
    arr[i]=t;
    kp(arr,left,i-1);
    kp(arr,i+1,right);
}

4.归并排序（Merge Sort）

基本思想：建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。
时间复杂度：O(nlogn)。
空间复杂度：O(n)，因为需要用到与输入数组等长的额外空间来进行合并操作。
稳定性：稳定。

 public static void split(intarr,int left,int right) {
     if(left==right){
         return;
     }
    int mid=(left+right)/2;
    split(arr,left,mid);
    split(arr,mid+1,right);
   merge(arr,left,mid,right);
 }

 //合并
 public static void merge(int[]arr,int left,int mid,int right) {
     //创建临时数组
   inttmp=new int[right-left+1];
   int s1=left;
   int s2=mid+1;
   int t=0;
   while(s1<=mid&&s2<=right){
       if(arr[s1]>arr[s2]){
           tmp[t]=arr[s2];
           s2++;
           t++;
       }else{
           tmp[t]=arr[s1];
           s1++;
           t++;
       }
   }
  //考虑有一边结束的情况
     while(s2<=right){
         tmp[t]=arr[s2];
         s2++;
         t++;
     }
     while(s1<=mid){
         tmp[t]=arr[s1];
         t++;
         s1++;
     }
     //把临时数组当中的数据放回原数组
     for(int j=0;j<tmp.length;j++) {
         arr[left+j]=tmp[j];
     }
 }