十大排序算法汇总-Java版（由小到大排序）

矫情吗；* 2022-05-10 11:20 190阅读 0赞

### 十大排序算法汇总-Java版（由小到大排序） ###

*  1.冒泡排序 — O(N^2)
 *  2.选择排序 — O(N^2)
 *  3.插入排序 — O(N^2)
 *  4.归并排序 — O(NlogN)
 *  5.快速排序 — O(NlogN)
 *  6.堆排序 — O(NlogN)
 *  7.希尔排序 — O(NlogN)
 *  8.计数排序 — O(N+K)
 *  9.桶排序 — O(N+K)
 *  10.基数排序 — O(N×K)

# 1.冒泡排序 — O(N^2) #

public void BubbleSort(int[] arr){
        for(int i=0;i<arr.length;i++)
            for(int j=0;j<arr.length-i-1;j++)
                if(arr[j]>arr[j+1]){
                    int temp = arr[j];
                    arr[j] = arr[j+1];
                    arr[j+1] = temp;
                }
    }

# 2.选择排序 — O(N^2) #

public void SelectSort(int[] arr){
        for(int i=0;i<arr.length;i++){
            int temp = arr[i];
            int flag = i;
            for(int j=i+1;j<arr.length;j++){
                if(arr[j]<temp){
                    temp = arr[j];
                    flag = j;
                }
            }
            if(flag!=i){
                arr[flag] = arr[i];
                arr[i] = temp;
            }
        }
    }

# 3.插入排序 — O(N^2) #

public void InsertSort(int[] arr){
        for(int i=1;i<arr.length;i++){
            int temp = arr[i], j = i;
            if(arr[j-1]>temp){
                while(j>0 && arr[j-1]>temp){
                    arr[j] = arr[j-1];
                    j--;
                }
            }
            arr[j] = temp;
        }
    }

# 4.归并排序 — O(NlogN) #

public static void main(String[] args) {
        int[] arr = {5,4,9,8,7,6,0,1,3,2};
        MergeSort(arr,0, arr.length-1);
        for(int i:arr)
            System.out.print(i + " ");
    }
    
    public static void MergeSort(int[] arr, int start, int end){
        if(start<end){
            int mid = (start+end)/2;
            MergeSort(arr, start, mid); // 左边归并排序
            MergeSort(arr, mid+1, end); // 右边归并排序
            Merge(arr, start, mid, end); // 两个有序子数组合合并操作
        }
    }
    
    public static void Merge(int[] arr, int start, int mid, int end){
        int len = end-start+1;
        int[] temp = new int[len];
    
        int t = 0;
        int i = start, j = mid+1;
        while(i<=mid && j<=end){
            if(arr[i]<arr[j])
                temp[t++] = arr[i++];
            else
                temp[t++] = arr[j++];
        }
        // 左序列有剩余
        while(i<=mid)
            temp[t++] = arr[i++];
        // 右序列有剩余
        while(j<=end)
            temp[t++] = arr[j++];
        t = 0;
        while(start<=end){
            arr[start++] = temp[t++];
        }
    }

# 5.快速排序 — O(NlogN) #

public void quickSort(int[] arr){
        sort(arr, 0, arr.length-1);
    }
    
    public void sort(int[] arr, int start, int end){
        int i = start, j = end;
        if(start>=end)
            return;
        int base = arr[start]; // 以最左边的数值为基准值
        while(start<end){
            while(start<end && arr[end]>=base)
                end--;
            if(start<end)
                arr[start++] = arr[end];
            while(start<end && arr[start]<=base)
                start++;
            if(start<end)
                arr[end--] = arr[start];
        }
    
        arr[start] = base;
        sort(arr, i, start-1);
        sort(arr, start+1, j);
    }

# 6.堆排序 — O(NlogN) #

public void main(String[] args) {
        int[] arr = {5,4,9,8,7,6,0,1,3,2};
        int len = arr.length;
        MinHeapSort(arr, len);
    }
    
    public void adjustMinHeap(int[] a, int pos, int len){
        int child, temp;
        for(temp = a[pos]; (2*pos+1)<=len; pos = child){
            child = 2*pos + 1;
            if(child<len && a[child]>a[child+1])  // 有右子节点
                child++;
            if(a[child]<temp)
                a[pos] = a[child];
            else
                break;
        }
        a[pos] = temp;
    }
    
    public void MinHeapSort(int[] a, int len){
        int i;
        for(i=(len-1)/2;i>=0;i--)   // 调整至小顶堆，从最后一个有孩子的结点开始往上调整
            adjustMinHeap(a, i, len-1);
        for(i=len-1;i>=0;i--){
            System.out.println(a[0]);
            swap(a, 0, i);
            adjustMinHeap(a, 0, i-1); // 调整小顶堆
        }
    }

# 7.希尔排序 — O(NlogN) #

public void shellSort(int[] arr){
        for(int h = arr.length/2;h>0;h=h/2){
            for(int i=h;i<arr.length;i++){
                int temp = arr[i], j = 0;
                for(j=i-h;j>=0;j=j-h){
                    if (temp<arr[j])
                        arr[j+h] = arr[j];
                    else
                        break;
                }
                arr[j+h] = temp;
            }
        }
    }

# 8.计数排序 — O(N+K) #

public void countingSort(int[] arr){
        int min = arr[0], max = arr[0];
        for(int i=1;i<arr.length;i++){
            if(arr[i]>max)
                max = arr[i];
            if(arr[i]<min)
                min = arr[i];
        }
    
        int[] bucket = new int[max-min+1];
        for(int i=0;i<arr.length;i++)
            bucket[arr[i]-min]++;
    
        int index = 0, i = 0;
        while(index<arr.length){
            if(bucket[i]!=0){
                arr[index] = i + min;
                bucket[i]--;
                index++;
            }
            else
                i++;
        }
    }

# 9.桶排序 — O(N+K) #

public ArrayList<Integer> result = new ArrayList<>();
    // BucketSize作为每个桶所能放置多少个不同数值(同种数值容量不限)
    public void BucketSort(int[] arr, int bucketSize){
        int max = arr[0], min = arr[0];
    
        for(int i=1;i<arr.length;i++){
            if(arr[i]>max)
                max = arr[i];
            if(arr[i]<min)
                min = arr[i];
        }
        int bucketCount = (max-min+1)/bucketSize; // 桶的数量
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>();
        for(int i=0;i<bucketCount;i++)
            bucketArr.add(new ArrayList<Integer>());
        for(int i=0;i<arr.length;i++)
            bucketArr.get((arr[i]-min)/bucketSize).add(arr[i]);
    
        for(int i=0;i<bucketCount;i++){
            if(bucketSize==1){ // 一个桶内有重复数字时
                for (int j=0;j<bucketArr.get(i).size();j++){
                    result.add(bucketArr.get(i).get(j));
                }
            }else{
                if(bucketCount==1)
                    bucketSize--;
                // arraylist 转 int[]
                int[] intArr = bucketArr.get(i).stream().mapToInt(Integer::intValue).toArray();
                BucketSort(intArr, 1);
            }
        }
    }

# 10.基数排序 — O(N×K) #

public void radixSort(int[] arr){
        int max = arr[0];
        for(int i=1;i<arr.length;i++)
            if(arr[i]>max)
                max = arr[i];
    
        int maxDigit = 0; // 最大位数
        while(max!=0){
            max /= 10;
            maxDigit++;
        }
    
        int mod = 10, div = 1;
        ArrayList<ArrayList<Integer>> bucketList = new ArrayList<>();
        for(int i=0;i<10;i++)
            bucketList.add(new ArrayList<Integer>());
        for(int i=0;i<maxDigit;i++, mod*=10,div*=10){
            for(int j=0;j<arr.length;j++){
                int num = (arr[j] % mod)/div;
                bucketList.get(num).add(arr[j]);
            }
            int index = 0;
            for(int j=0;j<bucketList.size();j++){
                for(int k=0;k<bucketList.get(j).size();k++){
                    arr[index++] = bucketList.get(j).get(k);
                }
                bucketList.get(j).clear();
            }
        }
    }