内部排序

一、冒泡排序

public class 冒泡排序 {
    public static void main(String[] args) {
        int[] a=new int[10];
        for (int i = 0; i < 10; i++) {
            a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
            System.out.print(a[i]+" ");
        }
        System.out.println("\n");

        for (int i = a.length-1; i > 0; i--) {
            boolean flag=true;// 设定一个标记，若为true，则表示此次循环没有进行交换，也就是待排序列已经有序，排序已经完成
            for (int j = 0; j < i; j++) {
                if(a[j]>a[j+1]){
                    int temp = a[j];
                    a[j]=a[j+1];
                    a[j+1]=temp;
                    flag=false;
                }
            }
            if (flag) {
                break;
            }
        }

        for (int i = 0; i < 10; i++) {
            System.out.print(a[i] + " ");
        }
    }
}

二、选择排序

public class 选择排序 {
    public static void main(String[] args) {
        int[] a=new int[10];
        for (int i = 0; i < 10; i++) {
            a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
            System.out.print(a[i]+" ");
        }
        System.out.println("\n");

        for (int i = 0; i < a.length-1; i++) {
            int min=i;
            for (int j = i+1; j <a.length ; j++) {
                // 记录目前能找到的最小值元素的下标
                if(a[j]<a[min]){
                    min=j;
                }
            }
            if (i!=min) {
                int temp=a[i];
                a[i]=a[min];
                a[min]=temp;
            }
        }

        for (int i = 0; i < 10; i++) {
            System.out.print(a[i] + " ");
        }
    }
}

三、插入排序

public class 插入排序 {
    public static void main(String[] args) {
        int[] a=new int[10];
        for (int i = 0; i < 10; i++) {
            a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
            System.out.print(a[i]+" ");
        }
        System.out.println("\n");

        Insertsort(a);//插入排序

        for (int i = 0; i < 10; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void Insertsort(int[] a){
        for (int i = 1; i < a.length; i++) {
            int number=a[i];
            int j;
            for (j=i;j>0&&number<a[j-1];j--) {
                // 从已经排序的序列最右边的开始比较，找到比其小的数
                a[j]=a[j-1];
            }
            if (j!=i) {
                a[j]=number;
            }
        }
    }
}

四、折半插入排序

public class 折半插入排序 {
    public static void main(String[] args) {
        int[] a=new int[10];
        for (int i = 0; i < 10; i++) {
            a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
            System.out.print(a[i]+" ");
        }
        System.out.println("\n");

        HalveInsertsort(a);//折半插入排序

        for (int i = 0; i < 10; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void HalveInsertsort(int[] a){
        for (int i = 1; i < a.length; i++) {
            int number=a[i];

            int low=0,high=i;
            while (low<=high) {
                int mid=low+(high-low)/2;
                if (number<a[mid]) {
                    high=mid-1;
                } else if (number>a[mid]) {
                    low=mid+1;
                }else{
                    low=mid;
                    break;
                }
            }

            int k;
            for(k=i;k>low;k--){
                a[k]=a[k-1];
            }

            a[k]=number;
        }
    }
}

五、希尔排序

//希尔排序：希尔排序是基于插入排序而提出改进方法的
public class 希尔排序 {
    public static void main(String[] args) {
        int[] a=new int[10];
        for (int i = 0; i < 10; i++) {
            a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
            System.out.print(a[i]+" ");
        }
        System.out.println("\n");

        Shell_Sort(a,a.length);//希尔排序

        for (int i = 0; i < 10; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void Shell_Sort(int[] a,int n){
        int increment=n;//增量
        do{
            increment=increment/3+1;
            ShellPass(increment,n,a);
        }while (increment>1);
    }

    public static void ShellPass(int d,int n,int[] a){
        int j;
        for (int i=d;i<n;i++) {
            if (a[i] < a[i - d]) {
                int number = a[i];
                for (j = i - d; j >= 0 && a[j] > number; j -= d) {
                    a[j + d] = a[j];
                }
                a[j + d] = number;
            }
        }
    }
}

六、快速排序

//快速排序算是在冒泡排序基础上的递归分治法
public class 快速排序 {
    public static void main(String[] args) {
        int[] a=new int[10];
        for (int i = 0; i < 10; i++) {
            a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
            System.out.print(a[i]+" ");
        }
        System.out.println("\n");

        QKsort(a,0,a.length-1);

        for (int i = 0; i < 10; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void QKsort(int[] a,int low,int high){
        int pos;
        if(low<high){
            pos=QKpass(a,low,high);
            QKsort(a,low,pos-1);
            QKsort(a,pos+1,high);
        }
    }

    public static int QKpass(int[] a,int low,int high){
        int x=a[low];
        while (low<high) {
            while (low<high&&a[high]>x) {high--;}
            if (low<high) {a[low]=a[high];}

            while (low<high&&a[low]<x) {low++;}
            if (low<high) {a[high]=a[low];}
        }
        a[low]=x;
        return low;
    }
}

七、归并排序

public class 归并排序 {
    public static void main(String[] args) {
        int[] a=new int[10];
        for (int i = 0; i < 10; i++) {
            a[i]=(int)(10+Math.random()*90);//产生10-100之间的随机数
            System.out.print(a[i]+" ");
        }
        System.out.println("\n");

        MergeSort(a,0,a.length-1);//归并排序

        for (int i = 0; i < 10; i++) {
            System.out.print(a[i] + " ");
        }
    }

    public static void MergeSort(int[] a,int low,int high){
        if(low<high){
            int mid=low+(high-low)/2;
            MergeSort(a,low,mid);
            MergeSort(a,mid+1,high);
            Merge(a,low,mid,high);
        }
    }

    public static void Merge(int[] a,int low,int mid,int high){
        int[] temp=new int[a.length];

        int i=low,j=mid+1,k=low;
        while (i<=mid&&j<=high) {
            if(a[i]<a[j]){temp[k]=a[i];i++;}
            else{temp[k]=a[j];j++;}
            k++;
        }
        while (i<=mid) {temp[k]=a[i];i++;k++;}
        while (j<=high) {temp[k]=a[j];j++;k++;}

        for (int i1 : temp) {
            System.out.print(i1+" ");
        }
        System.out.print('\n');

        for (int e = low; e <= high; e++) {
            a[e]=temp[e];
        }
    }
}

八、堆排序

import java.util.Arrays;

public class HeapSort {
    public static void main(String []args){
        int []arr = {7,6,7,11,5,12,3,0,1};
        System.out.println("排序前："+Arrays.toString(arr));
        sort(arr);
        System.out.println("排序前："+Arrays.toString(arr));
    }
 
    public static void sort(int []arr){
        //1.构建大顶堆
        for(int i=arr.length/2-1;i>=0;i--){
            //从第一个非叶子结点从下至上，从右至左调整结构
            adjustHeap(arr,i,arr.length);
        }
        //2.调整堆结构+交换堆顶元素与末尾元素
        for(int j=arr.length-1;j>0;j--){
            swap(arr,0,j);//将堆顶元素与末尾元素进行交换
            adjustHeap(arr,0,j);//重新对堆进行调整
        }
 
    }
 
    // 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上）
    public static void adjustHeap(int []arr,int i,int length){
        int temp = arr[i];//先取出当前元素i
        for(int k=i*2+1;k<length;k=k*2+1){//从i结点的左子结点开始，也就是2i+1处开始
            if(k+1<length && arr[k]<arr[k+1]){//如果左子结点小于右子结点，k指向右子结点
                k++;
            }
            if(arr[k] >temp){//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
                arr[i] = arr[k];
                i = k;
            }else{
                break;
            }
        }
        arr[i] = temp;//将temp值放到最终的位置
    }
 
    //交换元素
    public static void swap(int []arr,int a ,int b){
        int temp=arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }
}

参考来源：https://blog.csdn.net/qq_36186690/article/details/82505569

九、基数排序

public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {63, 157, 189, 51, 101, 47, 141, 121, 157, 156,
                194, 117, 98, 139, 67, 133, 181, 12, 28, 0, 109};

        radixSort(arr);

        System.out.println(Arrays.toString(arr));
    }

    /**
     * 高位优先法
     *
     * @param arr 待排序列，必须为自然数
     */
    private static void radixSort(int[] arr) {
        //待排序列最大值
        int max = arr[0];
        int exp;//指数

        //计算最大值
        for (int anArr : arr) {
            if (anArr > max) {
                max = anArr;
            }
        }

        //从个位开始，对数组进行排序
        for (exp = 1; max / exp > 0; exp *= 10) {
            //存储待排元素的临时数组
            int[] temp = new int[arr.length];
            //分桶个数
            int[] buckets = new int[10];

            //将数据出现的次数存储在buckets中
            for (int value : arr) {
                //(value / exp) % 10 :value的最底位(个位)
                buckets[(value / exp) % 10]++;
            }

            //更改buckets[i]，
            for (int i = 1; i < 10; i++) {
                buckets[i] += buckets[i - 1];
            }

            //将数据存储到临时数组temp中
            for (int i = arr.length - 1; i >= 0; i--) {
                temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i];
                buckets[(arr[i] / exp) % 10]--;
            }

            //将有序元素temp赋给arr
            System.arraycopy(temp, 0, arr, 0, arr.length);
        }

    }
}

参考来源：https://www.cnblogs.com/luomeng/p/10639926.html