常见排序算法

void QuickSort(int[] arr,int begin,int end)
{
    //返回条件！！
    if(begin>end)
    {
        return;
    }
    int i=begin;
    int j=end;
    int flag=arr[i];
    while(i<j)
    {
        //一定要从右开始找！！！
        while(arr[j]>=flag&&j>i)
        {
            j--;
        }
        while(arr[i]<=flag&&i<j)
        {
            i++;
        }
        int temp=arr[i];
        arr[i]=arr[j];
        arr[j]=temp;
    }
    arr[begin]=arr[i];
    arr[i]=flag;
    //左边的数都比基准数小，右边的都比基准数大，两个数组再分别排序
    QuickSort(arr, begin, i-1);
    QuickSort(arr, i+1, end);
}
/////////////////////////////////////////////
int[] BubbleSort(int[] arr)
{
    //两个for循环
    for (int i=0;i<arr.length-1;i++)
    {
        for(int j=arr.length-1;j>i;j--)
        {
            if(arr[j]<arr[j-1])
            {
                int temp=arr[j];
                arr[j]=arr[j-1];
                arr[j-1]=temp;
            }
        }
    }
    return arr;
}
///////////////////////////////////////////////////////
//为什么  h<arr1.length 比  h<h+gap速度快
    int[]ShellSort(int[] arr1)
{
    //第一个循环不断缩小gap；第二个循环把按照gap分类的每个数组都用插入排序
    for(int gap=arr1.length/2;gap>0;gap=gap/2)
    {
        for(int h=gap;h<arr1.length;h++)
        {
            arr1=InsertSort(arr1, gap, h);
        }
    }
    return arr1;
}
//////////////////////////////////////////////////////
int[] InsertSort(int[]arr1,int gap,int h)
{
    if(arr1==null||arr1.length==1)
        return arr1;
    //第一个循环从前往后确定需要移动的数
    for(int i=h;i<arr1.length;i=i+gap)
    {
        int current=arr1[i];
        int preIndex=i-gap;
        //第二个循环从后往前确定插入的位置
        while(preIndex>=0&&arr1[preIndex]>current)
        {
            arr1[preIndex+gap]=arr1[preIndex];
            preIndex=preIndex-gap;
        }
        arr1[preIndex+gap]=current;
    }
    return arr1;
}
///////////////////////////////////////////////////////////
void MergeSort(int []arr1,int low,int high)
{
    if(low<high)
    {
    int mid=(low+high)/2;
    MergeSort(arr1, low, mid);
    MergeSort(arr1, mid+1, high);
    Merge(arr1, low, high);
    }
}
//有序数组的合并
void Merge(int[]arr1,int low,int high)
{
    //先比较两个数组的大小，如果一个数组排完了则把另一数组剩下的数全部存入
    int p1=low;
    int p2=(low+high)/2+1;
    int count=0;
    int[]SortedArr=new int[high-low+1];
    while(p1<=((low+high)/2)&&p2<=high)
    {
        if(arr1[p1]<arr1[p2])
        {
            SortedArr[count++]=arr1[p1++];
        }
        else {
            SortedArr[count++]=arr1[p2++];
        }

    }
    while(p1<(low+high)/2+1)
    {
        SortedArr[count++]=arr1[p1++];            
    }
    while(p2<high+1)
    {
        SortedArr[count++]=arr1[p2++];            
    }
    for(int i=low;i<high+1;i++)
    {
        arr1[i]=SortedArr[i-low];
        System.out.print(arr1[i]+" ");

    }

    System.out.println();
}


static void InsertSort(int[]arr)
{
    for(int i=1;i<arr.length;i++)
    {
        int j=i;
        int current=arr[j];
        while(arr[j-1]>current&&j>0)
        {
            arr[j]=arr[j-1];
            j--;
        }
        arr[j]=current;
    }
}

void shell(int[]arr)
{
    for(int gap=arr.length/2;gap>0;gap=gap/2)
    {
        for(int i=gap;i<arr.length;i++)
        {
            //插入排序
            int current=arr[i];
            while((i-gap)>=0&&arr[i-gap]>current)
            {
                arr[i]=arr[i-gap];
                i=i-gap;
            }
            arr[i]=current;
        }
        for(int i=0;i<arr.length;i++)
              {
                  System.out.print(arr[i]+" ");
              }
        System.out.println();
    }
}
//////////////////////////////////////////////////////////////////
void SelectSort(int[]arr) {
    for(int i=0;i<arr.length;i++)
    {
        int minIndex=i;
        for(int j=i;j<arr.length;j++)
        {
            if (arr[j]<arr[minIndex])
            {
                minIndex=j;
            }
        }
        int temp=arr[i];
        arr[i]=arr[minIndex];
        arr[minIndex]=temp;
    }