常见排序算法及java实现-蒲公英云

在这里插入图片描述

排序算法时间复杂度和空间复杂度

在这里插入图片描述

1. 冒泡排序

基本思想：两个数比较大小，较大的数下沉，较小的数冒起来。

过程：

比较相邻的两个数据，如果第一个数比第二个数小，就交换位置。一直比较到最后两个数据。最终最小数被交换到n的位置，这样第一个最小数的位置就排好了。
继续重复上述过程，依次将第2.3…n-1个最小数排好位置。
java实现：

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;
            }
        }
    }
}

2.快速排序算法

基本思想：分治法，①一边大一边小，取第一个数字作为标准，比它大的放右边，小的放左边；②分别迭代标准值的左边数组和右边数组

//快速排序，分治，一边大一边小，取第一个数字作为标准，比它大的放右边，小的放左边
    //分别迭代标准值的左边和右边
    public static void quickSort(int[] arr, int start, int end){ 
        if(start<end){ 
            //把数组中第0个数字作为标准数
            int stand = arr[start];
            //记录需要排序的下标
            int low = start;
            int high = end;
            //循环找出比标准数大的数和比标准数小的数
            while(low<high){ 
                //右边数字比标准数大
                while(low<high && arr[high]>= stand){ 
                    high--;
                }
                //右边数字替换左边数字
                arr[low]=arr[high];
                //左边数字比标准数小
                while (low<high && arr[low]<=stand){ 
                    low++;
                }
                //左边数字替换右边数字
                arr[high]=arr[low];
            }
            //把标准数赋给低位所在位置的元素
            arr[low] = stand;
            //处理所有的小的数字
            quickSort(arr,start,low);
            //处理所有的大的数字
            quickSort(arr,low+1,end);
        }
    }

3.插入排序算法

基本思想：从1位开始逐次与前面的值比较，如果该值比前面的值小，则把大值后移，并把1位值放到不大于的位置，遍历完后，从2位开始逐次与前面比。
过程：在区间 [1,length-1] ，从1位开始作为指针，for循环操作；指针位 j =i-1 （j在0~j之间）与 i 位进行比较，如果 i 比 j 位的值小，则 j 位值赋值给 j+1 位，若不小，则 j+1位值为 i位值。

//插入排序
    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 && arr[j]>temp;j--){ 
                    //把前一个数字赋给后一个数字
                    arr[j+1] = arr[j];
                }
                //把临时变量赋给不满足条件的后一个元素
                arr[j+1] = temp;
            }
        }
    }

4.希尔排序算法

基本思想：（类比插入排序算法，解决了插入排序中小数在末尾导致最终移动次数过多的情况，提升效率。）每次比较步长间隔的数组。

过程：设定步长为d=length/2，循环一次后，步长d = d/2，直到d/2为0。在每次循环步长的数组中，采用插入排序算法。

//希尔排序算法
    public static void shellSort(int[] arr){ 
        //遍历所有步长
        for (int d = arr.length/2; d > 0; d/=2) { 
            //遍历元素
            for (int i = d; i < arr.length; i+=d) { 
                //如果当前元素小于减步长后的那个元素，循环交换位置
                if(arr[i]<arr[i-d]){ 
                    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;
                        }
                    }
                }
            }
        }
    }

5.选择排序算法

基本思想：遍历数组，每次都找数组中最小的元素，进行交换。
过程：遍历所有数；如果最小数下标和当前遍历数的下标不一致，说明下标为minIndex的数比当前遍历的数小，交换位置；再判断，次小数下标和当前遍历数的下标不一致，再交换位置；直到遍历完数组。
在这里插入图片描述

//选择排序
    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[j]<arr[minIndex]){ 
                    minIndex = j;
                }
            }
            //如果最小数下标和当前遍历数的下标不一致，说明下标为minIndex的数比当前遍历的数小，交换位置
            if(minIndex!=i){ 
                int temp = arr[minIndex];
                arr[minIndex] = arr[i];
                arr[i] = temp;
            }
        }
    }

6.归并排序算法

基本思想：两个有序数组，逐位比较，小的放到新数组里。

过程：Merge方法处理两个有序数组，用一个临时数组temp存放排序后的数组；MergeSort方法负责把无序数组切分成两个数组，之后归并排序。

//归并排序
    public static void MergeSort(int[] arr,int low, int high){ 
        if(low<high){ 
            int middle = (high+low)/2;
            //处理左边
            MergeSort(arr,low,middle);
            //处理右边
            MergeSort(arr,middle+1,high);
            //归并
            Merge(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(i<=middle){ 
            temp[index]=arr[i];
            i++;
            index++;
        }
        while(j<=high){ 
            temp[index]=arr[j];
            j++;
            index++;
        }
        //临时数组中的数据存入原数组
        for (int k = 0; k < temp.length; k++) { 
            arr[low+k] = temp[k];
        }
    }

7.基数排序

适用于大数小数都有，位数相差明显，eg:{2,53,1,684,222,64,33}
基本思想：第一轮：首先把数字按个位放到相对数字的桶里（共10个桶，0~9），然后从前往后的顺序从桶里取出元素，每个桶里的元素按照先放的先取的顺序；第二轮：把数字按十位放到相对数字的桶里，再同样的方式取出；第三轮：按百位取。。。轮数看数组中最大的数字有几位则比较几轮。
在这里插入图片描述

//基数排序
    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++) { 
                //记录数量的数组counts中,当前余数记录的数量不为0
                if(counts[k]!=0){ 
                    //循环取出元素
                    for (int l = 0; l < counts[k]; l++) { 
                        arr[index] = temp[k][l];
                        index++;
                    }
                    //把数量置为0
                    counts[k]=0;
                }
            }
        }
    }