How to implement common sorting algorithms in Java-javaTutorial-php.cn

How to implement common sorting algorithms in Java

王林

Release： 2023-04-28 20:34:12

forward

1069 people have browsed it

Summary:

How to implement common sorting algorithms in Java

1. Bubble sort

Determine the best value in each round of loop;

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;
        }
    }
}

Copy after login

2. Selection sort

Select the best value each time and swap it to the edge;

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;
        }
    }
}

Copy after login

3. Insertion sort

Find its own position for each number in the loop and insert it;

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;
    }
}

Copy after login

4. Quick sort

Select a basic value that is smaller than it Put it on one side, and put the larger one on the other side;

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);
}

Copy after login

5. Merge sort

Divide and conquer algorithm;

//归
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);
}

Copy after login

6. Er sort

Introducing step size to reduce the number of number exchanges and improve efficiency;

6.1 Hill-bubble sort (slow)

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;
                }
            }
        }
    }
}

Copy after login

6.2 Hill -Insertion sort (fast)

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;
        }
    }
}

Copy after login

7. Heap sort

Big top heap implements ascending order, moving the maximum value to the last position of the heap each time;

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;
}

Copy after login

8. Counting sorting

Count the occurrences of each number in order;

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++;
        }
    }
}

Copy after login

9. Bucket sorting

Similar to counting sorting, the difference is that the statistics are the numbers in a certain interval (bucket);

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++;
        }
    }
}

Copy after login

10. Cardinal sorting

By ones, tens, hundreds Bits are sorted in order;

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;
    }
}

Copy after login

11. Using collections or API

11.1 Priority queue

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();
    }
}

Copy after login

11.2 Java API

public void arraysApiSort(int[] nums){
    Arrays.sort(nums);
}

Copy after login

The above is the detailed content of How to implement common sorting algorithms in Java. For more information, please follow other related articles on the PHP Chinese website!