A brief introduction to the odd even sorting algorithm and its implementation in Java array
- 2020-05-09 18:32:39
- OfStack
Odd-even sorting is a kind of unique sorting. The basic idea is to arrange odd columns in 1 order, even columns in 1 order, odd columns in 1 order, and even columns in 1 order, until all of them are in order
For example,
For row array
[6 2 4 1 5 9]
The first time the odd column is compared, the odd column is compared to its neighbor even columns, such as 6 and 2,4 and 1,5 and 9
[6 2 4 1 5 9]
When you swap it out
[2 6 1 4 5 9]
The second time you compare even columns, you compare 6 to 1,5 to 5
[2 6 1 4 5 9]
When you swap it out
[2 1 6 4 5 9]
The third row is an odd column, and we chose 2,6, and 5 to compare with their neighbor columns
[2 1 6 4 5 9]
After exchanging
[1 2 4 6 5 9]
The fourth row of even columns
[1 2 4 6 5 9]
One exchange
[1 2 4 5 6 9]
Java implementation:
static void oddEvensort(int[] ary) {
// Parity sorting
boolean flag = true;
while (flag) {
boolean odd = false, even = false;
for (int i = 0; i < ary.length - 1; i+=2) {
if (ary[i] > ary[i + 1]) {
ary[i] = ary[i + 1] + 0 * (ary[i + 1] = ary[i]);
odd = true;
}
}
for (int i = 1; i < ary.length - 1; i+=2) {
if (ary[i] > ary[i + 1]) {
ary[i] = ary[i + 1] + 0 * (ary[i + 1] = ary[i]);
even = true;
}
}
flag = odd || even; // if false , indicating that no matter whether the sequence is odd or even, 1 There are no qualified comparisons
}
}
flag = odd || even; If one of is true, which means it is still swapping, then flag is only false if they are all false.
So flag = odd && even; has one false, and it no longer cycles as a whole. Like bubble sort 1, you can reduce the last inner loop.