经典排序算法

• 排序算法
• 前言
• • 一.冒泡排序
  • 二.选择排序
  • 三.插入排序
  • 四.希尔排序
  • 五.快速排序
  • 六.归并排序
  • 七.堆排序
  • 八.计数排序
  • 九.桶排序

基本排序算法(java)

每次比较，将大值向后两两交换

//冒泡
 public int[] BubbleSort(int[] array){

        for (int i = 0; i < array.length; i++) {
            for (int j = 0; j < array.length-i-1; j++) {
                if(array[j]>array[j+1]){
                    int tmp=array[j];
                    array[j]=array[j+1];
                    array[j+1]=tmp;
                }
            }
        }
        return array;
    }

每次从当前值向后扫描，找出最小值的索引与当前值交换。

//选择排序
 public int[] SecSort(int[] array){
        for (int i = 0; i < array.length; i++) {
            int minIndex=i;
            for (int j = i; j array[j]){
                    minIndex=j;
                }
            }
            if(minIndex!=i){
            int tmp=array[i];
            array[i]=array[minIndex];
            array[minIndex]=tmp;}

        }
        return array;


    }

前面为已排序序列，将未排序序列中的当前值插入到前面已排序序列

//插入排序
 public int[] InsertSort(int[] array){
        for (int i = 0; i < array.length-1; i++) {
           int cur=array[i+1];
           int index=i;
           while (index>=0&&cur 
四.希尔排序 
对数组进行分组，分别进行插入排序。每次分组排序完成之后减少增量。
 
//希尔排序
    public int[] ShellSort(int[] array){
        int gap=array.length/2;
        while (gap>0){
            for (int i = 0; i < array.length; i++) {
                int cur=array[i];
                int index=i-gap;
                while (index>=0&&cur 
五.快速排序 
    public void QuickSort(int[] array,int a,int b){
        if(a>=b){
            return ;
        }
        int index=indexFind(array,a,b);
        QuickSort(array,a,index-1);
        QuickSort(array,index+1,b);

    }
    private int indexFind(int[] array,int s,int e){
        int index=array[s];
        while (sarray[s])s++;
            array[s]=array[e];
        }
        array[s]=index;
        return s;
    }
 
六.归并排序 
//归并排序
public int[] MergeSort(int[] array){
        if(array.length<2){
            return array;
        }
        int mid=array.length/2;
        int[] left= Arrays.copyOfRange(array,0,mid);
        int[] right=Arrays.copyOfRange(array,mid,array.length);
        return Merge(MergeSort(left),MergeSort(right));
    }
    
    private int[] Merge(int[] left,int[] right){
        int[] ans=new int[left.length+right.length];
        int index=0;
        for (int i = 0,a=0,b=0; i right[b]){
                ans[index++]=right[b++];
            }else if(a>=left.length){
                ans[i]=right[b++];
            }else if(b>=right.length){
                ans[i]=left[a++];
            }
            
        }
        return ans;
        
        
    } 
 
七.堆排序 
构成最大堆，堆顶元素与最后一个元素交换并重新调整堆。
 
//堆排序
   public int[] HeapSort(int[] array){
        int len=array.length;
        for (int i = (len/2-1); i >=0; i--) {
            help(array,i,len);
        }


        for (int i = len-1; i >=0 ; i--) {
            int tmp=array[0];
            array[0]=array[i];
            array[i]=tmp;
            help(array,0,i);

        }
        return array;

    }
    private void help(int[] array,int index,int length){
        int max=index;
        int lc=index*2;
        int rc=index*2+1;
        if (length>lc&&array[max]rc&&array[max] 
八.计数排序 
将数值化为键值存储在额外开辟的数组空间中
 
//计数排序

public static int[]  countSort(int[] array){
        int min=array[0];
        int max=array[0];
        for (int i = 0; i < array.length; i++) {
            if(min>array[i]){
                min=array[i];
            }
            if(max0){
                    array[index++]=j+min;
                    cnt--;
                }
            }
            return ans;



    }
 
九.桶排序 
将数据放入每个桶中，再进行排序。
 
//桶排序
    public static int[] bucketSort(int[] array){
        int max=array[0];
        int min=array[0];
        for (int i = 0; i array[i]){
                min=array[i];
            }
        }
        int butNum=array.length;
        ArrayList> but=new ArrayList<>();
        for (int i = 0; i < butNum; i++) {
            but.add(new ArrayList<>());
        }
        for (int i = 0; i  li=but.get(i);
            for (Integer nu: li) {
                result[index++]=nu;
            }

        }
        return result;

    }