奇偶排序

编辑:展开网互动百科 时间:2020-01-24 04:32:46
编辑 锁定
本词条缺少名片图,补充相关内容使词条更完整,还能快速升级,赶紧来编辑吧!
奇偶排序法的思路是在数组中重复两趟扫描。第一趟扫描选择所有的数据项对,a[j]和a[j+1],j是奇数(j=1, 3, 5……)。如果它们的关键字的值次序颠倒,就交换它们。第二趟扫描对所有的偶数数据项进行同样的操作(j=2, 4,6……)。重复进行这样两趟的排序直到数组全部有序。
中文名
奇偶排序
外文名
Parity sorting
思    路
数组中重复两趟扫描
相关著作
Java数据结构和算法

目录

奇偶排序详细说明

编辑
和冒泡排序法一样,奇偶排序的时间复杂度为O(N^2)。
Java数据结构和算法》中写道:
奇偶排序实际上在多处理器环境中很有用,处理器可以分别同时处理每一个奇数对,然后又同时处理偶数对。因为奇数对是彼此独立的,每一刻都可以用不同的处理器比较和交换。这样可以非常快速地排序。
Java代码
1 public void oddEvenSort(int[] array){
2 for (int i = 0; i < array.length; i += 2){
3 int j = 0;
4 scan(array, j);
5 j = 1;
6 scan(array, j);
7 }
8 }
9
10 private void scan(int[] array, int j) {
11 while (j < array.length - 1){
12 if (array[j] > array[j + 1]){
13 swap(array, j, j + 1);
14 }
15 j += 2;
16 }
17 }
18
19 private static void swap(int[] array, int index1, int index2) {
20 int temp = array[index1];
21 array[index1] = array[index2];
22 array[index2] = temp;
23 }
后来有朋友提出建议,我小小的改动了一下,对随机数组排序的效率略有提高:
Java代码
24 public static void oddEvenSort(int[] array) {
25 boolean unsorted = true;
26 while (unsorted) {
27 unsorted = false;
28 int i = 1;
29 boolean oddUnsorted = scan(array, i);
30 i = 0;
31 boolean evenUnsorted = scan(array, i);
32 unsorted = oddUnsorted || evenUnsorted;
33 }
34 }
35
36 private static boolean scan(int[] array, int i) {
37 boolean unsorted = false;
38 while (i < array.length - 1) {
39 if (array[i] > array[i + 1]) {
40 swap(array, i, i + 1);
41 unsorted = true;
42 }
43 i += 2;
44 }
45 return unsorted;
46 }
47
48 private static void swap(int[] array, int index1, int index2) {
49 int temp = array[index1];
50 array[index1] = array[index2];
51 array[index2] = temp;
52 }
词条标签:
计算机术语 计算机学