排序总结

冒泡排序

public static void sort01(int[] arr)
    {
        for(int i=arr.length-1;i>=0;i--)//外反
        {
            for(int j=0;j<i;j++)//内正(判断条件j<i)
            {
                if(arr[j]>arr[j+1])//交换元素j和j+1
                {
                    swap(arr,j,j+1);
                }
            }
        }
    }

插入排序

public static void sort02(int[] arr)
    {
        for(int i=1;i<arr.length;i++)
        {
            for(int j=i-1;j>-1&&arr[j]>arr[j+1];j--)
            {
                swap(arr,j,j+1);
            }
        }
    }

选择排序

public static void sort03(int[] arr)
    {
        int minIndex=0;
        for(int i=0;i<arr.length;i++)
        {
            minIndex=i;
            for(int j=i+1;j<arr.length;j++)
            {
                minIndex=arr[minIndex]>arr[j]?j:minIndex;
            }
            swap(arr,i,minIndex);
        }
    }

堆排序

public static void sort(int[] arr)
    {
        for(int i=0;i<arr.length;i++)
        {
            heapInsert(arr,i);
        }
        int size=arr.length;
        swap(arr,0,--size);
        while(size>0)
        {
            heapify(arr,0,size);
            swap(arr,0,--size);
        }
    }
public static void heapify(int[] arr,int index,int size)
    {
         int left=index*2+1;
         while(left<size)
         {
             int largest=left+1<size&&arr[left+1]>arr[left]?left+1:left;
             largest = arr[largest] > arr[index] ? largest : index;

             if(largest==index)
             {
                 break;
             }
             swap(arr,largest,index);
             index=largest;
             left=index*2+1;
         }
    }
public static void heapInsert(int[] arr,int index)
    {
        while(arr[(index-1)/2]<arr[index])
        {
            swap(arr,(index-1)/2,index);
            index=(index-1)/2;
        }
    }

快速排序

public static void swap(int[] arr,int m,int n)
    {
        int temp=arr[m];
        arr[m]=arr[n];
        arr[n]=temp;
    }

public static void sort03(int[] arr)
    {
        quickSort(arr,0,arr.length-1);
    }

public static void quickSort(int[] arr,int l,int r)
    {
        if(l<r)
        {
             swap(arr,r,l+(int)Math.random()*(r-l+1));
             int[] p=parition(arr,l,r);
             quickSort(arr,l,p[0]-1);
             quickSort(arr,p[1]+1,r);
        }
    }
public static int[] parition(int[] arr,int l,int r)
    {
        int less=l-1;
        int more=r;
        while(l<more)
        {
            if(arr[l]>arr[r])
            {
                swap(arr,--more,l);
            }
            else if(arr[l]<arr[r])
            {
                swap(arr,++less,l++);
            }
            else
            {
                l++;
            }
        }
        swap(arr,more,r);
        return new int[]{less+1,more};
    }

归并排序

public static void mergeSort(int[] arr,int l,int r)
{
        if(l==r)
        {
            return;
        }
        int mid = l + ((r - l) >> 1);
        mergeSort(arr,l,mid);
        mergeSort(arr,mid+1,r);
        merge(arr,l,r,mid);
}
public static void merge(int[] arr,int l,int r,int mid)
{
        int index=0;
        int p1=l;
        int p2=mid+1;
        int[] help=new int[r-l+1];
        while(p1<mid+1&&p2<r+1)
        {
            help[index++]=arr[p1]<arr[p2]?arr[p1++]:arr[p2++];
        }
        while(p1<mid+1)
        {
            help[index++]=arr[p1++];
        }
        while(p2<r+1)
        {
            help[index++]=arr[p2++];
        }
        for(int i=0;i<=help.length-1;i++)
        {
            arr[l+i]=help[i];
        }
}