[数据结构与算法]排序算法Java实现

1.冒泡排序

package 冒泡排序;

/**
 * 冒泡排序：每次选择相邻两个元素进行比较交换，一共需要进行len-1此轮回，
 * 每次轮回可将一个最值放到应该的位置
 */
public class Bubble_sort {

    public static void sort(int[] array){
        int len=array.length;
        //一共需要进行i-1次操作
        for (int i=0;i<len;i++){
            //将响铃两个元素进行比较交换，array[len-1-i~len-1]为已放好的数组
            for (int j = 0;j<len-1-i;j++){
                if(array[j]>array[j+1]){
                    int t=array[j];
                    array[j]=array[j+1];
                    array[j+1]=t;
                }
            }
        }
    }

    public static void print(int[] array){
        System.out.print("array:");
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

    public static void main(String[] args) {
        int[] array=new int[20];
        for (int i=0;i<20;i++){
            array[i]=(int)(Math.random()*100);
        }
        print(array);
        sort(array);
        print(array);
    }
}

2.选择排序

package 选择排序;

/**
 * 选择排序：从未排序数组中选择一个最小（大）值加入到已排序数组中的末尾
 */

public class Select_sort {

    public static void sort(int[] array){
        int len=array.length;
        int minIndex;
        //array[0~i-1]已排好序的数组，array[i~len-1]未排序的数组
        for (int i=0;i<len-1;i++){
            minIndex=i;
            for (int j=minIndex+1;j<len;j++){
                if(array[j]<array[minIndex]){
                    minIndex=j;
                }
            }
            int t=array[minIndex];
            array[minIndex]=array[i];
            array[i]=t;
        }
    }

    public static void print(int[] array){
        System.out.print("array:");
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

    public static int[] gen(int n){
        int[] array=new int[n];
        for (int i=0;i<n;i++){
            array[i]=(int)(Math.random()*100);
        }
        return array;
    }
    public static void main(String[] args) {
        int[] array=gen(20);
        print(array);
        sort(array);
        print(array);
    }
}

3.插入排序

package 插入排序;

/**
 * 插入排序:将当前值，在排好序的数组中进行比较，将比该值大（小）的元素向后移一位，
 * 并把当前值插入到排好序的数组中比该元素大的元素前面
 */
public class Insert_sort {
    public static void sort(int[] array){
        int len=array.length;
        int preIndex,cur;
        //首先0号元素默认已经排好序
        for (int i=1;i<len;i++){
            //之前排好序的数组最后一个下标
            preIndex=i-1;
            //当前需要插入到排好序的数组中的元素
            cur=array[i];
            //将比该树大的元素向后移一位
            while (preIndex>=0&&cur<array[preIndex]){
                array[preIndex+1]=array[preIndex];
                preIndex--;
            }
            array[++preIndex]=cur;
        }
    }

    public static void print(int[] array){
        System.out.print("array:");
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

    public static int[] gen(int n){
        int[] array=new int[n];
        for (int i=0;i<n;i++){
            array[i]=(int)(Math.random()*100);
        }
        return array;
    }
    public static void main(String[] args) {
        int[] array=gen(20);
        print(array);
        sort(array);
        print(array);
    }
}

4.希尔排序

package 希尔排序;

/**
 * 希尔排序：对待排序的序列分成gap个字序列，分别进行插入排序
 */
public class Shell_sort {
    /**
     * 希尔排序
     * @param array
     * @param m 希尔排序每组的元素数量
     */
    public static void sort(int[] array,int m){
        int len=array.length;
        //gap是希尔排序的增量，即是组数
        //增量gap，并逐步缩小增量
        for (int gap=len/m;gap>0;gap=gap/2){
            //从第gap个元素，逐个对其所在组进行直接插入排序操作
            for (int j=gap;j<len;j++){
                int t=j;
                int curVal=array[t];
                //插入排序
                while(t-gap>=0&&curVal<array[t-gap]){
                    array[t]=array[t-gap];
                    t-=gap;
                }
                array[t]=curVal;
            }
        }
    }

    public static void print(int[] array){
        System.out.print("array:");
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

    public static int[] gen(int n){
        int[] array=new int[n];
        for (int i=0;i<n;i++){
            array[i]=(int)(Math.random()*100);
        }
        return array;
    }
    public static void main(String[] args) {
        int[] array=gen(20);
        print(array);
        sort(array,7);
        print(array);
    }


}

5.归并排序

package 归并排序;

import oracle.jrockit.jfr.parser.FLREventInfo;

public class Merge_sort {
    public static int[] sort(int[] array){
        int len=array.length;
        return merge(array,0,len-1);
    }

    public static int[] merge(int[] array,int left,int right){
        int mid=left+(right-left)/2;
        if(right==left){
            return new int[]{array[left]};
        }
        int[] leftArray=merge(array,left,mid);
        int[] rightArray=merge(array,mid+1,right);
        return mergeSort(leftArray,rightArray);
    }

    public static int[] mergeSort(int[] left,int[] right){
        int len1=left.length;
        int len2=right.length;
        int[] rs=new int[len1+len2];
        int lefti=0,righti=0;
        int i;
        for (i=0;lefti<len1&righti<len2;i++){
            if(left[lefti]<right[righti]){
                rs[i]=left[lefti++];
            }else{
                rs[i]=right[righti++];
            }
        }
        if(lefti==len1){
            while (righti<len2){
                rs[i++]=right[righti++];
            }
        }
        if(righti==len2){
            while (lefti<len1){
                rs[i++]=left[lefti++];
            }
        }
        return rs;
    }

    public static void print(int[] array){
        System.out.print("array:");
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

    public static int[] gen(int n){
        int[] array=new int[n];
        for (int i=0;i<n;i++){
            array[i]=(int)(Math.random()*100);
        }
        return array;
    }
    public static void main(String[] args) {
        int[] array=gen(20);
        print(array);
        int[] rs=sort(array);
        print(rs);
    }
}

6.快速排序

package 快速排序;

/**
 * 快速排序：首先将一个数放在最终该放的位置，然后通过这个位置将数组进行二分
 */
public class Quick_sort {
    public static void sort(int[] array){
        quictSort(array,0,array.length-1);
    }

    public static void quictSort(int[] array,int left,int right){
        if(left>=right){
            return;
        }
        int l=left;
        int r=right;
        int curVal=array[left];
        //将curVal找到最终应该放置的位置
        while (l<r){
            //找到右边第一个小于curVAl的值
            while (l<r&&array[r]>curVal){
                r--;
            }
            //如果是找到第一个小于curVal的值，则需要将左边的值换成该值；
            //并且左边下标需要+1，因为l是刚才小于curVal的值，需要在左边，所以不需要更多操作
            if (l<r){
                array[l++]=array[r];
            }
            //找到左边第一个大于curVal的值
            while (l<r&&array[l]<curVal){
                l++;
            }
            //如果找到，则将右边的值换成该值
            //并且右边下标需要+1，理由同上
            if(l<r){
                array[r--]=array[l];
            }
        }
        //最终退出条件l==r，此时curVal找到最终应该在的位置，所以需要将该curVal赋给l
        array[l]=curVal;
        quictSort(array,left,l-1);
        quictSort(array,l+1,right);
    }

    public static void print(int[] array){
        System.out.print("array:");
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

    public static int[] gen(int n){
        int[] array=new int[n];
        for (int i=0;i<n;i++){
            array[i]=(int)(Math.random()*100);
        }
        return array;
    }
    public static void main(String[] args) {
        int[] array=gen(20);
        print(array);
        sort(array);
        print(array);
    }
}

7.堆排序

package 堆排序;

public class Heap_sort {
    public static void sort(int[] array){
        int len=array.length;
        //第一次构建堆，需要对每个非叶子节点元素进行调整,从第一个非叶子节点开始
        for (int i=len/2;i>=0;i--){
            adjustHeap(array,i,len);
        }
        //无序列表长度为i
        for (int i=len-1;i>0;i--){
            //array[0]为最大值
            int t=array[0];
            array[0]=array[i];
            array[i]=t;
            //对根节点进行堆调整，因为只是根节点被换了
            adjustHeap(array,0,i);
        }
    }

    public static void adjustHeap(int[] array,int i,int len){
        int t=array[i];
        //以i为根节点构建大顶堆，同时找到一个节点刚好比array[i]小，并互换
        for (int k=2*i+1;k<len;k=2*k+1){
            //比较左右节点哪个大
            if(k+1<len&&array[k]<array[k+1]){
                k=k+1;
            }
            //左右节点大的如果比t大，则需要将该节点放到array[i]
            //并且更新i为当前节点（i是最终需要替换为t的节点）
            if(array[k]>t){
                array[i]=array[k];
                i=k;
            }else{
                break;
            }
        }
        array[i]=t;
    }

    public static void print(int[] array){
        System.out.print("array:");
        for (int i=0;i<array.length;i++){
            System.out.print(array[i]+" ");
        }
        System.out.println();
    }

    public static int[] gen(int n){
        int[] array=new int[n];
        for (int i=0;i<n;i++){
            array[i]=(int)(Math.random()*100);
        }
        return array;
    }
    public static void main(String[] args) {
        int[] array=gen(20);
        print(array);
        sort(array);
        print(array);
    }
}

具体算法流程详细