栏目分类:
子分类:
返回
名师互学网用户登录
快速导航关闭
当前搜索
当前分类
子分类
实用工具
热门搜索
名师互学网 > IT > 软件开发 > 后端开发 > Java

十大排序(Java)

Java 更新时间: 发布时间: IT归档 最新发布 模块sitemap 名妆网 法律咨询 聚返吧 英语巴士网 伯小乐 网商动力

十大排序(Java)

十大排序 (java)

冒泡排序

算法实现:

假设数组长度为N:
1,从第一个数据开始,比较相邻两个数据,如果前面数据大于后面数据,就交换两个数值;
2,遍历该数组,一次遍历结束后最大的数值就跑到了最后一位(即第N-1个位置);
3,N = N-1(最大数值位置已定不用再管);只要N不等于0就重复第二步骤,直至排序完成。

import java.util.Arrays;

public class Bubblen {
    public static void sort(int[] arr){
        for (int i = 0; i < arr.length - 1; i++) {
            boolean boo = true;
            for (int j = 0; j < arr.length - i - 1; j++) {
                 if(arr[j] > arr[j + 1]){
                     int temp = arr[j];   // 额外的空间
                     arr[j] = arr[j+1];
                     arr[j+1] = temp;
                     boo = false;
                 }
            }
            if(boo){
                break;   // 如果一趟循环下来,没有交换过,数组就是有序的,直接退出循环
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {1,4,8,4,5,6,32,54,3,2,4,11,2,3};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
选择排序

算法实现:在未排序的数组中找到最小(最大)的值,放到第一(最后位置),以此类推到最后一个

import java.util.Arrays;


public class Choice {
    public static void sort(int[] arr){
        for (int i = 0; i < arr.length; i++) {
            int min = i;
            for (int j = i; j < arr.length; j++) {
                if(arr[min] > arr[j]){
                    min = j;
                }
            }
            if(min != i){
                int temp = arr[min];
                arr[min] = arr[i];
                arr[i] = temp;
            }
        }
    }
    public static void main(String[] args) {
        int[] arr = {2,4,1,5,6,9,10,1,2,22,3,4,7};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
插入排序
import java.util.Arrays;

public class Insert {
    public static void sort(int[] arr){
        for (int i = 1; i < arr.length; i++) { // i = 1 第一元素不用比较
            int temp = arr[i];
            int j = i - 1;  // 从右往左 进行比较,左边是有序的
            while(j >= 0 && arr[j] > temp){ // 直到j到达第一个数 或者 小于temp 停止比较
                arr[j + 1] = arr[j]; // 数一直比temp大 就一直移动  且数组的值往后移
                j--;
            }
            arr[j + 1] = temp; //  最终找到比它小的 放在其后
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,4,5,6,1,3,9,7,10,2,11};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
希尔排序
import java.util.Arrays;

public class Shell {
    public static void sort(int[] arr){
      // group 为每次分组的增量
     for (int group = arr.length/2; group >= 1; group = group/2){
         for (int i = group; i < arr.length; i++) {
             // 分组进行插入排序
             //  移动法 这个比较好,while可以减少一些比较次数
              int temp = arr[i];
              int j = i - group;
              while(j >=0 && arr[j] > temp){
                  arr[j + group] = arr[j];
                  j -= group;
              }
              arr[j + group] = temp;
             
         }
     }
 }
    public static void main(String[] args) {
        int[] arr = {2,3,4,2,1,6,7,4,8,9,10,2,6};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
归并排序
import java.util.Arrays;

public class Merge {

    public static void sort(int[] arr, int left, int right, int[] temp){
        if(left < right){
            int mid = (left + right) / 2;
            sort(arr, left, mid, temp);   // 对左边的序列进行归并排序
            sort(arr, mid+1, right, temp);  // 对有变动的序列进行归并排序
            merge(arr,left,mid,right,temp); // 合并两个有序队列
        }
    }
    public static void merge(int[] arr, int left, int mid, int right, int[] temp){
        int index = 0;  // temp的索引
        int first = left, second = mid + 1;  // 两个序列的起始索引
        while(first <= mid && second <= right){
            if(arr[first] <= arr[second]){    // 注意:这里要 <= 才能保证排序是稳定的 ,如果是 < 则不稳定
                temp[index++] = arr[first++];
            }else{
                temp[index++] = arr[second++];
            }
        }
        // 把剩余的序列,拷贝到temp[] 上
        while(first <= mid){
            temp[index++] = arr[first++];
        }
        while(second <= right){
            temp[index++] = arr[second++];
        }
        //排序好的temp[] 赋值 到原数组上, 原数组就排序好了 这一步很关键
        for (int i = 0; i < index; i++) {
            arr[left + i] = temp[i];  // left + i;
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,4,6,7,2,3,4,1,3,8,9};
        int[] temp = new int[arr.length];
        sort(arr,0, arr.length - 1, temp);
        System.out.println("arr数组:" + Arrays.toString(arr));
        System.out.println("temp数组:" + Arrays.toString(temp));
    }

}

快速排序
import java.util.Arrays;

public class Quick {
    //递归
    public static void quickSort(int[] arr, int left, int rigth){
        if(left < rigth) {
            int index = getIndex(arr, left, rigth);
            quickSort(arr, left, index - 1);
            quickSort(arr, index + 1, rigth);
        }
    }
    //得到排序好位置的基值得位置(枢轴)
    public static int getIndex(int[] arr, int left, int rigth){
        int num = arr[left];  //基值
        while(left < rigth){
            // 前后顺序不能反了, 因为我们是以第一个元素为基值 arr[left]
            while(left < rigth && arr[rigth] >= num){
                rigth--;
            }
            arr[left] = arr[rigth];
            while(left < rigth && arr[left] <= num) {
                left++;
            }
            arr[rigth] = arr[left];
        }
        arr[left] = num;
        return left;
    }

    public static void main(String[] args) {
        int[] arr = {2,3,7,5,8,9,12,4,6,2};
        quickSort(arr, 0, arr.length-1);
        System.out.println(Arrays.toString(arr));
    }
}
堆排序
import java.util.Arrays;


public class Heap {
    public static void sort(int[] arr){
       //1.首先要构建大顶推
        for (int i = arr.length/2 - 1; i >= 0 ; i--) {
            //从第一个非叶子节点从下至上,从右至左调整结构
            heap(arr, i, arr.length);
        }
        //2.再在大顶推的基础上,把堆顶的最大元素放到数组的末尾,堆长度减一,再继续调整前面的堆结构
        for (int i = arr.length - 1; i >0 ; i--) {
            swap(arr,0, i );
            heap(arr, 0, i);
        }
    }
    public static void heap(int[] arr, int node, int length){
        int temp = arr[node];

        for (int i = 2*node + 1; i < length; i = 2*i + 1) {//从i结点的左子结点开始,也就是2i+1处开始
            if(i + 1 < length && arr[i] < arr[i+1]){ //如果左子结点小于右子结点,k指向右子结点
                i++;
            }
            if(arr[i] > temp){ //如果子节点大于父节点,将子节点值赋给父节点(不用进行交换)
                arr[node] = arr[i];
                node = i;
            }else{
                break;
            }
        }
        arr[node] =temp;  //将temp值放到最终的位置
    }
    //元素交换
    public static void swap(int[] arr, int a, int b){
        int temp = arr[a];
        arr[a] = arr[b];
        arr[b] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {7, 6, 7, 11, 5, 12, 3, 0, 1};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
计数排序
import java.util.Arrays;

public class Count {
    public static void sort(int[] arr){
        int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if(arr[i] > max){
                max = arr[i];
            }
            if(min > arr[i]){
                min = arr[i];
            }
        }
        int[] array = new int[max - min + 1];  // 新建一个数组区间来记录各个值的数量
        for (int i = 0; i < arr.length ; i++) {
            array[arr[i] - min]++;
        }
        int index = 0;
        for (int i = 0; i < array.length; i++) {  // 遍历区间数组,进行排序
            if(array[i] > 0){
                for (int j = 0; j < array[i]; j++) {
                    arr[index++] = min + i;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2,4,5,6,1,3,9,7,10,2,11};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
桶排序
import java.util.Arrays;


public class Bucket {
    public static void sort(int[] arr, int num){ // num 为桶的数量
       int max = Integer.MIN_VALUE, min = Integer.MAX_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if(max < arr[i]){
                max = arr[i];
            }
            if(min > arr[i]){
                min = arr[i];
            }
        }
        //求出每个桶的长度,这里必须使用Double
        double size=(double)(max-min+1)/num;
        ArrayList list[] = new ArrayList[num];
        for (int i = 0; i < num; i++) {
            list[i] = new ArrayList();
        }

        for (int i = 0; i < arr.length; i++) {
            insert(list[(int)Math.floor((arr[i] - min)/size)], arr[i]);
        }

        //遍历每一个桶,把排序好的桶的值,赋值给原数组
        int index= 0;
        for (int i = 0; i < num; i++) {
            for (int j = 0; j < list[i].size(); j++) {
                arr[index++] = list[i].get(j);
            }
        }
    }
    // 在桶的链表里插入新的元素,采用插入排序
    public static void insert(ArrayList list, int value){
       if(list == null || list.size() == 0){
           list.add(value);
       }else{
           int size = list.size() - 1;
           while(size >= 0 && list.get(size) > value){
              if(size == (list.size() - 1)){
                  list.add(list.get(size));
              }else{
                  list.set(size + 1, list.get(size));
              }
              size--;
           }
           if(size != (list.size() - 1)){
               list.set(size + 1, value);
           }else{
               list.add(value);
           }
       }
    }

    public static void main(String[] args) {
        int[] arr = {2,2,2,2,2,2,2};
        sort(arr, 4);  // 可以自定义桶的数量
        System.out.println(Arrays.toString(arr));
    }
}
基数排序

算法实现:根据数位来进行比较排序的,从个位开始

import java.util.ArrayList;
import java.util.Arrays;

public class Base {
    public static void sort(int[] arr){
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if(max < arr[i]){
                max = arr[i];
            }
        }
        //数位 0 - 9
        ArrayList list[] = new ArrayList [10];
        for(int i = 0; i < 10; i++){
            list[i] = new ArrayList();
        }
        int k = 1; // k 表示数位
        for (int i = 0; i < String.valueOf(max).length(); i++) {
            base(arr, list, k);
            k *= 10;
        }

    }
    public static void base(int[] arr, ArrayList list[], int k){ // k 表示数位
        for (int i = 0; i < arr.length; i++) {
            list[arr[i]/k%10].add(arr[i]);
        }
        //把排序完的数组合并到原数组上
        int index = 0;
        for (int i = 0; i < list.length; i++) {
            for (int j = 0; j < list[i].size(); j++) {
                arr[index++] = list[i].get(j);
            }
            list[i].clear();  // 去清空list
        }
    }

    public static void main(String[] args) {
        int[] arr = {11,13,12,15,2,3,5,6,23,21,28,29};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
转载请注明:文章转载自 www.mshxw.com
本文地址:https://www.mshxw.com/it/981034.html
我们一直用心在做
关于我们 文章归档 网站地图 联系我们

版权所有 (c)2021-2022 MSHXW.COM

ICP备案号:晋ICP备2021003244-6号