Shulou(Shulou.com)06/03 Report--

Array sorting problem-counting sorting

Yesterday we left a question "give you an integer array, the number that appears in [0-100], can you use the optimal method to sort me?"

1. Make sure we understand the problem and try an example to make sure we understand it correctly.

This is a sorting algorithm problem, we have learned a lot of sorting algorithms. The difference is that it gives an additional condition that each number in the array is between 1 and 100. If we adopt the traditional sorting algorithm, we don't seem to need this condition. If you find that some conditions are not useful during the interview, basically the algorithm we give may not be optimal, or we may not solve its original requirements. For example, in the array {50,46,50,0,100 zero}, we can see at a glance that there are two zeros, one in 46, two in 50, and one in 100. if we put them together, we will get {0, 46, 50, 50100}.

two。 Think about what you can do to solve the problem, which one will you choose, and why?

In the above analysis, we can conclude that there are two important steps involved in sorting manually. 1: count the number of occurrences of each number between 0-100: 2: splice them in the order of 0-100. So now we need to solve the problem of how to make it easy to count. Declare a number with a length of 101. Suppose 50 appears once, and we add 1. 0 to the subscript 50 in the array. When it's all counted, we'll scan the number and write the results back.

Now let's look at its complexity. We scanned the original array once and the count array again, so our complexity is O (n). Here we also find that we embody a principle in this question, that is, to trade space for time.

3. Explain your algorithm and implement the method count part: scan the original array and find the corresponding position int [] indexArray = new int in the index array; foreach (var e in inputArray) {indexArray [e] + +;} merge the array part int count = 0 for (int index = 0; index)

< indexArray.Length; index++){if(indexArray[index] >

0) / / indicates that the number of index has appeared, and we need to put it together. After a few times, we add a few numbers {inputArray [count] = index; count + +;}} 4. When writing code, remember, be sure to explain what you are doing now

Then let's go straight to the code.

/ / sorts the array with values between 0 and 100 / public static void IndexSort (int [] array) {int [] indexArray = new int [101]; for (var index = 0; index)

< indexArray.Length; index++) { indexArray[index] = 0; } foreach (var e in array) { indexArray[e]++; } int count = 0; for (int index = 0; index < indexArray.Length; index++) { if (indexArray[index] >

0) {for (int elementCount = 0; elementCount < indexArray [index]; elementCount++) {array [count++] = index;}

Have you found that the above code can actually be optimized and will reflect your basic skills? If you want to pretend to be forced, you can bring it up with the interviewer. The default value of int is 0, so there is no need to scan it again and assign it a default value. So this code is redundant:

For (var index = 0; index < indexArray.Length; index++) {indexArray [index] = 0;}

Let's test this method:

Static void Main (string [] args) {int [] array = new int [] {100,8,0,7,0,34}; IndexSort (array); foreach (var e in array) {Console.Write (e + ");}} 5. Repair defect

The results we got:

It's done. Welcome to follow my official account, as well as my series of project courses.

Video tutorial data structure and algorithm Classical algorithm face-to-face question guidance sorting topic explanation linked list topic explanation

If you have any better solution, you are welcome to discuss it.

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.