Java 常见排序算法代码分享

public void bubbleSort( int [] nums){

    int temp;

    boolean isSort = false ; //优化，发现排序好就退出

    for ( int i = 0 ; i < nums.length- 1 ; i++) {

        for ( int j = 0 ; j < nums.length- 1 -i; j++) {   //每次排序后能确定较大值

            if (nums[j] > nums[j+ 1 ]){

                isSort = true ;

                temp = nums[j];

                nums[j] = nums[j+ 1 ];

                nums[j+ 1 ] = temp;

            }

        }

        if (!isSort){

            return ;

        } else {

            isSort = false ;

        }

    }

}

public void selectSort( int [] nums){

    for ( int i = 0 ; i < nums.length- 1 ; i++) {

        int index = i;

        int minNum = nums[i];

        for ( int j = i+ 1 ; j < nums.length; j++) {

            if (nums[j] < minNum){

                minNum = nums[j];

                index = j;

            }

        }

        if (index != i){

            nums[index] = nums[i];

            nums[i] = minNum;

        }

    }

}

public void insertionSort( int [] nums){

    for ( int i = 1 ; i < nums.length; i++) {

        int j = i;

        int insertNum = nums[i];

        while (j- 1 >= 0 && nums[j- 1 ] > insertNum){

            nums[j] = nums[j- 1 ];

            j--;

        }

        nums[j] = insertNum;

    }

}

public void quickSortDfs( int [] nums, int left, int right){

    if (left > right){

        return ;

    }

    int l = left;

    int r = right;

    int baseNum = nums[left];

    while (l < r){

        //必须右边先走

        while (nums[r] >= baseNum && l < r){

            r--;

        }

        while (nums[l] <= baseNum && l < r){

            l++;

        }

        int temp = nums[l];

        nums[l] = nums[r];

        nums[r] = temp;

    }

    nums[left] = nums[l];

    nums[l] = baseNum;

    quickSortDfs(nums, left, r- 1 );

    quickSortDfs(nums, l+ 1 , right);

}

//归

public void mergeSortDfs( int [] nums, int l, int r){

    if (l >= r){

        return ;

    }

    int m = (l+r)/ 2 ;

    mergeSortDfs(nums, l, m);

    mergeSortDfs(nums, m+ 1 , r);

    merge(nums, l, m, r);

}

//并

private void merge( int [] nums, int left, int mid, int right){

    int [] temp = new int [right-left+ 1 ];

    int l = left;

    int m = mid+ 1 ;

    int i = 0 ;

    while (l <= mid && m <= right){

        if (nums[l] < nums[m]){

            temp[i++] = nums[l++];

        } else {

            temp[i++] = nums[m++];

        }

    }

    while (l <= mid){

        temp[i++] = nums[l++];

    }

    while (m <= right){

        temp[i++] = nums[m++];

    }

    System.arraycopy(temp, 0 , nums, left, temp.length);

}

public void shellBubbleSort( int [] nums){

    for ( int step = nums.length/ 2 ; step > 0 ; step /= 2 ) {

        for ( int i = step; i < nums.length; i++) {

            for ( int j = i-step; j >= 0 ; j -= step) {

                if (nums[j] > nums[j+step]){

                    int temp = nums[j];

                    nums[j] = nums[j+step];

                    nums[j+step] = temp;

                }

            }

        }

    }

}

public void shellInsertSort( int [] nums){

    for ( int step = nums.length/ 2 ; step > 0 ; step /= 2 ) {

        for ( int i = step; i < nums.length; i++) {

            int j = i;

            int insertNum = nums[i];

            while (j-step >= 0 && nums[j-step] > insertNum){

                nums[j] = nums[j-step];

                j-=step;

            }

            nums[j] = insertNum;

        }

    }

}

public void heapSort2( int [] nums) {

    for ( int i = nums.length/ 2 - 1 ; i >= 0 ; i--){

        sift(nums, i, nums.length);

    }

    for ( int i = nums.length- 1 ; i > 0 ; i--) {

        int temp = nums[ 0 ];

        nums[ 0 ] = nums[i];

        nums[i] = temp;

        sift(nums, 0 , i);

    }

}

private void sift( int [] nums, int parent, int len) {

    int value = nums[parent];

    for ( int child = 2 *parent + 1 ; child < len; child = child* 2 + 1 ) {

        if (child+ 1 < len && nums[child+ 1 ] > nums[child]){

            child++;

        }

        if (nums[child] > value){

            nums[parent] = nums[child];

            parent = child;

        } else {

            break ;

        }

    }

    nums[parent] = value;

}

public void countSort( int [] nums){

    int max = Integer.MIN_VALUE;

    int min = Integer.MAX_VALUE;

    for ( int num : nums){

        max = Math.max(max, num);

        min = Math.min(min, num);

    }

    int [] countMap = new int [max-min+ 1 ];

    for ( int num : nums){

        countMap[num-min]++;

    }

    int i = 0 ;

    int j = 0 ;

    while (i < nums.length && j < countMap.length){

        if (countMap[j] > 0 ){

            nums[i] = j+min;

            i++;

            countMap[j]--;

        } else {

            j++;

        }

    }

}

public void bucketSort( int [] nums){

    int max = Integer.MIN_VALUE;

    int min = Integer.MAX_VALUE;

    for ( int num : nums){

        max = Math.max(max, num);

        min = Math.min(min, num);

    }

    int bucketCount = (max-min)/nums.length+ 1 ;

    List<List<Integer>> bucketList = new ArrayList<>();

    for ( int i = 0 ; i < bucketCount; i++) {

        bucketList.add( new ArrayList<>());

    }

    for ( int num : nums){

        int index = (num-min)/nums.length;

        bucketList.get(index).add(num);

    }

    for (List<Integer> bucket : bucketList){

        Collections.sort(bucket);

    }

    int j = 0 ;

    for (List<Integer> bucket : bucketList){

        for ( int num : bucket){

            nums[j] = num;

            j++;

        }

    }

}

public   void radixSort( int [] nums){

    int min = Integer.MAX_VALUE;

    int max = Integer.MIN_VALUE;

    for ( int num : nums) {

        min = Math.min(min, num);

        max = Math.max(max, num);

    }

    for ( int i = 0 ; i < nums.length; i++) {

        nums[i] -= min;

    }

    max -= min;

    int maxLen = (max+ "" ).length();

    int [][] bucket = new int [nums.length][ 10 ];

    int [] bucketCount = new int [ 10 ];

    for ( int i = 0 , n = 1 ; i < maxLen; i++, n*= 10 ) {

        for ( int num : nums) {

            int digitVal = num / n % 10 ;

            bucket[bucketCount[digitVal]][digitVal] = num;

            bucketCount[digitVal]++;

        }

        int index = 0 ;

        for ( int j = 0 ; j < bucketCount.length; j++) {

            if (bucketCount[j] > 0 ){

                for ( int k = 0 ; k < bucketCount[j]; k++) {

                    nums[index] = bucket[k][j];

                    index++;

                }

            }

            bucketCount[j] = 0 ;

        }

    }

    for ( int i = 0 ; i < nums.length; i++) {

        nums[i] += min;

    }

}

public void priorityQueueSort( int [] nums){

    PriorityQueue<Integer> queue = new PriorityQueue<>();

    for ( int num : nums){

        queue.offer(num);

    }

    for ( int i = 0 ; i < nums.length; i++) {

        nums[i] = queue.poll();

    }

}

public void arraysApiSort( int [] nums){

    Arrays.sort(nums);

}