八大排序（冒泡，选择，插入，希尔，快排，堆，归并，基数）总结一波

叁歲伎倆 2023-06-08 06:42 3阅读 0赞

## 时间复杂度和稳定性 ##

选择排序、快速排序、希尔排序、堆排序不是稳定的排序算法。  
冒泡排序、插入排序、归并排序和基数排序是稳定的排序算法。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0_size_16_color_FFFFFF_t_70]  
以下排序都是升序排列。

## 冒泡 ##

两个两个比较，一轮下来，最大值就到数组末尾了。

import java.util.Arrays;
    
    public class Sort1{ 
        public static void main(String[] args){ 
            int [] arr={ 9,6,3,8,5,2,1,4,7,-1,-7};
            for(int i=0;i<arr.length-1;i++){ 
                boolean flag=true;
                for(int j=0;j<arr.length-1-i;j++){ 
                    if(arr[j]>arr[j+1]){ 
                        int t=arr[j];
                        arr[j]=arr[j+1];
                        arr[j+1]=t;
                        flag=false;//判断有无交换位置
                    }
                      
                }
                //若没有交换位置，则证明已经排好了，不用再继续了
                if (flag){ 
                    break;
                }
            }
            System.out.println(Arrays.toString(arr));
            
        }
    }

## 选择 ##

第一个与他后面的每一个都比较，第一轮，下来最小的放在第一位。

import java.util.Arrays;
    
    public class Sort2{ 
        public static void main(String[] args){ 
            int [] arr={ 9,6,3,8,5,2,1,4,7,-1,-7};
    		for(int i=0;i<arr.length-1;i++){ 
                for(int j=1+i;j<arr.length;j++){ 
                    if(arr[i]>arr[j]){ 
                    	int t=arr[i];
                    	arr[i]=arr[j];
                    	arr[j]=t;
                    }
                }
    		}
    
    
     		System.out.println(Arrays.toString(arr));
            
        }
    }

## 插入排序 ##

思路，总是保证当前元素为有序的。  
开始为一个元素（有序），再加入第二个元素保证有序，再加入第三个元素，保证有序，依次类推。

import java.util.Arrays;
    
    public class Sort3{ 
        public static void main(String[] args){ 
            int [] arr={ 9,6,3,8,5,2,1,4,7,-1,-7};
            for(int i=1;i<arr.length;i++){ 
                int j=i;
                while(j>0){ 
                    if(arr[j-1]>arr[j]){ 
                        int t=arr[j];
                        arr[j]=arr[j-1];
                        arr[j-1]=t;
                        j--;
                    }else{ 
                        break;
                    }
                    
                }
                
            }
            
            
    		System.out.println(Arrays.toString(arr));
            
        }
    }

## 希尔排序 ##

**交换法**  
按步长，开始为数组长度的一半，然后再为数组的1/4，再为数组的1/8，直到步长为1为止。

import java.util.Arrays;
    
    public class Sort4 { 
        public static void main(String[] args) { 
            int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
    
            for (int gap = arr.length / 2; gap > 0; gap /= 2) { 
                
                for (int i = gap; i < arr.length; i++) { 
                    for (int j = i - gap; j >= 0; j -= gap) { 
                        if (arr[j] > arr[j + gap]) { 
                            int t = arr[j];
                            arr[j] = arr[j + gap];
                            arr[j + gap] = t;
                        }
                    }
                }
            }
            System.out.println(Arrays.toString(arr));
        }
    }

**移位法**  
效率比交换法高

import java.util.Arrays;
    
    public class Sort5 { 
        public static void main(String[] args) { 
            int[] arr = { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
    
            for (int gap = arr.length / 2; gap > 0; gap /= 2) { 
                for (int i = gap; i < arr.length; i++) { 
                    int j = i;
                    int temp = arr[j];//保存要插入的元素
                    //如果前一个元素比要插入的元素大，则进入循环
                    if (arr[j - gap] > arr[j]) { 
                        while (j - gap >= 0 && arr[j - gap] > temp) { 
                            //大则移位到后一个
                            arr[j] = arr[j - gap];
                            j -= gap;
                        }
                        //跳出循环意味找到位置了
                        arr[j] = temp;
                    }
    
                }
            }
            System.out.println(Arrays.toString(arr));
        }
    }

## 快排 ##

比如序列为5 3 3 4 3 8 9 10 11，现在中枢元素5和3（第5个元素，下标从1开始计）交换就会把元素3的稳定性打乱，所以快速排序是一个不稳定的排序算法，不稳定发生在中枢元素和a\[j\] 交换的时刻。

import java.util.Arrays;
    
    public class Main { 
        public static void main(String[] args) { 
            int[] arr = { -1, 5, 1,1,3, 2, 4, 3};
            sort(arr, 0, arr.length - 1);
            System.out.println(Arrays.toString(arr));
        }
    
        public static void sort(int[] arr, int i, int j) { 
            if (i < j) { 
                int index = getIndex(arr, i, j);
                sort(arr, i, index - 1);
                sort(arr, index + 1, j);
            }
        }
    
        public static int getIndex(int[] arr, int i, int j) { 
    
            int x = arr[i];
            while (i < j) { 
                while (i < j && arr[j] > x) { 
                    j--;
                }
                if (i < j) { 
                    arr[i] = arr[j];
                    i++;
                }
                while (i < j && arr[i] < x) { 
                    i++;
                }
                if (i < j) { 
                    arr[j] = arr[i];
                    j--;
                }
            }
            arr[i] = x;
            return i;
        }
    }

## 堆排序（最大堆） ##

最小堆，最小的元素在最上方，最后排出来是从大到小的顺序，因为将最小的元素取出放在了数组末尾，所以最后出来最小堆是降序排列，最大堆是升序排列。

heapify是每次将堆顶元素取出，放在数组末尾后调整堆的结构的，buildHeap是最开始的时候将数组变为最小堆的结构，

import java.util.Arrays;
    
    public class HeapSort3 { 
        public static void main(String[] args) { 
            int[] arr = { 1, 2, 3, 4, 5, 6, 7};
            heapSort(arr);
            System.out.println(Arrays.toString(arr));
    
        }
    
        public static void heapSort(int[] arr) { 
            buildHeap(arr, arr.length);
            int n = arr.length - 1;
            for (int i = n; i >= 0; i--){ 
                swap(arr,i,0);//交换最大值和末尾元素
                heapify(arr,i,0);//对堆顶元素进行最大堆排列。
            }
    
        }
    
        public static void buildHeap(int[] arr, int n) { 
            int lastNode = n - 1;
            int parentNode = (lastNode - 1) / 2;
            //从下自上，从右自左，对父结点进行heapify
            for (int i = parentNode; i >= 0; i--) { 
                heapify(arr, n, i);
            }
        }
    
        /** * @param arr * @param n 结点的个数，也就是数组长度 * @param i 结点索引 */
        public static void heapify(int[] arr, int n, int i) { 
            if (i >= n) { 
                return;
            }
            //比较当前结点和左右子节点的大小
            int c1 = i * 2 + 1;
            int c2 = i * 2 + 2;
            int max = i;
            if (c1 < n && arr[max] < arr[c1]) { 
                max = c1;
            }
            if (c2 < n && arr[max] < arr[c2]) { 
                max = c2;
            }
            if (max != i) { 
                //交换最大值max和i位置的数字
                swap(arr, max, i);
                //交换后，对此时max位置的小数字 递归
                heapify(arr, n, max);
            }
    
        }
    
        private static void swap(int[] arr, int max, int i) { 
            int t = arr[max];
            arr[max] = arr[i];
            arr[i] = t;
        }
    }

## 归并排序 ##

先递归将所有元素分开，然后分到最后一个，再调用整理排序的方法，最后回溯（递归回去）

import java.util.Arrays;
    
    public class MergerSort { 
        public static void main(String[] args) { 
            int[] arr = { 8, 4, 5, 7, 1, 3, 6, 2};
            //归并排序需要一个额外的内存空间
            int[] temp = new int[arr.length];
            sort(arr, 0, arr.length - 1, temp);
    
            System.out.println(Arrays.toString(arr));
        }
    
        /** * 递归分开数组元素，一直分 * @param arr * @param left * @param right * @param temp */
        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);
    
            }
    
        }
    
        /** * 对分开的元素进行排序 * @param arr * @param left 左边索引 * @param mid 中间索引，左边的末尾元素索引 * @param right 右边末尾索引 * @param temp 零时数组 */
        public static void merge(int[] arr, int left, int mid, int right, int[] temp) { 
            int i = left;
            int j = mid + 1;
            int t = 0;
            while (i <= mid && j <= right) { 
            //比较左边的序列，和右边的序列 大小
                if (arr[i] <= arr[j]) { 
                    temp[t] = arr[i];
                    t++;
                    i++;
                } else { 
                    temp[t] = arr[j];
                    t++;
                    j++;
                }
    
            }
            //将左边或者右边的序列中剩余的元素放入零时数组
            while (i <= mid) { 
                temp[t] = arr[i];
                i++;
                t++;
            }
            while (j <= right) { 
                temp[t] = arr[j];
                j++;
                t++;
            }
            
            //将零时数组中的元素，放回到原来序列中
            t = 0;
            int nowLeft = left;
            while (nowLeft <= right) { 
                arr[nowLeft] = temp[t];
                t++;
                nowLeft++;
            }
    
    
        }
    }

## 基数 ##

import java.util.Arrays;
    
    public class RadixSortDemo { 
        public static void main(String[] args) { 
            int[] arr = { 12, 589, 456, 3, 45, 66, 32,-1,-11};
            sort(arr);
            System.out.println(Arrays.toString(arr));
    
        }
    
        public static void sort(int[] arr) { 
            //二维数组表示10个桶，从0-->9
            int[][] buckets = new int[10][arr.length];
            //记录每个桶中实际元素个数
            int[] bucketNumCounts = new int[10];
            //找到最大数
            int max = arr[0];
            for (int i = 1; i < arr.length; i++) { 
                if (arr[i] > max) { 
                    max = arr[i];
                }
            }
            //计算最大数长度,也就是位数
            int m = (max + "").length();
    
            //m位数表示需要排序的次数，n用于辅助计算各个位数的数字
            for (int l = 0, n = 1; l < m; l++, n *= 10) { 
    
                for (int i = 0; i < arr.length; i++) { 
                    //拿到元素的当前位上的数
                    int q = (arr[i] / n) % 10;
                    //将数放入对应的桶中
                    buckets[q][bucketNumCounts[q]] = arr[i];
                    //记录每个桶中的数的数量
                    bucketNumCounts[q]++;
                }
                //按序取出桶中的数
                int index = 0;
                for (int i = 0; i < buckets.length; i++) { 
                    for (int j = 0; j < bucketNumCounts[i]; j++) { 
                        arr[index] = buckets[i][j];
                        index++;
                    }
                    //将数量归零，后面使用
                    bucketNumCounts[i]=0;
                }
    
    
            }
        }
    }

以上基数排序只能解决正整数，如果有负数的话，将所有的数加上最小的负数的绝对值，让所有数变为正数，然后基数排序，最后再减去刚加的负数的绝对值。

import java.util.Arrays;
    
    public class RadixSortDemo { 
        public static void main(String[] args) { 
            int[] arr = { 12, 589, 456, 3, 45, 66, 32,-1,-11};
            sort(arr);
            System.out.println(Arrays.toString(arr));
    
        }
    
        public static void sort(int[] arr) { 
            //二维数组表示10个桶，从0-->9
            int[][] buckets = new int[10][arr.length];
            //记录每个桶中实际元素个数
            int[] bucketNumCounts = new int[10];
    
            //遍历所有数将如果有负数，就先给各个数加上负数的最小值，使得所有数都变为正数
            int min=arr[0];
            for (int i = 1; i < arr.length; i++) { 
                if (arr[i]<min){ 
                    min=arr[i];
                }
            }
            //将所有数都变为正数
            if (min<0){ 
                for (int i = 0; i < arr.length; i++) { 
                    arr[i]-=min;
                }
            }
    
            //找到最大数
            int max = arr[0];
            for (int i = 1; i < arr.length; i++) { 
                if (arr[i] > max) { 
                    max = arr[i];
                }
            }
            //计算最大数长度,也就是位数
            int m = (max + "").length();
    
            //m位数表示需要排序的次数，n用于辅助计算各个位数的数字
            for (int l = 0, n = 1; l < m; l++, n *= 10) { 
    
                for (int i = 0; i < arr.length; i++) { 
                    //拿到元素的当前位上的数
                    int q = (arr[i] / n) % 10;
                    //将数放入对应的桶中
                    buckets[q][bucketNumCounts[q]] = arr[i];
                    //记录每个桶中的数的数量
                    bucketNumCounts[q]++;
                }
                //按序取出桶中的数
                int index = 0;
                for (int i = 0; i < buckets.length; i++) { 
                    for (int j = 0; j < bucketNumCounts[i]; j++) { 
                        arr[index] = buckets[i][j];
                        index++;
                    }
                    //将数量归零，后面使用
                    bucketNumCounts[i]=0;
                }
            }
    
            //还原负数
            if (min<0){ 
                for (int i = 0; i < arr.length; i++) { 
                    arr[i]+=min;
                }
            }
    
    
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQzMzcxMDA0_size_16_color_FFFFFF_t_70]: /images/20230531/30c6b1ef43794532a8d216ae2752efa3.png