大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 各种排序算法的Java实现

各种排序算法的Java实现

关键词:Java各种排序算法的Java实现  阅读(592) 赞(11)

[摘要]本文主要是对各种排序算法的Java实现的讲解,希望对大家学习各种排序算法的Java实现有所帮助。

  1.package com.sxsexe.study.algorithm;

  2.

  3.public class SortTest {

  4.

  5.    private static final int ARRAY_SEED = 100000;

  6.    private static final int ARRAY_LENGTH = 5;

  7.    private static int[] array = new int[ARRAY_LENGTH];

  8.

  9.    private static void initArray() {

  10.

  11.        for (int i = 0; i < ARRAY_LENGTH; i++) {

  12.            array[i] = (int) (Math.random() * ARRAY_SEED);

  13.        }

  14.    }

  15.

  16.    private static void printArray(boolean before) {

  17.

  18.        String s = null;

  19.        if (before)

  20.            s = "before :";

  21.        else

  22.            s = "after :";

  23.        System.out.print(s);

  24.        for (int i = 0; i < ARRAY_LENGTH; i++) {

  25.            System.out.print(array[i] + " ");

  26.        }

  27.        System.out.println(" ");

  28.    }

  29.

  30.    /**

  31.     * @param args

  32.     */

  33.    public static void main(String[] args) {

  34.

  35.        initArray();

  36.        // printArray(true);

  37.        long startTime = System.currentTimeMillis();

  38.        quickSort(0, ARRAY_LENGTH - 1);

  39.        long endTime = System.currentTimeMillis();

  40.        // printArray(false);

  41.        System.out.println("quick sort length : " + ARRAY_LENGTH + " took " + (endTime - startTime) + "ms");

  42.

  43.        initArray();

  44.        // printArray(true);

  45.        startTime = System.currentTimeMillis();

  46.        insertSort();

  47.        endTime = System.currentTimeMillis();

  48.        // printArray(false);

  49.        System.out.println("insert sort length : " + ARRAY_LENGTH + " took " + (endTime - startTime) + "ms");

  50.

  51.        initArray();

  52.        // printArray(true);

  53.        startTime = System.currentTimeMillis();

  54.        selectSort();

  55.        endTime = System.currentTimeMillis();

  56.        // printArray(false);

  57.        System.out.println("select sort length : " + ARRAY_LENGTH + " took " + (endTime - startTime) + "ms");

  58.

  59.        initArray();

  60.        // printArray(true);

  61.        startTime = System.currentTimeMillis();

  62.        bubbleSort();

  63.        endTime = System.currentTimeMillis();

  64.        // printArray(false);

  65.        System.out.println("bubble sort length : " + ARRAY_LENGTH + " took " + (endTime - startTime) + "ms");

  66.

  67.        initArray();

  68.        // printArray(true);

  69.        startTime = System.currentTimeMillis();

  70.        binarySearchSort();

  71.        endTime = System.currentTimeMillis();

  72.        // printArray(false);

  73.        System.out.println("binarySearchSort sort length : " + ARRAY_LENGTH + " took " + (endTime - startTime) + "ms");

  74.    }

  75.

  76.    private static void quickSort(int left, int right) {

  77.

  78.        int key = array[left];

  79.        int tmp;

  80.        int start = left;

  81.        int end = right;

  82.

  83.        while (left < right) {

  84.

  85.            // 首先从右向左找, 找到一个小于key的值 进行交换 然后准备从左向右找

  86.            if (array[right] >= key) {

  87.                right--;

  88.                continue;

  89.            }

  90.            // 交换

  91.            tmp = array[right];

  92.            array[right] = array[left];

  93.            array[left] = tmp;

  94.

  95.            // 从左向右找 找到一个大于key的值进行交换 然后循环

  96.            if (array[left] <= key) {

  97.                left++;

  98.                continue;

  99.            }

  100.            // 交换

  101.            tmp = array[right];

  102.            array[right] = array[left];

  103.            array[left] = tmp;

  104.        }

  105.        // 以left right为新数组的起点和终点 递归调用

  106.        if (start < left)

  107.            quickSort(start, left);

  108.        if (right < end)

  109.            quickSort(right + 1, end);

  110.

  111.        // System.out.println("quick sort over");

  112.    }

 

  113.

  114.    private static void binarySearchSort() {

  115.

  116.        int i = 1, middle = 0, tmp;

  117.

  118.        for (; i < ARRAY_LENGTH; i++) {

  119.

  120.            int low = 0;

  121.            int high = i - 1;

  122.

  123.            tmp = array[i];

  124.

  125.            while (low <= high) {

  126.                middle = (low + high) / 2;

  127.                if (tmp > array[middle])

  128.                    low = middle + 1;

  129.                else

  130.                    high = middle - 1;

  131.            }

  132.

  133.            for (int k = i; k > middle; k--)

  134.                array[k] = array[k - 1];

  135.            array[low] = tmp;

  136.

  137.        }

  138.    }

  139.

  140.    private static void insertSort() {

  141.

  142.        int i = 1, j, tmp;

  143.

  144.        for (; i < ARRAY_LENGTH; i++) {

  145.            tmp = array[i];

  146.            j = i;

  147.            while (j > 0 && array[j - 1] > tmp) {

  148.                array[j] = array[j - 1];

  149.                j--;

  150.            }

  151.            array[j] = tmp;

  152.        }

  153.    }

  154.

  155.    private static void selectSort() {

  156.

  157.        int i = 0, minValue, tmp;

  158.        int j = i + 1;

  159.

  160.        for (; i < ARRAY_LENGTH - 1; i++) {

  161.            minValue = array[i];

  162.            for (j = i + 1; j < ARRAY_LENGTH; j++) {

  163.                if (array[j] < minValue) {

  164.                    minValue = array[j];

  165.                    tmp = array[j];

  166.                    array[j] = array[i];

  167.                    array[i] = tmp;

  168.                }

  169.            }

  170.        }

  171.    }

  172.

  173.    private static void bubbleSort() {

  174.

  175.        int i = 0;

  176.        int j, tmp;

  177.

  178.        for (; i < ARRAY_LENGTH; i++) {

  179.            for (j = i + 1; j < ARRAY_LENGTH; j++) {

  180.                if (array[j] < array[i]) {

  181.                    tmp = array[j];

  182.                    array[j] = array[i];

  183.                    array[i] = tmp;

  184.                }

  185.            }

  186.        }

  187.    }

  188.

  189.}



相关评论