Tag:Sorting algorithm series
Category:牛客网--课程学习
Article From:https://www.cnblogs.com/ranjiewen/p/9060492.html

For a int array, please write a counting sort algorithm to sort the array elements.

Given an array of intAAnd the size of an arrayn,Please return to the sorted array.

Test sample:
[1,2,3,5,2,3],6
[1,2,2,3,3,5]
  • Counting sorting

class CountingSort {
public:
    int* countingSort(int* A, int n) {
        // write code here
        int min=A[0],max=A[0];
        for(int i=1;i<n;i++)
        {
            if(A[i]<min) min=A[i];
            if(A[i]>max) max=A[i];
        }
        int k=max-min+1;
        int* B=new int[k](); //Initialization is 0
        for(int i=0;i<n;i++)
            B[A[i]-min]++;
        int idx=0;
        for(int i=min;i<=max;i++)
            for(int j=0;j<B[i-min];j++)
                A[idx++]=i;
        delete []B;
        return A;
    }
};

For a int array, please write a cardinality sorting algorithm to sort the array elements.

Given an array of intAAnd the size of an arrayn,Please return to the sorted array. The guarantee element is less than 2000.

Test sample:
[1,2,3,5,2,3],6
[1,2,2,3,3,5]
  • Cardinality sorting

#include <iostream>
using namespace std;
const int MAX = 10;

void print(int *a, int sz) {
    for (int i = 0; i < sz; i++)
        cout << a[i] << " ";
    cout << endl;
}

void RadixSortLSD(int *a, int arraySize)
{
    int i, bucket[MAX], maxVal = 0, digitPosition = 1;
    for (i = 0; i < arraySize; i++) {
        if (a[i] > maxVal) maxVal = a[i];
    }

    int pass = 1;  // used to show the progress
    /* maxVal: this variable decide the while-loop count
    if maxVal is 3 digits, then we loop through 3 times */
    while (maxVal / digitPosition > 0) {
        /* reset counter */
        int digitCount[10] = { 0 }; //For each bit: Statistics 0-10 for numbers

        /* count pos-th digits (keys) */
        for (i = 0; i < arraySize; i++)
            digitCount[a[i] / digitPosition % 10]++;

        /* accumulated count */
        for (i = 1; i < 10; i++)
            digitCount[i] += digitCount[i - 1];

        /* To keep the order, start from back side */
        for (i = arraySize - 1; i >= 0; i--)
        {
            int temp = a[i] / digitPosition % 10;
            bucket[--digitCount[temp]] = a[i];
        }

        /* rearrange the original array using elements in the bucket */
        for (i = 0; i < arraySize; i++)
            a[i] = bucket[i];

        /* at this point, a array is sorted by digitPosition-th digit */
        cout << "pass #" << pass++ << ": ";
        print(a, arraySize);

        /* move up the digit position */
        digitPosition *= 10;
    }
}

 

Leave a Reply

Your email address will not be published. Required fields are marked *