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

Array sorting problem (2)

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, so let's just go 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; } } } } 大家有没有发现，上面的代码其实可以优化，会体现你的基本功哦。要装逼的话可以和面试官提出来的哦。int的默认值是0，所以我们没有必要扫描它一遍给它赋个默认值了。所以这段代码是多余的： [csharp] view plain copyfor (var index = 0; index < indexArray.Length; index++) { indexArray[index] = 0; } 我们来测试一下这个方法： [csharp] view plain copystatic 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. 我们得到的结果:

It's done. If you have any questions about the above algorithm, or a better solution, welcome to communicate.

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.

Linked list, sorting project to learn more resources.

Follow our official account for regular tweets. Pay attention to the courses, there will be regular discounts.

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.