快速排序（java）

快速排序是冒泡排序的优化，是一种非常高效的排序，甚至是目前为止最高效的排序，其思想是这样的：设数组a中存放了n个数据元素，low为数组的低端下标，high为数组的高端下标，从数组a中任取一个元素（通常取a[low]）做为标准元素，以该标准元素调整数组a中其他各个元素的位置，使排在标准元素前面的元素均小于标准元素，排在标准元素后面的均大于或等于标准元素，由此将数组根据标准元素分解成了两个子数组。对这两个子数组中的元素分别再进行方法类同的递归快速排序。算法的递归出口条件是low≥high。

可能讲到这里你不太懂，但是看完步骤之后你一定会懂得。

步骤如下：

1、有一个数据a [ n ]，

2、定义一个低端下标 low 和一个高端下标 high；

3、定义i, j 两个变量；

4、设置条件：如果 low >= high 算法结束，否则进行以下步骤；

5、取数组第一个数作为标准 int standar， j = high, i = low

6、当 i < j 时，从数组最后向前寻找，如果条件满足 i < j（因为可能在找的过程中i 和 j 的值发生了改变） , 并且a[ j ] >= standar， j--

　　不满足时停止，令 a[ i ] = a[ j ]，然后 i 的下标右移 i++；

7、当 i < j 时，从数组开始向后寻找，如果条件满足 i < j（因为可能在找的过程中i 和 j 的值发生了改变） , 并且a[ i ] <= standar， i++

　　不满足时停止，令 a[ j ] = a[ i ]，然后 i 的下标左移 j--；

8、退出整个循环体、令 i 位置的值为standar

9、递归数组的两个子数组

对应代码为：

package quickSort;

public class QuickSort {

    public int[] quicksort(int a[], int low, int high) {

        int i, j;

        if (low >= high) {

            return a;

        } else {

            int standar = a[low];

            i = low;

            j = high;

            while (i < j) {

                while (i < j && a[j] >= standar) {

                    j--;

                }

                if(i < j){

                    a[i] = a[j];

                    i++;

                }

                while (i < j && a[i] < standar) {

                    i++;

                }

                if(i < j){

                    a[j] = a[i];

                    j--;

                }

            }

            a[i] = standar;

            quicksort(a, low, i - 1);

            quicksort(a, i + 1, high);

            return a;

        }

    }

    public int[] sort(int a[], int low, int high) {

        a = quicksort(a, low, high);

        return a;

    }

}

测试类为：

package Test;

import org.omg.CORBA.Current;

import bubbleSort.BubbleSort;

import insertSort.InsertSort;

import quickSort.QuickSort;

import selectSort.SelectSort;

public class Test {

    public static void main(String[] args) {

        QuickSort quickSort = new QuickSort();

        int[] array = createArray();

        long ct1 = System.currentTimeMillis();

        int[] arrays = quickSort.sort(array, 0, array.length - 1);

        long ct2 = System.currentTimeMillis();

        display(arrays);

        System.out.println("所消耗的时间：" + (ct2 - ct1));

    }

    public static void display(int[] arrays) {

        System.out.println("排序后数据：");

        for (int i = 0; i < arrays.length; i++) {

            System.out.print(arrays[i] + "\t");

            if ((i + 1) % 10 == 0) {

                System.out.println();

            }

        }

        System.out.println();

    }

    public static int[] createArray() {

        int[] array = new int[100000];

        System.out.println("数组中元素是：");

        for (int i = 0; i < 100000; i++) {

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

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

            if ((i + 1) % 10 == 0) {

                System.out.println();

            }

        }

        System.out.println();

        return array;

    }

}

时间复杂度：

经过计算：10000个数的排序时间为2 ms， 100000个数的排序时间为 40ms ，比上次测试的冒泡排序14000ms 快了 300多倍。

巴特西

快速排序（java）

最新文章

热门文章