第一章课后习题1.1

佚名 5年前 (2019-08-27) 算法 1631人围观抢沙发百度已收录

1.1 编写一个程序解决选择问题。令k=N/2.画出表格显示程序对于N种不同的值的运行时间

package com.algorithm.chapterone;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.Random;

import org.junit.Test;

import sun.tools.jar.resources.jar;

/**
 * 编写一个程序解决选择问题。令k=N/2
 * @author Gao·Rongzheng
 *
 */
public class QuestionOne {
    public int[] numbers;
    
    /**
     * 生成范围从1到endNumber的随机数size个，并将其赋值给numbers
     * @param endNumber
     * @param size
     */
    public void creatArray(int endNumber, int size) {
        int[] numberArray = new int[size];
        Random random = new Random();
        
        for (int i=0; i<size; i++) {
            numberArray[i] = random.nextInt(endNumber) + 1;
        }
        
        numbers = numberArray;
    }
    
    /**
     * 冒泡排序算法
     */
    public void sortNumbersOne() {
        long startTime = System.currentTimeMillis();
        for (int m=1; m<numbers.length; m++) {
            for (int n=numbers.length-1; n>m-1; n--) {
                if (numbers[n] > numbers[n-1]) {
                    int temp = numbers[n];
                    numbers[n] = numbers[n-1];
                    numbers[n-1] = temp;
                }
            }
        }
        int k = 0;
        if (numbers.length%2 == 0) {
            k = numbers.length / 2 -1;
        } else {
            k = numbers.length / 2;
        }
        long endTime = System.currentTimeMillis();
        System.out.println("数组中第N/2个最大者： " + (numbers[k]));
        System.out.println("本次算法运行时间为: " + (endTime - startTime) + "ms");
    }
    
    /**
     * 把数组中的前N/2个数放进一个数组，后面的数放进另外一个数组，然后把第一个数组进行排序，依次读出后一个数组的数，把它和第一个数组的第一个数进行比较，符合条件的放入第一个数组把它移动到正确的位置，最后第一个数组的最后一个就是正确答案
     */
    public void sortNumbersTwo() {
        long startTime = System.currentTimeMillis();
        int k = 0;
        if (numbers.length%2 == 0) {
            k = numbers.length / 2 -1;
        } else {
            k = numbers.length / 2;
        }
        
        //※把前k个数放入一个数组，后面的数放入另外一个数组
        int[] result = new int[k+1];
        int[] comparator = new int[numbers.length - k -1];
        for (int i=0; i<numbers.length; i++) {
            if (i <= k) {
                result[i] = numbers[i];
            } else {
                comparator[i-k-1] = numbers[i];
            }
        }
        
        //※对结果数组进行从大到小的冒泡排序
        for (int m=1; m<result.length; m++) {
            for (int n=result.length-1; n>m-1; n--) {
                if (result[n] > result[n-1]) {
                    int temp = result[n];
                    result[n] = result[n-1];
                    result[n-1] = temp;
                }
            }
        }
        
        for (int j=0; j<comparator.length; j++) {
            int compareNumber = comparator[j];
            if (compareNumber > result[k]) {
                result[k] = compareNumber;
                for (int x=k; x>0; x--) {
                    if (result[x] > result[x-1]) {
                        int temp = result[x];
                        result[x] = result[x-1];
                        result[x-1] = temp;
                    } else {
                        break;
                    }
                }
            }
        }
        long endTime = System.currentTimeMillis();
        System.out.println("数组中第N/2个最大者： " + result[k]);
        System.out.println("本次算法运行时间为:  " + (endTime - startTime) + "ms");
    }
    
    @Test
    public void testSort() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        System.out.println("输入数组最大值");
        int endNumber = Integer.valueOf(br.readLine());
        System.out.println("输入数组长度");
        int size = Integer.valueOf(br.readLine());
        creatArray(endNumber, size);
        br.close();
        sortNumbersTwo();
    }
}