奇偶排序

十大经典排序算法

奇偶排序（Odd–even sort）是和冒泡排序类似的一种排序算法，冒泡排序每次都是和后面的数字比较。而奇偶排序是通过比较相邻的数字对来排序的。首先用奇数位置的数字和他后面挨着的比较，第一轮比较完之后，接着用偶数位置的数字和他后面挨着的比较……，一直重复这样的操作，直到数组有序为止。比如下面图中，第一轮是 [2，5]，[6，3]，[1，8]之间两两比较。第二轮是 [5，3]，[6，1]，[8，4]之间两两比较，接着第三轮，第四轮……，直到完全有序为止。

private void paritySort(int arr[]) {
    boolean complete = false; // 判断是否都排序完成
    int length = arr.length - 1;
    while (!complete) {
        complete = true;
        // 先偶数位比较，下标从 0 开始
        for (int i = 0; i < length; i += 2) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                complete = false;
            }
        }
        // 再奇数位比较
        for (int i = 1; i < length; i = i + 2) {
            if (arr[i] > arr[i + 1]) {
                swap(arr, i, i + 1);
                complete = false;
            }
        }
    }
}

private void swap(int[] nums, int i, int j) {
    int tmp = nums[i];
    nums[i] = nums[j];
    nums[j] = tmp;
}

相关链接