Java数据结构与算法之数组排序——奇偶排序

系统管理员 2022-08-09 03:13 222阅读 0赞

直接看代码

/** * 排序数组，用于对数组中的元素进行排序<br> * 采用奇偶排序 */
        /* * 思路： * 它的思路是在数组中重复两趟扫描。 * 第一趟扫描选择所有的数据项对，a[j]和a[j+1]，j是奇数(j=1,3,5,……)。 * 如果它们的关键字的值次序颠倒，就交换它们。 * 第二趟扫描对所有的偶数数据项进行同样的操作（j=2,4,6,……）。 * 重复进行这样两趟 的排序直到数组全部有序 * */
        /* 详解： * 所谓奇偶排序，其核心是遍历+交换 * 遍历：分奇选项和偶选项 * 奇选项遍历是指，以原数组索引值为奇数的选项，作为新的索引值进行遍历，偶选项也是如此； * 比较：相邻两个元素之间进行比较，即a[i]和a[i+1] * 如此循环往复，直到数组全部有序即可 */
        /* * 两种方法： * 区别点在于最后退出循环的判断。 */
        /* * 方法一，最后通过遍历数组，确定都有序后，才通知结束循环 */
        public void oddEvenSortOne()
        {
            //设置一个统计变量，统计遍历次数
            int countSort =0;
            //设置一个标志，用于结束奇偶排序
            boolean isEndFlag = false;
            //由于不清楚循环次数，故选择while循环比较好。
            while(!isEndFlag)
            {
                //因为数组的角标从0开始，故先做偶选项的遍历与比较
                for(int index = 0;index<elementPos-1;index+=2)
                {
                    if(randomArray[index]>randomArray[index+1])
                        swap(index,index+1);
                }
    
                //再做奇选项的遍历和比较
                for(int index = 1;index<elementPos-1;index+=2)
                {
                    if(randomArray[index]>randomArray[index+1])
                        swap(index,index+1);
                }
    
                //判断该数组是否有序
                for(int index=0;index<elementPos-1;index++)
                {
                    if(randomArray[index]>randomArray[index+1])
                        break;
                    else
                    {
                        if(index == elementPos-2)
                            isEndFlag = true;
                    }
                }
    
                countSort++;
            }
    
            System.out.println("奇偶排序执行了"+countSort+"次！");
        }
    
        /* * 方法二，当数据不再有交换的时候，就可以通知退出循环了 * 相比方法一，不需要重新再次遍历一遍，节省时间 */
        public void oddEvenSortTwo()
        {
            //设置一个统计变量，统计遍历次数
            int countSort =0;
            //设置一个标志，用于结束奇偶排序
            boolean isEndFlag = false;
            //由于不清楚循环次数，故选择while循环比较好。
            while(!isEndFlag)
            {
                isEndFlag = true;
                //因为数组的角标从0开始，故先做偶选项的遍历与比较
                for(int index = 0;index<elementPos-1;index+=2)
                {
                    if(randomArray[index]>randomArray[index+1])
                    {
                        swap(index,index+1);
                        isEndFlag = false;//交换发生，不退出循环
                    }
                }
    
                //再做奇选项的遍历和比较
                for(int index = 1;index<elementPos-1;index+=2)
                {
                    if(randomArray[index]>randomArray[index+1])
                    {
                        swap(index,index+1);
                        isEndFlag = false;//交换发生，不退出循环
                    }
                }
    
                countSort++;
            }
    
            System.out.println("奇偶排序执行了"+countSort+"次！");
        }

![奇偶排序的举例][20151008204320306]

[20151008204320306]: /images/20220731/1bf5530ddec347f29b90099b46073642.png