JAVA数据结构与算法基础学习笔记(三)

排序算法
数据结构 算法
发布日期:   2020-05-25
文章字数:   1.8k
阅读时长:   8 分
阅读次数:  

排序算法

时间复杂度和空间复杂度概述

时间复杂度：

空间复杂度：

八种常用排序算法

交换排序

  1. 冒泡排序
package demo4;

import java.util.Arrays;

public class BubbleSort{
    public static void main(String[] args){
        int[] arr = new int[] {5,7,2,9,4,1,0,5,7};

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

    }

    public static void bubbleSort(int[] arr){
        //控制一共比较多少轮
        for(int i=0;i<arr.length-1;i++){
            //每轮比较多少次
            for(int j=0;j<arr.length-1-i;j++){
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
            }
        }
    }
}
  1. 快速排序
package demo4;
import  java.util.Arrays;
public class QuickSort{
    public static void main(String[] args){
        int[] arr = new int[] {3,18,9,8,5,4,7,6};
        quickSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void quickSort(int[] arr,int start,int end){
        if(start<end>){
            //把数组中的第0个数字作为标准数
            int stard = arr[start];
            //记录需要排序的下标
            int low = start;
            int high = end;
            //循环找比标准数大的数和比标准数小的数
            while(low<high){
                //右边的数字比标准数大
                while(low<high&&stard<=arr[high]){
                    high--;
                }
                //使用右边的数字替换左边的数
                arr[low] = arr[high];
                //如果左边的数字比标准数小
                while(low<high&&arr[low]<=stard){
                    low++;
                }
                arr[high] = arr[low];
            }
            //把标准数赋给低所在的位置的元素
            arr[low] = stard;
            //处理所有小的数字，调用递归
            quickSort(arr,start,low);
            //处理所有大的数字
            quickSort(arr,low+1,end);
        }
    }
}

插入排序

  1. 直接插入排序
package demo4;

import java.util.Arrays;

public class insertSort{
    public static void main(String[] args){
        int[] arr = new int[] {5,7,2,9,4,1,0,5,7};

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

    }

    public static void insertSort(int[] arr){
        //遍历所有的数字
        for(int i=1;i<arr.length;i++){
            //如果当当前数字比前一个数字小
            if(arr[i]<arr[i-1]){
                //把当前遍历数字存起来
                int temp = arr[i];
                int j;
                //遍历当前数字前面所有的数字
                for(j=i<-1;j>=0&&temp<arr[j];j--){
                    //把前一个数字赋给后一个数字
                    arr[j+1] = arr[j];
                }
                //把临时变量(外层for循环的当前元素)赋给不满足条件的后一个元素
                arr[j+1] = temp;
            }
        }
    }
}
  1. 希尔排序
package demo4;
import java.util.Arrays;
public class ShellSort{
    public static void main(String[] args){
        int[] arr = new int[] {3,5,2,7,8,1,2,0,4,7,4,3,8};
        shellSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void shellSort(int[] arr){
        //遍历所有的步长
        for(int d = arr.length/2;d>0;d/=2){
            遍历所有的元素
            for(int i = d;i<arr.length;i++){
                //遍历本组中所有的元素
                for(int j=i-d;j>=0;j-=d){
                    //如果当前元素大于加上步长后的那个元素
                    if(arr[j]>arr[j+d]){
                        int temp = arr[j];
                        arr[j] = arr[j+d];
                        arr[j+d] = temp;
                    }
                }
            }
        }
    }
}

选择排序

  1. 简单选择排序
package demo4;
import java.util.Arrays;
public class SelectSort{
    public static void main(){
        int[] arr = new int[] {3,5,2,9,4,7,6,1};
        selectSort(arr);
        System.out.println(Arrays.toString(arr));
    }

        //选择排序
        public static void selectSort(int[] arr){
            //遍历所有的数
            for(int i=0;i<arr.length;i++){
                int minIndex = i;
                //把当前遍历的数和后面所有的数依次进行比较，并记录下最小的数的下标
                for(int j=i+1;j<arr.length;j++){
                    //如果后面比较的数比记录的最小的数小
                    if(arr[minIndex]>arr[j]){
                        //记录下最小的那个数的下标
                        minIndex = j;
                    }
                }
                //如果最小的数和当前遍历数的下标不一致，说明下标为Index的数比当前遍历的数更小
                if(i!=minIndex){
                    int temp = arr[i];
                    arr[i] = arr[minIndex];
                    arr[minIndex] = temp;
                }
            }
        }
    }
  1. 堆排序
package dome4;
import java.util.Arrays;
public class HeapSort{
    public static void main(String[] args){
        int[] arr = new int[] {9,6,8,7,0,1,10,4,2};
        heapSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void heapSort(int[] arr){
        //开始位置是最后一个非叶子节点，即最后一个节点的父节点
        int start = (arr.length-1)/2;
        //调整为大顶堆
        for(int i=start;i>=0;i--){
            maxHeap(arr,arr.length,i);
        }
        //先把数组中的第0个和堆中的最后一个数交换位置，再把前面的处理为大顶堆
        for(int i=arr.length-1;i>0;i--){
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            maxHeap(arr,i,0);
        }
    }

    public static void maxHeap(int[] arr,int size,int index){
        //左子节点
        int leftNode = 2*index+1;
        //右子节点
        int rightNode  =2*index+2;
        int max = index;
        //和两个子节点分别对比，找出最大的节点
        if(leftNode<size&&arr[leftNode]>arr[max]){
            max = leftNode;
        }
        if(rightNode<size&&arr[rightNode]>arr[max]){
            max = rightNode;
        }
        //交换位置
        if(max!=index){
            int temp = arr[index];
            arr[index] = arr[max];
            arr[max] = temp;
            //交换位置以后，可能会破坏之前排好的堆，所以，之前排好的堆需要重新调整
            maxHeap(arr,size,max);
        }
    }
}

归并排序

package demo4;
import java.util.Arrays;
public class MergerSort(){
    public static void main(String[] args){
        int[] arr= new int[] {1,3,5,2,4,6,8,10};
        mergeSort(arr,0,arr.length-1);
        System.out.println(Arrays.toString(arr));
    }

    public static void mergeSort(int[] arr;int low;int high){
        int middle=(high+low)/2;
        if(low<high){
            //处理左边
        mergeSort(arr,low,middle);
        //处理右边
        mergeSort(arr,middle+1,high);
        //归并
        mergeSort(arr,low,middle,high);
        }
    }

    public static void merge(int[] arr,int low,int middle,int high){
        //用于存储归并后的临时数组
        int[] temp = new int[high-low+1];
        //记录第一个数组中需要遍历的下标
        int i = low;
        //记录第二个数组需要遍历的下标
        int j = middle+1;
        //用于记录在临时数组中存放的下标
        int index = 0;
        //遍历两个数组取出小的数字，放入临时数组中
        while(i<=middle&&j<=high){
            //第一个数组是数据更小
            if(arr[i]<=arr[j]){
                //把小的数据放入临时数组中
                temp[index] = arr[i];
                //让下标向后移一位
                i++;
            }else{
                temp[index] = arr[j];
                j++;
            }
            index++;
        }
        //处理多余的数据
        while(j<=high){
            temp[index] = arr[j];
            j++;
            index++;
        }
        while(i<=middle){
            temp[index] = arr[i];
            i++;
            index++;
        }
        //把临时数组中的数据重新存入原数组
        for(int k=0;k<temp.length;k++){
            arr[k+low] = temp[k];
        }
    }
}

基数排序

package demo4;
import java.util.Arrays;
public class RadixSort{
    public static void main(){
        int[] arr = new in[] {23,6,189,45,9,287,56,1,798,34,65,652,5};
        radixSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    public static void radixSort(int[] arr){
        int max=Integer.MIN_VALUE;
        for(int i = 0;i<arr.length;i++>){
            if(arr[i]>max){
                max=arr[i];
            }
        }
        //计算最大数字是几位数
        int maxLength = (max+"").length();
        //用于临时存储数据的数组
        int[][] temp = new int[10][arr.length];
        //用于记录在temp中年相应的数组中存放的数字的数量
        int[] counts = new int[10];
        //根据最大长度的数决定比较的次数
        for(int i = 0,n = 1;i<maxLength;i++,n *= 10){
            //把每一个数字分别计算余数
            for(int j=0;j<arr.length;j++){
                //计算余数
                int ys = arr[j]/n%10;
                //把当前遍历的数据放入指定的数组中
                temp[ys][counts[ys]] = arr[j];
                //记录数量
                counts[ys]++;
            }
            //记录取的元素需要放的位置
            int index = 0;
            //把数字取出来
            for(int k=0;k<counts.length;k++){
                //记录数量的数组中当前余数记录的数量不为0
                if(counts[k]!=0){
                    //循环取出元素
                    for(int l=0;l<counts[k];l++){
                        //取出元素
                        arr[index] = temp[k][l];
                        //记录下一个位置
                        index++;
                    }
                    //把数量置为0
                    counts[k]=0;
                }
            }
        }
    }
}

八种排序方法的对比

文章作者: 小蜗龟
文章链接: https://xiaowogui.top/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E7%AC%94%E8%AE%B0(%E4%B8%89)10721.html
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 小蜗龟 !
排序算法
赏
评论
 上一篇
JAVA数据结构与算法基础学习笔记(二) JAVA数据结构与算法基础学习笔记(二)
栈 栈的定义栈是一种操作受限制的线性表，将允许进行插入、删除的一端称为栈顶，另一端称为栈底。 栈的分类栈主要分为静态栈和动态栈，静态栈类似于数组，而动态栈类似于链表，但只能对链表的一端进行操作。这里主要说一下静态栈。 静态栈的表示 #de
2020-05-25 数据结构 算法
栈、队列、链表
下一篇 
JAVA数据结构与算法基础学习笔记(一) JAVA数据结构与算法基础学习笔记(一)
一、概述数据结构概述 数据结构的定义：数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。 数据存储结构： 顺序存储 链式存储 数据的逻辑结构： 集合结构：其中的元素属于一个集合，它们是并列关系
2020-05-25 数据结构 算法
数据结构
  目录