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

Sorting Analysis and parity sorting in arrays

We have learned the general sorting methods in textbooks before, such as bubbling, quick arrangement, insertion, merging. The time complexity is O (N), O (Nlogn) and O (N2). Today we look at sorting in some specific cases, and whether all sorts are based on size, sometimes the range of numbers to be sorted is known, let's look at two typical examples:

To give you an array of integers, I want to put odd numbers first and even numbers after, that is, no even number appears before the odd number. I'll give you an integer array with numbers between [0-100]. Can you sort it for me in an optimal way?

Let's look at the first question today. Or according to the previous six-step.

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

The requirements have been refined in the title, and no even number comes before the odd number. For example, {1pr 2rec 3je 4je 5} will be arranged into {1pr 3je 5pr 4je 2}. Of course, there is one more question to be confirmed. Do we care about its size? That is, do both odd and even parts need ascending order? We can tell you here that we can ignore this. In this question, we only care about parity.

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

When we get this problem, the first thing that comes to mind is how to judge odd and even numbers. But that's not really the point of the question. A very simple method has come out. I declare that two arrays, one holds the odd number, the other holds the even number, and then merges the two arrays and returns them. This method is feasible, and when picking parity, we only need to scan the array once, but we waste storage space, at least we need to declare two more temporary arrays. Moreover, we do not know in advance how long the array of odd and even numbers should be. Is there a better way?

Let's take a look at the previous example and see if we can find anything strange. In fact, 1 is not moving, but 2 is sure to move ​ back. Where should I put it? The exact location doesn't matter, but just make sure there is no odd number behind it. Then from back to front, 5 is odd, make sure you want to put it forward. So far, if we can exchange 2 and 5, the problem will be solved perfectly. Yes, we just have to find out the even numbers from the back to the back, then find the odd numbers from the back to the front, and then exchange them. Find the next one. If we take this approach, we can solve the problem by scanning the array once.

3. Explain your algorithm and implementation

From the above analysis, we only need to set two temporary variables. One goes from back to back, the other from back to front, the condition of termination is that they meet. It would be nice to define another temporary variable and be responsible for the exchange.

4. When writing code, remember, be sure to explain what you are doing now

Then let's go straight to the code.

Public static void Switch (int [] array) {if (array! = null & & array.Length > 1) {int begin = 0; int end = array.Length-1; while (begin

< end) { if (array[begin] % 2 == 0) // 偶数 { if (array[end] % 2 == 1) //奇数 { //交换 int temp = array[end]; array[end] = array[begin]; array[begin] = temp; begin++; end--; } else { end--; } } else { begin++; } } } } 在上面的代码中有一个地方可以优化，当我们找到前面待交换的偶数，再确定后面是否有奇数时，我们总是会将后面的指针往前移动。所以end -- 可以移出来，将外面的else也删掉。 5. Workthrough6. 修复缺陷我们一起来测试一下这个方法static void Main(string[] args) { int[] array = new int[] { 1, 2, 3, 4, 5 }; Switch(array); foreach (var a in array) { Console.WriteLine(a); } } 大功告成了哈。欢迎大家关注我的公众号，还有我的系列专题课程 视频教程数据结构与算法经典算法面试题辅导排序专题讲解链表专题讲解 大家有什么更好的解法，也欢迎讨论哈。

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.