排序算法··

快排

堆排

归并

//归并
    public static void mergeSort(int[]arr,int left,int right,int[] temp){
        if(left<right){
            int mid = (left+right)/2;
            mergeSort(arr,left,mid,temp);
            mergeSort(arr,mid+1,right,temp);
            merge(arr,left,mid,right,temp);
        }

    }
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){
        int i = left,j = mid+1;
        int index = 0;
        while(i<=mid && j<=right){
            if(arr[i]<arr[j]) temp[index++] = arr[i++];
            else temp[index++] = arr[j++];
        }
        while(i<=mid) temp[index++] = arr[i++];
        while(j<=right) temp[index++] = arr[j++];

        index = 0;
        while(left<=right){
            arr[left++] = temp[index++];
        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

基数

//基数排序
    public static void radixSort(int[] arr){
        int max = arr[0];
        for(int x:arr){
            max = x>max? x:max;
        }
        String ss = ""+max;
        int max_len = ss.length();

        int bucket[][] = new int[10][arr.length];
        int bucketCounts[] = new int[10];

        for(int i = 0,n = 1;i<max_len;i++,n*=10){
            for(int j = 0;j<arr.length;j++){
                int pos = arr[j]/n %10;
                bucket[pos][bucketCounts[pos]] = arr[j];
                bucketCounts[pos]++;
            }

            int index = 0;
            for(int k = 0;k<bucketCounts.length;k++){
                if(bucketCounts[k]!=0){
                    for(int t =0;t<bucketCounts[k];t++){
                        arr[index] = bucket[k][t];
                        index++;
                    }
                }
                bucketCounts[k] = 0;
            }

        }
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32