A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 逆风TO 黑马粉丝团   /  2020-3-31 10:41  /  5432 人查看  /  46 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

简单选择排序:
[JavaScript] 纯文本查看 复制代码
public class EasySelectSort {
    public static void main(String[] args) {
        int arr[]={1,4,6,8,2,5,3,7,9};
        System.out.println("数组排序前顺序:");
        for (int n:arr){
            System.out.print(n+" ");
        }

        //简单选择排序
        selectSort(arr);

        System.out.println("\n数组排序后顺序:");
        for (int n :arr){
            System.out.print(n+" ");
        }

    }
    //简单选择排序
    private static void selectSort(int[] arr){
        int position = 0;//无序序列中的第一个位置
        //外层循环确定有序区
        for (int i=0;i<arr.length;i++){  //数组下标从0开始
            position = i;
            int temp = arr[i];  //把序列中第一个位置暂时作为最小记录
            //内层循环确定无序区
            for (int j=i+1;j<arr.length;j++){//在无序区查找最小记录
                if (arr[j]<temp){ //若最小记录不在最终位置时则交换位置
                    temp = arr[j];
                    position = j;//此时无序序列中第一个位置
                }
            }
            //最小记录在最终位置时
            arr[position] = arr[i];
            arr[i]=temp;
        }
    }
}

直接插入排序:
[JavaScript] 纯文本查看 复制代码
public class InsertSort {
    public static void main(String[] args) {
         int arr[] ={1,4,6,8,2,5,3,7,9};
        System.out.println("数组排序前顺序:");
        for (int n:arr){
            System.out.print(n+"");
        }

    //直接插入排序
    insertSort(arr);

        System.out.println("\n数组排序后顺序:");
        for (int n:arr){
            System.out.print(n+" ");
        }
  }

    //直接插入排序
    public static void insertSort(int[] arr){
        //外层循环确定待比较数值
        for (int i=1;i<arr.length;i++){//必须i=1,因为开始从第二个数与第一个数进行比较
            int temp=arr[i];//待比较数值
            int j=i-1;
            //内层循环为待比较数值确定其最终位置
            for (;j>=0&&arr[j]>temp;j--){ //待比较数值比前一位置小,应插往前插一位
                //将大于temp的值整体后移一个单位
                arr[j+1]=arr[j];
            }
            arr[j+1]=temp;//待比较数值比前一位置大,最终位置无误
        }
    }
}

堆排序:
[JavaScript] 纯文本查看 复制代码
public class HeapSort {
    public static void main(String[] args) {

[JavaScript] 纯文本查看 复制代码
    int arr[] = {1,4,6,8,2,5,3,7,9};
    System.out.println("数组排序前顺序:");
    for(int n : arr){
        System.out.print(n+" ");
    }

    //堆排序
    heapSort(arr);

    System.out.println("\n数组排序后顺序:");
    for(int n : arr){
        System.out.print(n+" ");
    }
}

//堆排序
private static void heapSort(int []arr){
    //1.构建大根堆
    for (int i=arr.length/2-1;i>=0;i--){//第一个非叶子结点下标i=arr.length/2-1
        //从第一个非叶子结点从下至上,从右至左调整结构
        adjustHeap(arr,i,arr.length);
    }
    //2.交换堆顶元素与末尾元素+调整堆结构
    for (int j=arr.length-1;j>0;j--){//堆末尾元素的下标j=arr.length-1,不能为0,因为它不能是堆顶元素
        //将堆顶元素与末尾元素进行交换
        int temp=arr[0];
        arr[0]=arr[j];
        arr[j]=temp;
        //重新对堆进行调整
        adjustHeap(arr,0,j);
    }
}

//调整大根堆(仅是调整过程,建立在大根堆已构建的基础上)
// arr: 要排序的序列(数组)
// i:   第一个非叶子结点下标
// n:   剩余序列的长度(需要调整的结点个数)

private static void adjustHeap(int []arr,int i,int n){

    int temp = arr[i];//先取出第一个非叶子结点(根节点)
    for(int k=i*2+1;k<n;k=k*2+1){//从i结点的左子结点开始,也就是2i+1处开始
        if(k+1<n && arr[k]<arr[k+1]){//如果左子结点小于右子结点,k指向右子结点(k+1,即2i+2)
            k++;
        }
        if(arr[k] > temp){//如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
            arr[i] = arr[k];
            i = k;
        }else{
            break;
        }
    }
    arr[i] = temp;//将temp值放到最终的位置

}

希尔排序:
[Java] 纯文本查看 复制代码
public class SheelSort {
    public static void main(String[] args) {

        int arr[]={1,4,6,8,2,5,3,7,9};
        System.out.println("数组排序前顺序:");
        for (int n:arr){
            System.out.println(n);
        }

        //希尔排序
        SheelSort(arr);

        System.out.println("\n数组排序后顺序:");
        for (int n:arr){
            System.out.println(n);
        }
    }

    //希尔排序
    private static void SheelSort(int[] arr){
        int i,j,temp,gap=1,len=arr.length;
        while (gap<len/3){
            gap=gap*3+1;
        }

        for (;gap>0;gap/=3){
            for (i=gap;i<len;i++){
                temp = arr[i];
                for (j=i-gap;j>=0&&arr[j]>temp;j-=gap){
                    arr[j+gap]=arr[j];
                }
                arr[j+gap]=temp;
            }
        }
    }
}


 归并排序:
 
public class MergeSort {
    public static void main(String[] args) {

        int arr[] = {1,4,6,8,2,5,3,7,9};
        System.out.println("数组排序前顺序:");
        for(int n : arr){
            System.out.print(n+" ");
        }

        //归并排序
        int lower = 0;
        int upper = arr.length-1;
        mergeSort(arr, lower, upper);

        System.out.println("\n数组排序后顺序:");
        for(int n : arr){
            System.out.print(n+" ");
        }

    }

    //归并排序
    private static void mergeSort(int[] arr, int lower, int upper) {

        if (lower < upper) {
            //找出中间索引
            int middle = (lower + upper)/2;
            //对左边数组进行递归
            mergeSort(arr, lower, middle);  //注意:此处和快速排序不一样,middle不需要减1,组成一个完整序列的下标
            //对右边数组进行递归
            mergeSort(arr, middle+1, upper);
            //合并
            merge(arr, lower, middle, upper);
        }

    }

    //归并
    private static void merge(int[] arr, int lower, int middle, int upper) {

        int[] tempArr = new int[arr.length]; //建立一个中间数组
        int mid = middle + 1; // 第二个子序列的第一个下标
        int third = lower; //third记录中间数组的索引
        int temp = lower;

        while (lower <= middle && mid <= upper) {
            //从两个数组中取出最小的放入中间数组
            if (arr[lower] <= arr[mid]) {
                tempArr[third++] = arr[lower++];
            } else {
                tempArr[third++] = arr[mid++];
            }
        }

        //剩余部分依次放入中间数组
        while (mid <= upper) {
            tempArr[third++] = arr[mid++];
        }

        while (lower <= middle) {
            tempArr[third++] = arr[lower++];
        }

        //将中间数组中的内容复制回原数组
        while (temp <= upper) {
            arr[temp] = tempArr[temp++];
        }

    }
}

基数排序:
[Java] 纯文本查看 复制代码
public class JiShuSort {
    public static void main(String[] args) {

        int arr[] = {1,4,6,8,2,5,3,7,9};
        System.out.println("数组排序前顺序:");
        for(int n : arr){
            System.out.print(n+"");
        }

        //基数排序
        radixSort(arr);

        System.out.println("\n数组排序后顺序:");
        for (int n:arr){
            System.out.print(n+"");
        }
    }

    //基数排序
    private static void radixSort(int[] arr){

        //首先确定排序的趟数
        int max=arr[0];
        for (int i=1;i<arr.length;i++){
            if (arr[i]>max){
                max=arr[i];
            }
        }
        int time=0;
        //判断位数
        while (max>0){
            max/=10;
            time++;
        }

        //建立10个List集合
        List<List<Integer>> list=new ArrayList<List<Integer>>();
        for (int i=0;i<10;i++){
            List<Integer> list1 = new ArrayList<Integer>();
            list.add(list1);
        }

        //进行time次分配和收集
        for (int i=0;i<time;i++){
            //分配数组元素
            for (int n:arr){
                //得到数字的第time+1位数
                int x=n%(int)Math.pow(10,i+1)/(int)Math.pow(10,i);
                List<Integer> list2=list.get(x);
                list2.add(n);
                list.set(x,list2);
            }

            int count =0;//元素计数器
            //收集队列元素
            for (int k=0;k<10;k++){
                while(list.get(k).size()>0){
                    List<Integer> list3=list.get(k);
                    arr[count] = list3.get(0);
                    list3.remove(0);
                    count++;
                }
            }
        }
    }
}


转自CSDN

46 个回复

倒序浏览
66666666666666666666666666
回复 使用道具 举报
6666666666666666666666666666666666666666666666
回复 使用道具 举报
6666666666666666666666666666
回复 使用道具 举报
回复 使用道具 举报
厉害了                     
回复 使用道具 举报
感谢分享  棒棒哒
回复 使用道具 举报
666666666666666
回复 使用道具 举报
可以的,奥利给!!!
回复 使用道具 举报

感谢分享  棒棒哒
回复 使用道具 举报

感谢分享  棒棒哒
回复 使用道具 举报

可以的,奥利给!!!
回复 使用道具 举报
好人一生平安
回复 使用道具 举报


                                                                                                  
键盘敲烂,月薪过万
回复 使用道具 举报
66666666666666666666666
回复 使用道具 举报
666666666666
回复 使用道具 举报
加油加油加油!!!
回复 使用道具 举报
6666666666666666666
回复 使用道具 举报
6666666666666666666666666
回复 使用道具 举报
回复 使用道具 举报
123下一页
您需要登录后才可以回帖 登录 | 加入黑马