常见排序算法及java实现

小咪咪 2022-12-11 12:27 182阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70_pic_center]

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

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70_pic_center 1]

## 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的数比当前遍历的数小，交换位置；再判断，次小数下标和当前遍历数的下标不一致，再交换位置；直到遍历完数组。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70_pic_center 2]

//选择排序
        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），然后从前往后的顺序从桶里取出元素，每个桶里的元素按照先放的先取的顺序；第二轮：把数字按十位放到相对数字的桶里，再同样的方式取出；第三轮：按百位取。。。轮数看数组中最大的数字有几位则比较几轮。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70_pic_center 3]

//基数排序
        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;
                    }
                }
            }
        }

## 8.堆排序 ##

**基本思想**：  
完全二叉树，父节点内容大于子节点内容

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/c50c18d2d0574c6dafe4fc82bf806097.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/13d430845ab54ec48f0cb47c8a68ecf9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/da915dc055a84b23936c283050b627b6.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80MjAxNDYyMg_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/9d60c2879d7a42dc82c9cccbf44426d0.png