Ten sorting algorithms

sort

Bubble sort

Sorting process

1. Given that the length of the array is n, if the total number of sorting passes is t, then t=n-1

2. The I pass (I value range [1,n-1]) starts from the 0 th element to the n-i element, and compares and exchanges the two adjacent elements one by one to ensure that the maximum (or minimum) value is later

3. Repeat step 2 after i + +

Time complexity

  • Worst case: n(n^2)
  • Best: n(n)

Spatial complexity

A basic temporary variable is assigned, so the space complexity is O(1)

stability

Exchange between adjacent data, so it is [stable sorting]

code implementation

	public List<Integer> sort(List<Integer> list) {
        int size = 0;
        if(list == null || (size = list.size()) <= 1){
            return list;
        }
        //Total number of trips
        int t = size - 1;
        for (int i = 1; i <= t; i++) {
            boolean sorted = true;
            for (int j = 0; j < size - i; j++) {
                if (list.get(j) <= list.get(j + 1)) {
                    continue;
                }
                //The front one is bigger than the back one. It needs to be exchanged
                Integer temp = list.get(j);
                list.set(j, list.get(j + 1));
                list.set(j + 1, temp);
                sorted = false;
            }
            if(sorted){
                //[optimization point] if there is no exchange in one trip, it means that the scheduling is finished
                break;
            }
        }
        return list;
    }

Selection sort

Sorting process

1. Given that the length of the array is n, if the total number of sorting passes is t, then t=n-1

2. The i-th pass (I value range [1,n-1]) starts from the i-th element to the n-1st element, and selects the position of the minimum (or maximum) value (assumed to be midx). If the value of the midx position is smaller (or larger) than the value of the i-1st position, it exchanges the values of the midx and i-1

3. Repeat step 2 after i + +

Time complexity

  • Worst case: n(n^2)
  • Best: n(n^2) does not jump out in advance

Spatial complexity

A basic temporary variable is assigned, so the space complexity is O(1)

stability

The earliest value of the i-1 trip needs to be exchanged with the data of the i-1 position, that is to say, the data of the i-1 position needs to span the replacement. In the process of replacement, it may span the same data as the i-1, and the stability is damaged. Therefore, this sort is [unstable sort]

code implementation

    public List<Integer> sort(List<Integer> list) {
        int size = 0;
        if(list == null || (size = list.size()) <= 1){
            return list;
        }
        //Number of trips
        int t = size - 1;
        for (int i = 1; i <= t; i++) {
            int minIdx = i - 1;
            for (int j = i; j < size; j++) {
                if (list.get(minIdx) > list.get(j)) {
                    //Select lower value subscript
                    minIdx = j;
                }
            }
            if (i - 1 != minIdx) {
                //If the subscript of the smaller value is not i-1, it needs to be exchanged
                Integer point = list.get(i - 1);
                list.set(i - 1, list.get(minIdx));
                list.set(minIdx, point);
            }
        }
        return list;
    }

Insertion sort

Sorting process

[Note: the feature of insertion sorting is that when selecting each reference element, all elements before this element are ordered, so the efficiency of insertion sorting for basically ordered sets is high]

1. Given that the length of the array is n, if the total number of sorting passes is t, then t=n-1

2. The i pass (i value range [1,n-1]) starts from the i-1 element to the 0 element, and compares with the i-1 reference element (assuming that the element is v) one by one from the back to the front. The element larger (or smaller) than V moves backward one position until it is no larger (or no smaller) than v. note that the position is J (obviously the range of J is [0,i-1]), and then set V to the position of j+1

3. Repeat step 2 after i + +

Time complexity

  • Best: O (n) (original order)
  • Worst case: O (N2) (originally in reverse order)

Spatial complexity

A basic temporary variable is assigned, so the space complexity is O(1)

stability

The span of backward displacement is all 1. Although the span of forward displacement of reference elements may be greater than 1, the elements crossed are all elements larger (or smaller) than the reference elements. The stability is not damaged, so it is [stable sorting]

code implementation

    public List<Integer> sort(List<Integer> list) {
        int size = 0;
        if(list == null || (size = list.size()) <= 1){
            return list;
        }
        if(size < 2){return list;}
        //Start with the second element of the data
        for (int i = 1; i < size; i++) {
            //Reference element
            Integer point = list.get(i);
            int idx = i;
            //Elements in front of reference elements are compared with reference elements one by one
            //The data before i is ordered before each insertion and sorting
            for (int j = i - 1; j >= 0; j--) {
                if(point < list.get(j)){
                    //Larger than the reference element, you need to move back
                    list.set(idx,list.get(j));
                    //Mark the position before moving back
                    idx = j;
                }else{
                    //Based on the feature that the data before i is in order before each insertion and sorting
                    //So no comparison is needed for the previous data
                    break;
                }
            }
            if(idx != i){
                //If the data larger than i position is moved backward, then the data in idx position is also moved backward to idx+1 position
                //Then the data of idx location needs to be replaced with reference data
                list.set(idx,point);
            }
        }
        return list;
    }

Quick sort

Sorting process

This is a recursive sort

1. Select a reference data each time, and then allocate the data to be sorted on the left and right sides of the reference data. The data on the left side is smaller (or larger) than the reference data, and the data on the right side is larger (or smaller) than the reference data

2. If the left and right batches of data obtained in the previous step have more than 2 data, perform the previous step for them respectively

Time complexity

  • Best: O(nlogn)
  • Worst: n ^ 2

Spatial complexity

Once the basic temporary variable is assigned, so the spatial complexity is O(1), but the sorting is recursive. The number of times of recursion is at least (logn) + 1, so the spatial complexity is logn*O(1), that is, O(logn)

stability

When constructing the right set, the permutations are all the permutations of a number behind the reference element and the rightmost element that is not compared with the reference element, which destroys the stability, so it is unstable sorting

code implementation

	public List<Integer> sort(List<Integer> list) {
        int size = 0;
        if(list == null || (size = list.size()) <= 1){
            return list;
        }
        return sort(list,0,size - 1);
    }

    private List<Integer> sort(List<Integer> list,final int begin,final int end){
        //The reference data is optional. Here, select the first data to be sorted
        Integer point = list.get(begin);
        int left = begin;
        int right = end;
        //Since the first data is selected as the reference data, traverse from the second data
        int idx = begin + 1;
        while (idx <= right){
            int temp = list.get(idx);
            if(temp < point){
                //Smaller than reference data, need to move to the left of reference data
                list.set(idx - 1,temp);
                list.set(idx,point);
                idx++;
            }else if(temp > point){
                //It is larger than the reference data and needs to be moved to the right of the reference data. In fact, temp itself is on the right of the reference data
                //If the location of this temp remains the same, the next time you encounter data smaller than the reference data, after exchanging data, this temp will appear on the left side of the reference data, which is wrong
                //So we need to move temp to the far right and reduce the sorting length
                //Note: the process of moving temp to the back destroys the stability
                list.set(idx,list.get(right));
                list.set(right,temp);
                right--;
            }else{
                //Same as reference data
                idx++;
                //Without this line of code, the purpose of this line of code is to try not to damage the documentation, but the above code has been damaged
                point = temp;
            }
        }
        //So far, the data from begin to end has been divided
        //idx-1 at this time represents the location of the reference data
        int pointIdx = idx - 1;
        if(pointIdx - begin > 1){
            //If the left amount of reference data is greater than 1, you need to split the left again
            list = sort(list,begin,pointIdx - 1);
        }
        if(end - pointIdx > 1){
            //If the amount of data on the right side of the reference data is greater than 1, you need to split the right side again
            list = sort(list,pointIdx + 1,end);
        }
        return list;
    }

Shell Sort

Sorting process

Hill's sorting is based on the theory of [basic ordered insertion sorting with high efficiency] to optimize the sorting and try to construct [basic ordered]

1. Given that the length of the array is n, select a step size step=n/2, group the array, divide all the subscripts idx%step into one group, so that the original array will be divided into step groups, and then insert and sort each group. After the first round, the elements with subscript difference of n/2 are in order

2. Shorten the step of the previous step so that step=step/2=(n/2)/2, after this round, the elements with subscript difference (n/2)/2 are in order

3. Continue shortening step until step=1, and the elements with the difference of the last subscript of 1 are ordered and sorted

[Note: Hill sorting with step 1 is equivalent to Hill sorting]

Time complexity

  • Best: O (n) (originally in order)
  • Worst case: O (n ^ 2) (after each step grouping, it is in reverse order (n ^ 2) / 2 + (n ^ 2) / 4 + (n ^ 2) / 8 + (n ^ 2) / 16 +... + n)
  • Average: O (n ^ 1.3) (very complex)

Spatial complexity

A basic temporary variable is assigned, so the space complexity is O(1)

stability

When the step length is greater than 1, there is crossing replacement and the stability is destroyed, so it is [unstable sequencing]

code implementation

    public List<Integer> sort(List<Integer> list) {
        int size = 0;
        if (list == null || (size = list.size()) <= 1) {
            return list;
        }
        int step = size / 2;
        //int step = 1; / / insert sort when step equals 1
        do {
            list = sort(list, size, step);
            step /= 2;
        } while (step > 0);
        return list;
    }

    private List<Integer> sort(List<Integer> list, int size, int step) {
        for (int s = 0; s < step; s++) {
            //Insert sort by reference to
            for (int i = s + step; i < size; i += step) {
                Integer point = list.get(i);
                int idx = i;
                for (int j = i - step; j >= 0; j -= step) {
                    if(point < list.get(j)){
                        list.set(idx,list.get(j));
                        idx = j;
                    }else {
                        break;
                    }
                }
                if(idx != i){
                    list.set(idx,point);
                }
            }
        }
        return list;
    }

Merge sort

Sorting process

Merge sorting includes two operations: split and merge

1. Given that the length of an array is n, the array is divided into [0,(n-1)/2] and [((n-1)/2) + 1,n-1] two sibling arrays

2. Continue to split the two brothers array in the previous step into four parts, which are composed of two brothers

3. Continue to dismantle until it can't be dismantled again

4. Merge. From the bottom to the top, merge the sibling data in order. The merged array is the sorting of the sibling's parent array

5. Merge the array from the previous step and its sibling array in order

6. Keep closing until there is no brother

Time complexity

  • Best: O (n logn) (the number of splits is logn, so the number of merges of an element is logn, and one has n elements)
  • Worst case: O(nlogn)

Spatial complexity

The first iteration needs to open up n/2 space for temporary storage elements (the left side will not start if it is not completed), and the second iteration is n / 4 (the left side will not start if it is not completed)... At the beginning of the right side, the left side is finished, so the space n/2+n/4+n/8+...=n is needed, that is, the space complexity is O(n)

stability

The permutation of elements is reflected in the combination, and the combination is assigned one by one, without destroying the stability, so it is [stable sorting]

code implementation

	public List<Integer> sort(List<Integer> list) {
        int size = 0;
        if (list == null || (size = list.size()) <= 1) {
            return list;
        }
        return sort(list, 0, size - 1);
    }

    private List<Integer> sort(List<Integer> list, int begin, int end) {
        if (begin == end) {
            return Arrays.asList(list.get(begin));
        }
        //Split the set to be sorted into two parts until there is only one element in the left and right parts
        int midd = begin + (end - begin) / 2;
        //On the left, it's in order
        List<Integer> leftList = sort(list, begin, midd);
        //On the right, it's in order
        List<Integer> rightList = sort(list, midd + 1, end);

        //Merge two ordered sets together,
        List<Integer> mergeList = new ArrayList<>(end - begin + 1);
        int leftIdx = 0, rightIdx = 0, mergeIdx = 0;
        while (leftIdx < leftList.size() && rightIdx < rightList.size()) {
            mergeList.add(leftList.get(leftIdx) <= rightList.get(rightIdx) ? leftList.get(leftIdx++) : rightList.get(rightIdx++));
            mergeIdx++;
        }
        while (leftIdx < leftList.size()) {
            mergeList.add(leftList.get(leftIdx++));
        }
        while (rightIdx < rightList.size()) {
            mergeList.add(rightList.get(rightIdx++));
        }
        return mergeList;
    }

Heap sort

Sorting process

First of all, understand the large (or small) top heap: a complete binary tree, and each node is larger (or smaller) than its left and right child nodes

Relationship between top heap and array: the subscript of a top heap from top to bottom and from left to right represents the small scale of the array

Order of top heap Construction: start from the parent node of the last node to the front of the array, so as to ensure that the smallest subtree is the top heap

1. It is known that the length of the array is n, and the subscript of the parent node of the last element is n/2-1 to construct the top heap

2. Then n/2-2 started to construct the top reactor

3,. . . If the data is long enough, the parent node of the vertex in the first step is (n/2-1)/2-1, assuming that the sequence number is p. if the top heap with P as the vertex is constructed, the left and right subtrees of P are not the top push subtrees, can they not be constructed? So that's why we have to start with the minimum duding heap

4. After the array is completely converted to the top heap, exchange the element with subscript 0 with the last unfixed element, so that the last element is the largest (or the smallest), and at the same time, fix the element until the sorting is completed. Note that the array other than the fixed number is not a top heap at this time. The reason is that the vertices have been swapped and the top heap needs to be reconstructed. This time, it is easier because the sub trees of vertices are all top heaps

5. Repeat the previous step until the element with a fixed subscript of 1, i.e. the second element, ends the sorting

Time complexity

  • Best: O(nlogn)
  • Worst case: O(nlogn)

Spatial complexity

A basic temporary variable is assigned, so the space complexity is O(1)

stability

In the construction of the top heap, there is a crossing displacement. There is no inevitable size relationship between the crossed element and the replaced element, and the stability is destroyed. At the same time, the process of setting the vertex when the maximum value is fixed is also a crossing displacement, which also destroys the stability. In summary, it is [unstable sequencing]

code implementation

	public List<Integer> sort(List<Integer> list) {
        int size = 0;
        if (list == null || (size = list.size()) <= 1) {
            return list;
        }
        for (int idx = size / 2 - 1; idx >= 0; idx--) {
            //Construction of large top reactor
            list = buildHeap(list, idx, size - 1);
        }
        //Large top reactor to be constructed
        for (int idx = size - 1; idx > 0; idx--) {
            //Change the fixed point of the large top reactor to the back (the first change to the back indicates that a large number has been confirmed)
            Integer temp = list.get(0);
            list.set(0, list.get(idx));
            list.set(idx, temp);
            //The fixed point of the large top reactor is replaced, and the large top reactor needs to be reconstructed. At the same time, the large number has been confirmed and should not participate in the reconstruction of the large top reactor
            list = buildHeap(list, 0, idx - 1);
        }
        return list;
    }

    private List<Integer> buildHeap(List<Integer> list, int begin, int end) {
        //Take this as the vertex
        Integer point = list.get(begin);
        int idx = begin * 2 + 1;
        while (idx <= end) {
            if (idx + 1 <= end && list.get(idx) < list.get(idx + 1)) {
                //Select the larger of the left and right child nodes of the vertex
                idx++;
            }
            //Greater and vertex comparison
            if (list.get(idx) > point) {
                //Exchange guarantee vertex maximum
                list.set(begin, list.get(idx));
                list.set(idx, point);
                //Continue to construct a large top heap subset with the original vertex's position after moving down as the vertex again
                begin = idx;
                idx = begin * 2 + 1;
            } else {
                break;
            }
        }
        return list;
    }

Bucket sorting

Sorting process

Bucket sorting is an idea of divide and rule

1. Determine the number of barrels b, find out the maximum value and the minimum value, and divide the range from the minimum value to the maximum value into b intervals

2. Traverse the whole set and put all elements into corresponding intervals (buckets)

3. Sort each bucket separately. The sorting method here can be arbitrary

4. Merge from the first bucket to get the result sorting

Time complexity

  • Best: O (n) [O (n) maximum bucket + bucket sorting o (b (n / b) log (n / b)) = O (n) + O (n (logn logb)) is evenly distributed and bucket multi efficiency is high, but space consumption is large]
  • Worst: O(n) min. barrel + O(n^2)

Spatial complexity

O(n+b), n elements need to be stored again, and B buckets need to be stored respectively

stability

The process of separating buckets is stable, and the stability of sorting each bucket determines the overall stability

code implementation

	public List<Integer> sort(List<Integer> list) {
        int size = 0;
        if (list == null || (size = list.size()) <= 1) {
            return list;
        }
        //Get maximum
        Integer[] minAndMax = getMinAndMax(list);
        Integer min = minAndMax[0], max = minAndMax[1];
        //Don't row if the maximum value is the same as the minimum value
        if (min == max) {
            return list;
        }
        //Bucket - Thought
        Integer bucketTotal = getBucketTotal(list);
        List<List<Integer>> lists = splitBucket(list, min, max, bucketTotal);
        //Sort each bucket - here we sort each bucket with merge sort
        Sort sort = new Sort06Merge();
        list.clear();
        for (List<Integer> temp : lists) {
            temp = sort.sort(temp);
            list.addAll(temp);
        }
        return list;
    }

    private Integer[] getMinAndMax(List<Integer> list) {
        Integer[] array = new Integer[2];
        Integer min = list.get(0), max = min;
        for (int idx = 1; idx < list.size(); idx++) {
            if (list.get(idx) < min) {
                min = list.get(idx);
            } else if (list.get(idx) > max) {
                max = list.get(idx);
            }
        }
        array[0] = min;
        array[1] = max;
        return array;
    }

    private Integer getBucketTotal(List<Integer> list) {
        return list.size() < DEF_BUCKET_TOTAL ? list.size() / 2 : DEF_BUCKET_TOTAL;
    }

    private List<List<Integer>> splitBucket(List<Integer> list, Integer min, Integer max, int bucketTotal) {
        List<List<Integer>> lists = new ArrayList<>(bucketTotal);
        for (int idx = 0; idx < bucketTotal; idx++) {
            lists.add(new ArrayList<>());
        }
        Integer step = (max - min + 1) / bucketTotal;
        for (Integer curr : list) {
            int bucketIdx = (curr - min) / step;
            lists.get(bucketIdx).add(curr);
        }
        return lists;
    }

Radix sorting

Sorting process

It is a concrete implementation of bucket sorting

First, define a noun -- cardinality: This is only limited to integers. The so-called cardinality is the i-th number of the integer value from the back to the front with symbols. I here represents the value value read for the i-th time. The cardinality with insufficient length is 0. For example, integer - 109: the cardinality of the number read for the first time is - 9, the second time is - 0, that is, 0, the third time is - 1, and the fourth time is 0.

The range of cardinality [- 9,9], which states 19 buckets, is used to store the elements corresponding to the 19 cardinalities [- 9,9]

1. Find out the longest data in the array, and define the maximum length as the number of times to execute the bucket

2. In the first round, all elements are put into the corresponding 19 buckets in the order of cardinality (the first round is the last one with sign), and then all bucket data are written into the original array in turn, and all buckets are emptied

3. In the second round, all elements are put into the corresponding 19 buckets in the order of cardinality (the second round is the last number with sign), and then all bucket data are written into the original array in turn, and all buckets are emptied

4,. . .

5. Until the sorting of the length round is completed

Time complexity

  • Best: O (max (length) * n * 2) = O (n * k)
  • Worst case: O (max (length) * n * 2) = O (n * k)

Spatial complexity

N data plus r barrels, O(n+r)

stability

The same elements will be divided into the same bucket every time, and the sequence will not be disordered. All of them are stable sequence

code implementation

	public List<Integer> sort(List<Integer> list) {
        int size = 0;
        if (list == null || (size = list.size()) <= 1) {
            return list;
        }
        //First define a noun -- cardinality: This is only limited to integers. The so-called cardinality is the i-th number of the integer value from the back to the front with symbols. The I here represents the value read for the i-th time
        //For example, if the integer - 109 is read for the first time, the cardinality of the number is - 9, the second is - 0, that is, 0, and the third is - 1
        //Find the number with the largest absolute value, in order to calculate the longest data
        int max = 0;
        for (Integer value : list) {
            if(Math.abs(value) > max){
                max = Math.abs(value);
            }
        }
        return sort(list, (int) Math.log10(max) + 1);
    }

    private List<Integer> sort(List<Integer> list, int maxLength) {
        //Why 19? Consider negative numbers
        List<List<Integer>> lists = new ArrayList<>(19);
        //Initialize temporary array
        for (int idx = 0; idx < 19; idx++) {
            //Why not use ArrayList here
            lists.add(new LinkedList<>());
        }
        for (int idx = 1, radix = 1; idx <= maxLength; idx++, radix *= 10) {
            for (Integer value : list) {
                //The reason for Radix plus 9 is that the order of Radix is - 9 to 9
                lists.get(((value / radix) % 10) + 9 ).add(value);
            }
            int i = 0;
            for (List<Integer> tempList : lists) {
                if(tempList.isEmpty()){
                    continue;
                }
                //Each round of grouping by cardinality will be written to the element array
                for (Integer value : tempList) {
                    list.set(i++,value);
                }
                //The writes to tempList are all add(), so you need to clear and write again in the next round
                tempList.clear();
            }
        }
        return list;
    }

Counting sort

Sorting process

Barrel partitioning principle

First of all, it emphasizes applicability, which is suitable for sorting with large amount of data but small value range of elements, such as score ranking of 100W candidates, national population age ranking

1. First find out the minimum value, confirm the value norm [min,max], define the count array count length as max-min+1

2. Traverse the array to be arranged, count the times of each element, and record the times in the corresponding position of the count array (subtracting min from the element value is the count subscript)

3. If stability is not considered, just traverse the count array, write the value of index idx plus min in turn to count[idx] times in the new array, and the sorting is completed

4. If stability is considered, it is necessary to record the maximum position of each data in the sorting result array

5. Traverse the original array element value in reverse order, and subtract min from value to get the subscript idx in count. At this time, count[idx] - 1 is the position of value in the sorting result array

Time complexity

  • Best: O(n+k)(k is the length of count)
  • Worst case: O(n+k)

Spatial complexity

N elements + K counts = O(n+k)

stability

Stable sorting can be realized when the number of records and the maximum position that should be written are recorded

code implementation

	private static final int MAX_STEP = 1024;

    @Override
    public List<Integer> sort(List<Integer> list) {
        int size = 0;
        if (list == null || (size = list.size()) <= 1) {
            return list;
        }
        //Get maximum
        Integer[] minAndMax = getMinAndMax(list);
        Integer min = minAndMax[0], max = minAndMax[1];
        //Don't row if the maximum value is the same as the minimum value
        if (min == max) {
            return list;
        }
        return sort(list, min, max, true);
    }

    private Integer[] getMinAndMax(List<Integer> list) {
        Integer[] array = new Integer[2];
        Integer min = list.get(0), max = min;
        for (int idx = 1; idx < list.size(); idx++) {
            if (list.get(idx) < min) {
                min = list.get(idx);
            } else if (list.get(idx) > max) {
                max = list.get(idx);
            }
        }
        array[0] = min;
        array[1] = max;
        return array;
    }

    private List<Integer> sort(List<Integer> list, Integer min, Integer max, boolean stability) {
        int countLength = max - min + 1;
        if (countLength > MAX_STEP) {
            System.err.println("The range of data value is too large. It is not recommended to count and sort");
            return list;
        }
        int[] count = new int[countLength];
        for (Integer value : list) {
            //Record the number of occurrences of each identical element
            ++count[value - min];
        }
        if (stability) {
            Integer [] sorted = new Integer[list.size()];
            for (int idx = 1; idx < countLength; idx++) {
                //Record the maximum position of the element in the ordered array based on the number of occurrences
                count[idx] = count[idx] + count[idx - 1];
            }
            //This has to be in reverse order
            for (int idx = list.size() - 1; idx >= 0; idx--) {
                Integer temp = list.get(idx);
                sorted[--count[temp - min]] = temp;
            }
            return Arrays.asList(sorted);
        } else {
            //If stability is not considered
            int k = 0;
            for (int idx = 0; idx < countLength; idx++) {
                for (int j = 0; j < count[idx]; j++) {
                    list.set(k++, idx + min);
                }
            }
            return list;
        }
    }

Tags: Programming shell

Posted on Wed, 18 Mar 2020 03:14:16 -0700 by adamjnz