tcitry
12/15/2014 - 3:51 PM

排序比较

排序比较

package com.company;

import java.util.Scanner;
public class Main {
    public static void main(String[] args) {
        System.out.println("请输入整数,作为数组的大小:");
        Scanner in = new Scanner(System.in);
        int n = in.nextInt();
        int[] arr = new int[n];
        System.out.println("请输入" + n + "个整数");
        for (int i = 0; i < n; i++) {
            arr[i] = in.nextInt();
        }
        int temp = 0;
        long nanotime0 = System.nanoTime();
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
        System.out.println("冒泡排序后的结果是:");
        for (int i = 0; i < arr.length; i++)
            System.out.print(" " + arr[i]);
        System.out.println();
        long nanotime1 = System.nanoTime();
        System.out.println("time:" + (nanotime1 - nanotime0));
        System.out.println();

        long time1 = System.nanoTime();
        int left = arr.length/2;
        int right = arr.length - left;
        quickSort(arr,left,right);
        System.out.println("快速排序的结果为: ");
        for (int b = 0;b<arr.length;b++){
            System.out.print(" "+arr[b]);
        }
        long time2 = System.nanoTime();
        System.out.println("time:"+(time2-time1));
    }
    public static void quickSort(int a[], int left, int right) {
        int i, j, temp;
        i = left;
        j = right;
        if (left > right)
            return;
        temp = a[left];
        while (i != j)/* 找到最终位置 */
        {
            while (a[j] >= temp && j > i)
                j--;
            if (j > i)
                a[i++] = a[j];
            while (a[i] <= temp && j > i)
                i++;
            if (j > i)
                a[j--] = a[i];
        }
        a[i] = temp;
        quickSort(a, left, i - 1);/* 递归左边 */
        quickSort(a, i + 1, right);/* 递归右边 */
    }
}