美文网首页
java实现八大排序算法

java实现八大排序算法

作者: Coder_Sven | 来源:发表于2020-05-18 09:50 被阅读0次

冒泡排序

1,比较相邻的元素,如果第一个比第二个大,就交换位置。

2,对每一个相邻元素做同样的操作,做完这一步之后,最后的元素会是最大的数

3,重复以上步骤,直到没有任何一对数字需要比较

    public static void bubbleSort(int [] array){ //第一轮确定最大的数,第二轮确定第二大的数,,依次下去
        //3 1 5 8 2 9 4 6 7
        for(int i=array.length-1;i>0;i--){
            for(int j = 0;j<i;j++){
                if(array[j] > array[j+1]){
                    int temp = array[j];
                    array[j] = array[j+1];
                    array[j+1] = temp;
                }
            }
        }
    }

选择排序

1,从未排序序列中,找到值最小的元素

2,如果最小元素不是未排序序列的第一个元素,将其和未排序序列第一个元素互换

3,重复1,2步,直到排序结束

    //顺序表的排序 (选择排序法)(试用场景:个位数的排序次数)
    public static void selectSort(int [] array){//两个两个比较,,选出最小的,然后拿最小的继续和后面做两两对比
        for(int i =0;i<array.length-1;i++){
            int index = i;
            for(int j = index+1;j<array.length;j++){
                if(array[j] <array[index]){
                    index = j;
                }
            }
            if(index != i){//如果当前就是最小的,就不需要交换
                int temp = array[index];
                array[index] = array[i];
                array[i] = temp;
            }
        }
    }

快速排序

1,从数列中挑出一个元素,称为基准。

2,所有比基准值小的元素放在基准值的前面,所有比基准值大的元素放在基准值的后面(相同的数可以到任意一边)。这样操作之后,基准值就处于数列的中间位置。

3,递归调用,把小于基准值的子数列和大于基准值元素的数列排序。一直到子数列的大小是0或者一的时候就排序好了。

   /**
     * 快速排序  31 21 59 68 12 40  (先取一个数据出来,第一轮排序之后左边都小于这个数,右边都大于这个数,然后一直循环)
     */
      public static void quickSort(int [] array,int begin,int end){
          if(end-begin<=0) return;

          int low = begin;//0
          int high = end;//5
          int x = array[begin];
          //由于会分别从两头取数据
          boolean direction = true;
          L1:
          while(low<high){
              if(direction){//从右往左找
                  for(int i = high;i>low;i--){
                      if(array[i]<=x){
                          array[low++] = array[i];
                          high = i;
                          direction = !direction;
                          continue L1;
                      }
                  }
                  high = low;//如果一直上面的if从未进入,让两个指针重合
              }else{//从左往右找
                  for(int i=low;i<high;i++){
                      if(array[i]>=x){
                          array[high--]=array[i];
                          low = i;
                          direction = !direction;
                          continue L1;
                      }
                  }
                  low = high;
              }
          }
          array[low] =x;//第一轮确定X位置,左边的都小于X,右边的都大于X
          quickSort(array,begin,low-1);
          quickSort(array,low+1,end);
      }

归并排序

二叉树的后序遍历思想

1,将序列每次折半拆分

2,比较左边和右边值的大小,然后排好序合并。按照二叉树的后序遍历的方式一层层的往上合并

3,递归调用

    /**
     * 归并排序 思想:二叉树的后序遍历
     * @param array 
     * @param left  0
     * @param right 数组长度-1
     */

      public static void mergeSort(int[] array,int left,int right){
          if(left == right){
              return;
          }else{
              int mid = (left+right)/2;
              //左半边往下拆分
              mergeSort(array,left,mid);
              //右半天边往下拆分
              mergeSort(array,mid+1,right);
              //排序之后合并
              merge(array,left,mid+1,right);
          }
      }
      
          /**
     * 将一个左右两边分别排好序的数组合并成一个完整的排好序的数组
     */
    //1,2,5,9  ========  3,4 ,10 ,11
     public static void merge(int []array,int left,int mid ,int right){       
         //1,将一个数组分成左右两个数组
         int leftSize = mid-left;
         int rightSize = right - mid + 1;
         int [] leftArray = new int[leftSize];
         int [] rightArray = new int[rightSize];
         //将数组的数填充到左右两个数组中去
         for(int i = left;i<mid;i++){
             leftArray[i-left] = array[i];
         }
         for(int i = mid;i<=right;i++){
             rightArray[i-mid] =array[i];
         }
         //将两个数组排序后合并
         int i=0;
         int j=0;
         int k=left;
         while(i<leftSize && j<rightSize){
             if(leftArray[i]<rightArray[j]){
                 array[k] = leftArray[i];
                 k++;i++;
             }else{
                 array[k] = rightArray[j];
                 k++;j++;
             }
         }

         while(i<leftSize){
             array[k] = leftArray[i];
             k++;i++;
         }

         while(j<rightSize){
             array[k] = rightArray[j];
             k++;j++;
         }
     }

插入排序

1,从第一个元素开始,该元素可以认为已经被排序。

2,取出下一个元素,在已经排序的元素序列中从后向前扫描。

3,如果已排序的元素大于新元素,将该元素移到下一个位置,新元素插入到该元素的位置。

4,重复步骤3,一直找到新元素应该插入到已排序的序列中的位置。保证新插入元素之后该序列还是一个排好序的序列。

5,重复步骤2-5

代码实现

    //直接插入排序
    public void insertSort(int [] array){
        for (int i = 1;i<array.length;i++){
            int j = i;
            int target = array[j];
            while(j>0 && target<array[j-1]){
                array[j] = array[j-1];
                j--;
            }
            array[j] = target;
        }
    }

希尔排序

一种改进的插入排序

将待排序数组按照步长gap进行分组,然后将每组的元素利用直接插入排序的方法进行排序;再将gap折半减小,循环上述操作;当gap=1时,利用直接插入,完成整个排序。

    @Test
    public void test(){
        int[] array=new int[]{2,3,4,5,6,7,1,8,9};

        shellSort(array,4);
         shellSort(array,2);
        shellSort(array,1);
        for (int i = 0; i < array.length; i++) {
            System.out.print(array[i]+" ");
        }
    }

    private void shellSort(int[] array, int step) {
        for(int k =0;k<step;k++){
            //直接插入排序
            for(int i = k+step;i<array.length;i=i+step){
                int j = i;
                int target = array[j];
                while(j>step - 1 && target<array[j-step]){
                    array[j] = array[j - step];
                    j = j - step;
                }
                array[j] = target;
            }
        }
    }

堆排序

完全二叉树中任何一个非叶子节点的值均不大于(或不小于)其左,右孩子节点的值。由此可知大顶堆的堆顶的值是所有堆中值最大的,小顶堆则是最小的。所以堆排序的过程就是将待排序的序列构造成一个堆,选出堆顶移走,再把剩余的元素调整成堆,找出最大的再移走,重复直至有序。

    void heapSort(int array[]){
        //循环一次,获取一次堆顶最大值,循环完毕数据就排好序了
        for(int i = array.length-1;i>0;i--){
            //建堆
            max_heapify(array,i);

            //将堆顶最大值存入到数组的最大索引处
            int temp = array[0];
            array[0] = array[i];
            array[i] = temp;
        }
    }

    /**
     * 创建一个大顶堆
     * @param array
     * @param n  数组的长度-1
     */
    void max_heapify(int [] array,int n){
        int child;
        for(int i = (n-1)/2;i>= 0;i--){//非叶子节点
            //该非叶子节点的左子节点位置
            child = 2*i+1;
            //假设该节点的右子节点存在,则比较左右子节点的值的大小,得到其中的大的值
            if (child != n && array[child] < array[child + 1]) {
                child++;
            }
            //交换父节点与左右子节点中的最大值
            if (array[i] < array[child]) {
                int temp = array[i];
                array[i] = array[child];
                array[child] = temp;
            }
        }
    }

基数排序

将所有待比较数值统一为同样的数位长度,数位较短的数前面补零,然后从最低位开始,依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序数列。

public static void sort(int[] arr) {
    if (arr.length <= 1) return;

    //取得数组中的最大数,并取得位数
    int max = 0;
    for (int i = 0; i < arr.length; i++) {
        if (max < arr[i]) {
            max = arr[i];
        }
    }
    int maxDigit = 1;
    while (max / 10 > 0) {
        maxDigit++;
        max = max / 10;
    }
    //申请一个桶空间
    int[][] buckets = new int[10][arr.length];
    int base = 10;

    //从低位到高位,对每一位遍历,将所有元素分配到桶中
    for (int i = 0; i < maxDigit; i++) {
        int[] bktLen = new int[10];        //存储各个桶中存储元素的数量

        //分配:将所有元素分配到桶中
        for (int j = 0; j < arr.length; j++) {
            int whichBucket = (arr[j] % base) / (base / 10);
            buckets[whichBucket][bktLen[whichBucket]] = arr[j];
            bktLen[whichBucket]++;
        }

        //收集:将不同桶里数据挨个捞出来,为下一轮高位排序做准备,由于靠近桶底的元素排名靠前,因此从桶底先捞
        int k = 0;
        for (int b = 0; b < buckets.length; b++) {
            for (int p = 0; p < bktLen[b]; p++) {
                arr[k++] = buckets[b][p];
            }
        }
        System.out.println("Sorting: " + Arrays.toString(arr));
        base *= 10;
    }
}

各种排序性能对比如下:

sort-comparison.png

相关文章

  • 排序

    八大排序算法 一、归并排序 递归及非递归的JAVA实现 二、快速排序 快排算法JAVA实现 三、堆排序 堆排序堆排...

  • 排序算法

    常见排序算法比较 参考资料:各种排序算法比较 参考资料:快速排序算法 必须知道的八大种排序算法【java实现】(一...

  • 数据结构&算法(一)

    一、Java实现快速排序算法 二、Java实现折半插入排序算法 三、Java实现冒泡排序算法

  • Java 八大排序实现

    参考链接 本文只给出算法的Java实现版本,具体原理参考:八大排序算法。 公用代码 下面的swap()函数,是排序...

  • java 实现排序算法之「插入排序」

    java 实现排序算法系列 这是 Java 实现排序算法的第三篇文章——插入排序算法。插入排序可以说成是「一类」简...

  • 八大排序

    初学java,整理了八大排序。 算法复杂度

  • 一文搞定十大经典排序算法(Java实现)

    本文总结十大经典排序算法及变形,并提供Java实现。参考文章:十大经典排序算法总结(Java语言实现)快速排序算法...

  • 【Java EE】从零开始写项目【总结】

    从零开发项目概述 最近这一直在复习数据结构和算法,也就是前面发出去的排序算法八大基础排序总结,Java实现单向链表...

  • 快速排序

    手写java版快速排序算法实现

  • 排序算法最强总结及其代码实现(Python/Java)

    前言 本文总结了常用的全部排序算法,内容包括: 排序算法的定义和思路 排序算法的代码实现:Python和Java,...

网友评论

      本文标题:java实现八大排序算法

      本文链接:https://www.haomeiwen.com/subject/oypsohtx.html