讨论/技术交流/快速排序/

题目:已知线性表按顺序存储,且每个元素都是不相同的整数型元素,设计把所有奇数移动到所有偶数前边的算法(要求时间最少,辅助空间最少)。

  1. 解题思想:本题可以采用基于快速排序的划分思想来设计算法,只需遍历一次即可,其时间复杂度为O(n),空间复杂度为O(1)。假设表为L[1...n],基本思想是:先从前向后找到一个偶数元素L(i),再从后向前找到一个奇数元素L(j),将二者交换;重复上述过程直到i大于j。
  2. 代码实现:
package cn.sun.it.review;

import java.util.Arrays;
import java.util.Scanner;

public class QuickSortUse {

	public static void main(String[] args) {
		System.out.println("请输入若干个整数,以逗号分隔");
		Scanner sc = new Scanner(System.in);
		String strNums = sc.nextLine();
		String[] splitNums = strNums.split(",");
		int[] arr = new int[splitNums.length];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.valueOf(splitNums[i]);
		}
		System.out.println("调整前:" + Arrays.toString(arr));
		fun1(arr);
		System.out.println("调整后:" + Arrays.toString(arr));
	}

	public static void fun1(int[] arr) {
		int i = 0;
		int j = arr.length - 1;
		int temp;
		while (i < j) {
			while (i < j && arr[i] % 2 != 0)
				i++;
			while (i < j && arr[j] % 2 != 1)
				j--;
			if (i < j) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				i++;
				j--;
			}
		}
	}

}
  1. 测试数据及输出结果
请输入若干个整数,以逗号分隔
2,4,6,7,1,3,5,11
调整前:[2, 4, 6, 7, 1, 3, 5, 11]
调整后:[11, 5, 3, 7, 1, 6, 4, 2]

4. 现在有如下问题:如果要在实现上述功能的前提下,分别对奇数部分和偶数部分进行排序,该怎么实现呢?如下:

请输入若干个整数,以逗号分隔
2,4,6,7,1,3,5,11
调整前:[2, 4, 6, 7, 1, 3, 5, 11]
调整后:[1, 3, 5, 7, 11, 2, 4, 6]
  1. 我自己写了一个比较笨拙的方法如下:
package cn.sun.it.review;

import java.util.Arrays;
import java.util.Scanner;

public class QuickSortUse {

	public static void main(String[] args) {
		System.out.println("请输入若干个整数,以逗号分隔");
		Scanner sc = new Scanner(System.in);
		String strNums = sc.nextLine();
		String[] splitNums = strNums.split(",");
		int[] arr = new int[splitNums.length];
		for (int i = 0; i < arr.length; i++) {
			arr[i] = Integer.valueOf(splitNums[i]);
		}
		
		System.out.println("调整前:" + Arrays.toString(arr));
		// 调整
		fun1(arr); 
		
		// 找到调整后,奇数在顺序表中出现的第一个位置
		int n = 0;
		for(int i=0;i<arr.length;i++){  
			if(arr[i]%2!=1){
				n = i;
				break;
			}
		}
		// 创建两个数组,一个存放前半部分的奇数,另一个存放后半部分的偶数
		int[] arr1 = new int[n];
		int[] arr2 = new int[arr.length-n];
		
		for(int i=0;i<arr1.length;i++){
			arr1[i] = arr[i];
		}
		for(int i=0;i<arr2.length;i++){
			arr2[i] = arr[n++];
		}
		// 分别对两个数组进行快速排序
		quickSort(arr1, 0, arr1.length-1);
		quickSort(arr2, 0, arr2.length-1);
		// 合并两个数组
		System.arraycopy(arr1, 0, arr, 0, arr1.length);
        System.arraycopy(arr2, 0, arr, arr1.length, arr2.length);
        // 打印最终结果
		System.out.println("调整后:" + Arrays.toString(arr));
	}

	public static void fun1(int[] arr) {
		int i = 0;
		int j = arr.length - 1;
		int temp;
		while (i < j) {
			while (i < j && arr[i] % 2 != 0)
				i++;
			while (i < j && arr[j] % 2 != 1)
				j--;
			if (i < j) {
				temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
				i++;
				j--;
			}
		}
	}
	
	/**
	 * 
	 * @param arr
	 *            待排序数组
	 * @param low
	 *            递归排序过程中的起始位置
	 * @param high
	 *            递归排序过程中的结束位置
	 */
	private static void quickSort(int[] arr, int low, int high) {
		if(low < high){
			int pivotPos = Partition(arr,low,high);
			quickSort(arr, low, pivotPos-1);
			quickSort(arr, pivotPos+1, high);
		}
	}

	/**
	 * 快速排序的划分操作
	 */
	private static int Partition(int[] arr, int low, int high) {
		int pivot = arr[low];
		while(low < high){
			while(low < high && pivot <= arr[high]){
				high--;
			}
			if(low < high){
				arr[low] = arr[high];
				low++;
			}
			while(low < high && pivot >= arr[low]){
				low++;
			}
			if(low < high){
				arr[high] = arr[low];
				high--;
			}
		}
		arr[low] = pivot;
		return low;
	}

}

6. 结果如下:

请输入若干个整数,以逗号分隔
2,4,6,7,1,3,5,11
调整前:[2, 4, 6, 7, 1, 3, 5, 11]
调整后:[1, 3, 5, 7, 11, 2, 4, 6]

7. 广大网友看看还有没有更好的解决办法,实现 4 中的需求?


1
共 0 个回复
暂无回复