算法：奇偶排序

柔光的暖阳◎ 2021-12-09 18:11 309阅读 0赞

> 奇偶排序实际上在多处理器的环境中很有用，处理器可以分别同时处理每一个奇数对，然后又同时处理偶数对。因为奇数对是彼此独立的，每一刻都可以用不同的处理器比较和交换。这样可以非常快速的排序

# 算法步骤 #

*  选取所有奇数列的元素与其右侧相邻的元素进行比较，将较小的元素排序在前面；
 *  选取所有偶数列的元素与其右侧相邻的元素进行比较，将较小的元素排序在前面；
 *  重复前面两步，直到所有序列有序为止。

# 举例 #

## 例子1： ##

目标：无序数组----> 从小到大排序

*  待排序数组： 初始化一个flag = true，表示还需要循环排序  
    ![在这里插入图片描述][20200619161356331.png]

因为flag为true，进入循环：

*  假定已经排序完了：flag = false
 *  比较奇数列，奇数列和它最右边相邻的元素比较：基准轴为6，4，5----》 6和2比较，4和1比较，5和9比较。  
    因为发生了交换：表示还没有比较完成，因此flag = true，仍然需要循环  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]
 *  比较偶数列，偶数类和它最右边相邻的元素比较：基准轴为6，4，9—》6和1比较，5和5比较，9无需比较  
    因为发生了交换，令flag = true，仍然需要循环

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]

判断是否还需要比较：因为flag = true，表示发生了交换，仍然需要循环，因此进入循环

*  进入循环之后，就令flag = false，表示已经不需要循环了
 *  进入奇数位比较，奇数列与相邻右侧比较，发生了交换，因此flag = true  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]
 *  比较偶数列，偶数类与相邻右侧比较，没有发生交换，什么也不干  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]

判断是否还需要循环：因为flag = true，表示上次比较发生了交换，因此进入循环：

*  进入循环后，令flag = false，期望经过这一次循环之后就不需要循环了
 *  比较奇数列，发现没有发生交换，什么也不干  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]
 *  比较偶数类，发现没有发生交换，什么也不干  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]

判断是否需要跳出循环：发现flag = false，表示当前数组已经整体有序，因此跳出循环

## 为什么说奇偶排序是并行算法 ##

从示例中，可看出整个比较交换分为独立的奇阶段或偶阶段。在每个阶段内，所有的比较和交换是没有数据相关性。因此，每一次比较和交换都可独立执行，也就可以并行化了。比如，第一次奇阶段排序中，100个元素可以分为4个CPU执行，第一个排序1-25，第二个排序26-50，第三个排序51-75，第四个排序76-100。

# 代码实现 #

## java ##

package com.oceanstar;
    
    import java.util.*;
    
    public class TreeNode {
        
        // 从最后一个非叶子节点开始调整，调整为一个大根堆
        private static void OddEventSort(int[]arr){
        
            if (arr == null || arr.length < 2){
        
                return;
            }
            boolean flag = true; //
            while (flag){
        
                //先默认已经排序完了
                flag = false;
    
    
                //先进行 奇数位 排序
                for (int i = 0; i < arr.length ; i = i + 2){
        
                    //如果 前者 大于 后者，则需要进行交换操作,也要防止边界
                    if ((i + 1) < arr.length && arr[i] > arr[i+1]){
        
                        swap(arr, i, i+1);
                        //说明存在过排序，还没有排序完
                        flag = true;
                    }
                }
    
                //再进行 奇数位 排序
                for (int i = 1; i < arr.length; i = i + 2){
        
                    //如果 前者 大于 后者，则需要进行交换操作，也要防止边界
                    if ((i + 1) < arr.length && arr[i] > arr[i+1]){
        
                        swap(arr, i, i+1);
                        //说明存在过排序，还没有排序完
                        flag = true;
                    }
                }
            }
        }
    
    
        private static void swap(int []arr, int i, int j){
        
            int t = arr[i];
            arr[i] = arr[j];
            arr[j] = t;
        }
    
        public static void main(String[] args) {
        
            int[] arr = new int[]{
        23,19,81,79,89,83,17,48,55,26};
            OddEventSort(arr);
    
            System.out.println(Arrays.toString(arr));
        }
    }

## golang ##

package main
    
    import (
    	"fmt"
    )
    
    
    func OddEventSort(arr [] int)[]int{
        
    	length := len(arr)
    	 if length <= 1 {
        
    		return arr
    	}else{
        
    		 flag := true
    		 for flag  {
        
    		 	 flag = false
    			 for i := 0; i + 1 < length ; i = i + 2 {
           //先进行 奇数位 排序.  因为是与右侧相邻的元素比较，所以i + 1 必须小于length
    				 if arr[i] > arr[i + 1] {
        
    				 	arr[i], arr[i + 1] = arr[i + 1], arr[i]
    				 	flag = true
    				 }
    			 }
    
    			 for i := 1; i + 1 < length ; i = i + 2 {
           //进行 偶数位 排序.  因为是与右侧相邻的元素比较，所以i + 1 必须小于length
    				 if arr[i] > arr[i + 1] {
        
    					 arr[i], arr[i + 1] = arr[i + 1], arr[i]
    					 flag = true
    				 }
    			 }
    		 }
    
    		 return arr;
    	}
    }
    
    
    
    func main() {
        
    	arr:=[]int {
        1,9,2,8,3,7,4,6,5,10, -1}
    	fmt.Println(OddEventSort(arr))
    	fmt.Println(arr)
    }

## C++ ##

### 实现过程 ###

#include <iostream>
    #include <list>
    #include <vector>
    #include <map>
    
    
    template<typename T>
    std::ostream& print(std::ostream &out,T const &val) {
        
        return (out << val << " ");
    }
    
    template<typename T1,typename T2>
    std::ostream& print(std::ostream &out,std::pair<T1,T2> const &val) {
        
        return (out << "{" << val.first << " " << val.second << "} ");
    }
    
    template<template<typename,typename...> class TT,typename... Args>
    std::ostream& operator<<(std::ostream &out,TT<Args...> const &cont) {
        
        for(auto&& elem : cont) print(out,elem);
        out << "\n";
        return out;
    }
    
    
    void swap(int & i, int &j){
        
        int t = i;
        i = j;
        j = t;
    }
    
    
    void OddEventSort11(std::vector<int> &vec){
        
        if(vec.empty() || vec.size() == 1){
        
            return;
        }
    
        if(vec[0] < vec[1]){
        
            swap(vec[0], vec[1]);
        }
    
        if(vec[2] < vec[3]){
        
            swap(vec[2], vec[3]);
        }
    
        if(vec[4] < vec[5]){
        
            swap(vec[4], vec[5]);
        }
    
        if(vec[6] < vec[7]){
        
            swap(vec[6], vec[7]);
        }
    
        if(vec[8] < vec[9]){
        
            swap(vec[8], vec[9]);
        }
    
        // 10
        // -------------------------
        if(vec[1] < vec[2]){
        
            swap(vec[1], vec[2]);
        }
    
        if(vec[3] < vec[4]){
        
            swap(vec[3], vec[4]);
        }
    
        if(vec[5] < vec[6]){
        
            swap(vec[5], vec[6]);
        }
    
    
        if(vec[7] < vec[8]){
        
            swap(vec[7], vec[8]);
        }
    
        if(vec[9] < vec[10]){
        
            swap(vec[9], vec[10]);
        }
    }
    
    
    void OddEventSort123(std::vector<int> &vec){
        
        if(vec.empty() || vec.size() == 1){
        
            return;
        }
    
        for(int i = 0; i + 1 < vec.size(); i += 2){
        
            if(vec[i] < vec[i+1]){
        
                swap(vec[i], vec[i+1]);
            }
        }
    
    
        for(int i = 1; i + 1 <  vec.size(); i += 2){
        
            if(vec[i] < vec[i+1]){
        
                swap(vec[i], vec[i+1]);
            }
        }
    
        // 10   // 1+ 1 > 10
        // ---
        if(vec.empty() || vec.size() == 1){
        
            return;
        }
    
        if(vec[0] < vec[1]){
        
            swap(vec[0], vec[1]);
        }
    
        if(vec[2] < vec[3]){
        
            swap(vec[2], vec[3]);
        }
    
        if(vec[4] < vec[5]){
        
            swap(vec[4], vec[5]);
        }
    
        if(vec[6] < vec[7]){
        
            swap(vec[6], vec[7]);
        }
    
        if(vec[8] < vec[9]){
        
            swap(vec[8], vec[9]);
        }
    
        // 10
        // -------------------------
        if(vec[1] < vec[2]){
        
            swap(vec[1], vec[2]);
        }
    
        if(vec[3] < vec[4]){
        
            swap(vec[3], vec[4]);
        }
    
        if(vec[5] < vec[6]){
        
            swap(vec[5], vec[6]);
        }
    
    
        if(vec[7] < vec[8]){
        
            swap(vec[7], vec[8]);
        }
    
        if(vec[9] < vec[10]){
        
            swap(vec[9], vec[10]);
        }
    
    }
    
    void OddEventSortnnn(std::vector<int> &vec){
        
        if(vec.empty() || vec.size() == 1){
        
            return;
        }
    
        for(int i = 0; i + 1 < vec.size(); i += 2){
        
            if(vec[i] < vec[i+1]){
        
                swap(vec[i], vec[i+1]);
            }
        }
    
    
        for(int i = 1; i + 1 <  vec.size(); i += 2){
        
            if(vec[i] < vec[i+1]){
        
                swap(vec[i], vec[i+1]);
            }
        }
    
        // 10   // 1+ 1 > 10
        // ---
        for(int i = 0; i + 1 < vec.size(); i += 2){
        
            if(vec[i] < vec[i+1]){
        
                swap(vec[i], vec[i+1]);
            }
        }
    
    
        for(int i = 1; i + 1 <  vec.size(); i += 2){
        
            if(vec[i] < vec[i+1]){
        
                swap(vec[i], vec[i+1]);
            }
        }
    
    
    
        // ----
    
        for(int i = 0; i + 1 < vec.size(); i += 2){
        
            if(vec[i] < vec[i+1]){
        
                swap(vec[i], vec[i+1]);
            }
        }
    
    
        for(int i = 1; i + 1 <  vec.size(); i += 2){
        
            if(vec[i] < vec[i+1]){
        
                swap(vec[i], vec[i+1]);
            }
        }
    
    }
    
    
    
    void OddEventSort1233(std::vector<int> &vec){
        
        if(vec.empty() || vec.size() == 1){
        
            return;
        }
    
        while (true){
        
            for(int i = 0; i + 1 < vec.size(); i += 2){
        
                if(vec[i] < vec[i+1]){
        
                    swap(vec[i], vec[i+1]);
                }
            }
    
    
            for(int i = 1; i + 1 <  vec.size(); i += 2){
        
                if(vec[i] < vec[i+1]){
        
                    swap(vec[i], vec[i+1]);
                }
            }
        }
    }
    
    
    void OddEventSort(std::vector<int> &vec){
        
        if(vec.empty() || vec.size() == 1){
        
            return;
        }
    
        bool flag = false;
        while (true){
        
           // flag = false;
            for(int i = 0; i + 1 < vec.size(); i += 2){
        
                if(vec[i] < vec[i+1]){
        
                    swap(vec[i], vec[i+1]);
                    flag = true;
                }
            }
    
    
            for(int i = 1; i + 1 <  vec.size(); i += 2){
        
                if(vec[i] < vec[i+1]){
        
                    swap(vec[i], vec[i+1]);
                    flag = true;
                }
            }
    
    
            if(flag == false){
        
                break;
            }
    
            flag = false;
        }
    }
    int main() {
        
        std::vector<int> vec = {
        1,9,2,8,3,7,4,6,5,10, -1};
        OddEventSort(vec);
        std::cout << vec;
        return 0;
    }

# 算法复杂度分析 #

![在这里插入图片描述][202006191631062.png]

# 参考 #

[经典算法题每日演练——第二十二题 奇偶排序][Link 1]  
[排序算法系列：奇偶排序算法][Link 2]

[20200619161356331.png]: /images/20211209/7212ba0db55c4f93927f7fa04d99da87.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70]: /images/20211209/b458ff8ba0a344e99a29b107afe9a6e4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 1]: /images/20211209/ca9480bb396d493b84bc4381e461b168.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 2]: /images/20211209/0e6372235963494aa364eb1880b5e945.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 3]: /images/20211209/49b886b962a34cf5aa6afe9540b2fca2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 4]: /images/20211209/8a29d65365d049e3a80097800cf7dfd3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3poaXpoZW5nZ3Vhbg_size_16_color_FFFFFF_t_70 5]: /images/20211209/d75831b678a24397bab82a6bca6be905.png
[202006191631062.png]: /images/20211209/2acc80be747247a481a2e63795bd7ca0.png
[Link 1]: https://blog.csdn.net/weixin_33698043/article/details/85608136
[Link 2]: https://blog.csdn.net/lemon_tree12138/article/details/50605563