题解 | #排序#

JAVA
一、插入排序
二、二分插入排序
三、Shell希尔插入排序
四、冒泡排序
五、快速排序
六、选择排序
七、调用库函数
八、归并排序

冒泡、插入排序，选择排序没有通过编译（可能因为复杂度不满足要求）
自己瞎写的，可能存在问题，欢迎指正。

一、插入排序（复杂度太高，不能通过）

import java.util.*;
public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        int size=arr.length;
        for(int i=1;i<size;++i){
            int temp=arr[i];
            int j=i-1;
            while(j>=0 && arr[j]>temp){
                arr[j+1]=arr[j];
                j--;
            }
            if(j==-1)
                arr[0]=temp;
            else if(arr[j]<=temp){
                arr[j+1]=temp;
            }

        }
        return arr;
    }
}

二、二分插入排序

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        //折半插入
        int size=arr.length;
        for(int i=1;i<size;++i){
            int left=0,right=i-1;
            int temp=arr[i];
            while(left<=right){
                 int mid=(left+right)/2;
                if(temp<arr[mid]){
                    right=mid-1;
                }else if(temp>=arr[mid]){
                    left=mid+1;
                }
            }
            for(int j=i;j>left;--j){
                arr[j]=arr[j-1];
            }
            arr[left]=temp;
        }
        return arr;
    }
}

三、Shell希尔插入排序

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        int size=arr.length;
        int gap=size/2;
        while(gap!=0){
            for(int i=gap;i<size;++i){
                int temp=arr[i];
                int j;
                for(j=i;j>=gap;j-=gap){
                    if(arr[j-gap]>temp)
                        arr[j]=arr[j-gap];
                    else break;
                }
                arr[j]=temp;
            }
            gap=gap/2;
        }
        return arr;
    }
}

四、冒泡排序（复杂度太高，不能通过）

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        int size=arr.length;
        for(int i=1;i<size;++i){
            int flag=1;
            for(int j=size-1;j>=i;--j){
                if(arr[j]<arr[j-1]){
                    int temp=arr[j];
                    arr[j]=arr[j-1];
                    arr[j-1]=temp;
                    flag=0;
                }
            }
            if(flag==1) return arr;
        }
        return arr;
    }
}

五、快速排序

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        quickSort(arr,0,arr.length-1);
        return arr;
    }
    void quickSort(int[] arr,int left,int right){
        if(left>=right) return;
        if(left<right){
            int mid=partition2(arr,left,right);
            quickSort(arr,left,mid-1);
            quickSort(arr,mid+1,right);
        }

    }
    int partition2(int[] arr,int left,int right){

        int temp=arr[left];
        while(left<right){
            while(left<right && arr[right]>=temp)
                right--;
            arr[left]=arr[right];
            while(left<right && arr[left]<=temp)
                left++;
            arr[right]=arr[left];
        }
        arr[left]=temp;
        return left;
    }
}

六、选择排序（复杂度太高，不能通过）

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        int size=arr.length;
        for(int i=0;i<size;++i){
            int min= getMinIndex(arr,i,size-1);
            swap(arr,i,min);
        }
        return arr;
    }
    void swap(int [] arr,int left,int right){
        if(left==right) return;
        int temp=arr[left];
        arr[left]=arr[right];
        arr[right]=temp;
    }
    int getMinIndex(int[]arr,int left,int right){
        if(left>right) return -1;
        else if(left==right) return left;
        int min=arr[left];
        int index=left;
        for(int i=left+1;i<=right;++i){
            if(arr[i]<min){
                min=arr[i];
                index=i;
            }
        }
        return index;
    }
}

七、调用库函数

import java.util.*;
public class Solution {
    public int[] MySort (int[] arr) {
        // write code here
        Arrays.sort(arr);
        return arr;
    }
}

八、归并排序

import java.util.*;
import java.util.ArrayList;

public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 将给定数组排序
     * @param arr int整型一维数组 待排序的数组
     * @return int整型一维数组
     */
    public int[] MySort (int[] arr) {
        // write code here
        mergeSort(arr,0,arr.length-1);
        return arr;
    }
    void mergeSort(int[] arr,int left,int right){
        if(left>=right) return;
        int mid=(left+right)/2;
        mergeSort(arr,left,mid);
        mergeSort(arr,mid+1,right);
        merge(arr,left,mid,right);
    }
    void merge(int []arr,int left,int mid,int right){
        if(left>=right) return;
        int p1=left,p2=mid+1;
        int []help = new int[right-left+1];
        int count=0;
        while(p1<=mid || p2<=right){
            if(p1<=mid&&p2<=right){
                if(arr[p1]<=arr[p2]){
                    help[count++]=arr[p1++];
                }else help[count++]=arr[p2++];
            }else if(p1<=mid && p2>right){
                help[count++]=arr[p1++];
            }else if(p1>mid && p2<=right){
                help[count++]=arr[p2++];
            }
        }
        for(int i=0;i<count;++i){
            arr[left+i]=help[i];
        }

    }
}