Examples of sorting methods in java-JavaBase-php.cn

Examples of sorting methods in java

王林

Release： 2019-11-12 15:36:28

Original

4116 people have browsed it

Examples of sorting methods in java

Bubble sort

Features: low efficiency, simple implementation

Thoughts (from small to large): each Move the largest element in the sequence to be sorted to the end, and the remainder is the new sequence to be sorted. Repeat the above steps until all elements are sorted. This is just a type of bubble sorting, of course it can also be sorted from back to front.

public void bubbleSort(int array[]) {
        int t = 0;        
        for (int i = 0; i < array.length - 1; i++)            
        for (int j = 0; j < array.length - 1 - i; j++)                
        if (array[j] > array[j + 1]) {
                    t = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = t;
                }
    }

Copy after login

Selection sort

Features: low efficiency, easy to implement

Idea: select the smallest one from the sequence to be sorted in each pass The elements are placed at the end of the sorted sequence, and the remaining bits are left to be sorted. Repeat the above steps until the sorting is completed.

public void selectSort(int array[]) {
        int t = 0;        
        for (int i = 0; i < array.length - 1; i++)            
        for (int j = i + 1; j < array.length; j++)                
        if (array[i] > array[j]) {
                    t = array[i];
                    array[i] = array[j];
                    array[j] = t;
                }
    }

Copy after login

Insertion sort

Features: low efficiency, easy to implement

Idea: Divide the array into two parts, and divide the last part of the elements Compare it with the previous elements one by one. If the current element array[i] is small, replace it. Find a reasonable position to insert array[i]

public void insertionSort(int array[]) {
        int i, j, t = 0;        
        for (i = 1; i < array.length; i++) {
            t = array[i];            
            for (j = i - 1; j >= 0 && t < array[j]; j--)
                array[j + 1] = array[j];
            array[j + 1] = t;
        }
    }

Copy after login

Quick sort

Features: high efficiency, time complexity is nlogn.

Adopt the idea of the divide and conquer method: first set an axis value pivot, and then use this axis value as the dividing basis to divide the sequence to be sorted into two parts larger than the pivot and smaller than the pivot, and then divide the divided subdivisions. The sequence is quick sorted until the subsequence contains one element.

public void quickSort(int array[], int low, int high) {// 传入low=0，high=array.length-1;
        int pivot, p_pos, i, t;// pivot->位索引;p_pos->轴值。        
        if (low < high) {
            p_pos = low;
            pivot = array[p_pos];            
            for (i = low + 1; i <= high; i++)                
            if (array[i] > pivot) {
                    p_pos++;
                    t = array[p_pos];
                    array[p_pos] = array[i];
                    array[i] = t;
                }
            t = array[low];
            array[low] = array[p_pos];
            array[p_pos] = t;            // 分而治之
            quickSort(array, low, p_pos - 1);// 排序左半部分
            quickSort(array, p_pos + 1, high);// 排序右半部分
        }

Copy after login