想了解一下JAVA有几种排序？尽可能详细些！请提供代码！谢谢！

xieqian_ssmc 2008-02-18 03:56:13

华为面试时，最爱考这个！！！

...全文

1607 28 打赏收藏转发到动态举报

写回复

用AI写文章

28 条回复

切换为时间正序

请发表友善的回复…

发表回复

youjianbo_han_87 2008-07-18

打赏
举报

赶紧结贴散分

youjianbo_han_87 2008-07-18

打赏
举报

楼主，你这个都不会，你还去华为面试？搞笑

zwziyl 2008-07-18

打赏
举报

继续膜拜

zwziyl 2008-07-18

打赏
举报

膜拜ing

Dan1980 2008-02-19

打赏
举报

深秋小雨的笔记对学习排序原理来说不错。
不过，实际应用中用Java提供的api就可以了，api是开发人员反复测试和用户长期体验的结果，其效率和可靠性都是信得过的。
对一般Java程序员来说，用好Comparable接口和Comparator类就足够了，没必要自己去写排序算法。

kcseason 2008-02-19

打赏
举报

学习学习 ...

codeartisan 2008-02-19

打赏
举报

快速排序3：(仍然用三数据项取中法选择枢纽，用插入排序法代替了原来的手动排序法。)

import java.util.Random;

class QuickSort3{

    private int[] source;

    public QuickSort3(int[] source){

        this.source = source;

    }

    public void sort(){

        recQuickSort(0,source.length-1);

    }

    private void recQuickSort(int left, int right){

        int size = right - left + 1;

        if (size < 10){//当子数组长度为9时使用插入排序

            insertionSort(left, right);

        } else {

            int median = medianOf3(left, right);

            int partition = partition(left, right, median);

            recQuickSort(left, partition - 1);

            recQuickSort(partition + 1, right);

        }

    }

    private int medianOf3(int left, int right){

        int center = (left + right) / 2;

        if (source[left] > source[center])

            swap(left, center);

        if (source[left] > source[right])

            swap(left, right);

        if (source[center] > source[right])

            swap(center, right);

        swap(center, right-1);

        return source[right-1];

    }

    private int partition(int left, int right, int pivot){

        int leftPtr = left;

        int rightPtr = right - 1;

        while (true){

            while (source[++leftPtr] < pivot);

            while (source[--rightPtr] > pivot);

            if (leftPtr > rightPtr){

                break;

            } else {

                swap(leftPtr, rightPtr);

            }

        }

        swap(leftPtr, right - 1);

        return leftPtr;

    }

    private void swap(int idx1, int idx2){

        int temp = source[idx1];

        source[idx1] = source[idx2];

        source[idx2] = temp;

    }

    private void insertionSort(int left, int right){//插入排序法

        int temp;

        for (int i=left+1; i<right+1; i++){

            int j;

            temp = source[i];

            for (j=i-1; j>-1; j--){

                if (temp < source[j])

                    source[j] = source[j+1];

                else

                    break;

            }

        }

    }

    public static void main(String args[]){

        int[] source = new int[10000];

        QuickSort3 qs3;

        Random random = new Random();

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

            source[i] = random.nextInt(10000);

        }

        qs3 = new QuickSort3(source);

        long s = System.currentTimeMillis();

        qs3.sort();

        long e = System.currentTimeMillis();

        for (int i: source){

            System.out.print(i+",");

        }

        System.out.println("耗时："+(e-s)/1000.0+"秒");

    }

}

10次对长度为10^6的数组进行排序：
耗时：0.157秒
耗时：0.172秒
耗时：0.156秒
耗时：0.156秒
耗时：0.157秒
耗时：0.172秒
耗时：0.156秒
耗时：0.172秒
耗时：0.172秒
耗时：0.156秒

引用书上作者的话：===================================================================
如果使用三数据项取中划分方法，则必须要遵循快速排序算法不能执行三个或者少于三个数据项的划分的规则。在这种情况下，数字3被称为切割点(cutoff)。在第2个例子中，是用一段代码手动地对两个或三个数据项的子数组来排序的。这并不是最好的方法。
处理小划分的另一个选择是使用插入排序。当使用插入排序的时候，不用限制以3为切割点。可以把界限定为10、20或者其他任何数。试验不同切割点的值以找到最好的执行效率，这件事是很有意义的。Knuth推荐使用9作为切割点。但是，最好的选择值取决于计算机、操作系统、编译器等。上面这个例子(第3个例子)使用插入排序来处理小于10个数据项(即长度为9)的子数组。

在第3个例子中，对小的子数组使用插入排序被证实为最快的一种方法，但是它不比在第2个例子中对三个或者更少的数据项的子数组手动地排序快。比较和复制的次数在快速排序阶段都大大地减少了，但是在插入排序阶段却又上升了差不多相同的次数，因此并没有明显地节省时间。但是，要想把快速排序的性能发挥到极限，这个方法大概还是有用的。

另一个选择是对数组整个使用快速排序，不去考虑小于界限的划分的排序。如果使用这种做法，那么应该从recQuickSort()中删除对方法insertionSort()的调用。当快速排序结束时，数组已经是基本有序的了。然后可以对整个数组应用插入排序。插入排序对基本有序的数组执行效率很高，而且很多专家都提倡使用这个方法，但是在我们的设置中，这个方法运行得很慢。插入排序显然更合适做很多小规模的排序，而不是一个大的排序。
===================================================================
以下是改动了第3个例子后运行的结果，看起来要比第3个例子慢，甚至比第2个例子慢。
耗时：0.187秒
耗时：0.187秒
耗时：0.187秒
耗时：0.187秒
耗时：0.188秒
耗时：0.172秒
耗时：0.188秒
耗时：0.187秒
耗时：0.188秒
耗时：0.187秒

当时看的这本书叫《Java数据结构和算法》，中国电力出版社的。

codeartisan 2008-02-19

打赏
举报

快速排序的基本思想是在一个数组中取一个值做为标准，这个标准被称作枢纽，把小于枢纽的值放在一边，把大于枢纽的值放到另一边，再把枢纽插入到这两边之间的位置，这种“分边”的算法被叫做划分算法。利用递归(可以用循环来消除递归)多次调用划分算法分别对枢纽两边的数组进行同样的操作，最终达到排序目的的算法叫快速排序算法。

下面是我自己写的3种快速排序算法的例子，第4种没有写出来，因为只要稍微改一下第3种就变成第4种了，没必要再写那么多代码占版面。

快速排序1：(选择子数组的最右端为枢纽，用划分算法进行快速排序。)

class QuickSort{

    private int[] source;

    public QuickSort(int[] source){

        this.source = source;

    }

    public void sort(){

        recQuickSort(0,source.length-1);

    }

    private void recQuickSort(int left, int right){

        if (left >= right){

            return;

        } else {

            int pivot = source[right];//选择子数组的最右端为枢纽

            int partition = partition(left, right, pivot);

            recQuickSort(left, partition-1);

            recQuickSort(partition+1, right);

        }

    }

    private int partition(int left, int right, int pivot){//划分算法

        int leftIdx = left - 1;

        int rightIdx = right ;

        while (true){

            while (source[++leftIdx] < pivot);

            while (rightIdx > 0 && source[--rightIdx] >= pivot);

            if(leftIdx < rightIdx){

                swap(leftIdx, rightIdx);

            } else {

                break;

            }

        }

        swap(leftIdx, right);

        return leftIdx;

    }

    private void swap(int idx1, int idx2){

        int temp = source[idx1];

        source[idx1] = source[idx2];

        source[idx2] = temp;

    }

    

    public static void main(String[] args){

        int[] n = new int[6046];    //超过6046溢出

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

            n[i] = 6046-i;

        }

        QuickSort qs = new QuickSort(n);

        qs.sort();

        for (int i: n){

            System.out.print(i+",");

        }

    }

}

快速排序2：(用三数据项取中法选择枢纽，用手动排序为长度为3或3以下的子数组进行排序。)

import java.util.Random;

class QuickSort2{

    private int[] source;

    public QuickSort2(int[] source){

        this.source = source;

    }

    public void sort(){

        recQuickSort(0,source.length-1);

    }

    private void recQuickSort(int left, int right){

        int size = right - left + 1;

        if (size <= 3){

            manualSort(left, right);

        } else {

            int median = medianOf3(left, right);

            int partition = partition(left, right, median);

            recQuickSort(left, partition - 1);

            recQuickSort(partition + 1, right);

        }

    }

    private int medianOf3(int left, int right){//用三数据项取中法选择枢纽

        int center = (left + right) / 2;

        if (source[left] > source[center])

            swap(left, center);

        if (source[left] > source[right])

            swap(left, right);

        if (source[center] > source[right])

            swap(center, right);

        swap(center, right-1);

        return source[right-1];

    }

    private int partition(int left, int right, int pivot){

        int leftPtr = left;

        int rightPtr = right - 1;

        while (true){

            while (source[++leftPtr] < pivot);

            while (source[--rightPtr] > pivot);//这里不能加等号，否则数组索引有可能越界。

            if (leftPtr > rightPtr){

                break;

            } else {

                swap(leftPtr, rightPtr);

            }

        }

        swap(leftPtr, right - 1);

        return leftPtr;

    }

    private void swap(int idx1, int idx2){

        int temp = source[idx1];

        source[idx1] = source[idx2];

        source[idx2] = temp;

    }

    private void manualSort(int left, int right){//用手动排序为长度为3或3以下的子数组进行排序

        int size = right - left + 1;

        switch (size){

            case 2:

                if (source[left] > source[right])

                    swap (left, right);

                break;

            case 3:

                if (source[left] > source[left + 1])

                    swap(left, left + 1); 

                if (source[left] > source[right])

                    swap(left, right);

                if (source[left + 1] > source[right])

                    swap(left + 1, right);

                break;

        }

    }

    public static void main(String args[]){

        int[] source = new int[10000];

        QuickSort2 qs2;

        Random random = new Random();

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

            source[i] = random.nextInt(source.length);

        }

        qs2 = new QuickSort2(source);

        long s = System.currentTimeMillis();

        qs2.sort();

        long e = System.currentTimeMillis();

        for (int i: source){

            System.out.print(i+",");

        }

        System.out.println("耗时："+(e-s)/1000.0+"秒");

    }

}

10次对长度为10^6的数组进行排序：
耗时：0.188秒
耗时：0.172秒
耗时：0.172秒
耗时：0.187秒
耗时：0.172秒
耗时：0.172秒
耗时：0.188秒
耗时：0.172秒
耗时：0.188秒
耗时：0.171秒

codeartisan 2008-02-19

打赏
举报

Ant_Yan插队哈，这里接9楼 :)

对于这里的“间隔”设置的说明，我从书上摘抄下来：

在希尔（人名）的原稿中，他建议初始的间距为N/2，简单地把每一趟排序分成了两半。因些，对于N=100的数组逐渐减小的间隔序列为：50，25，12，6，3，1。这个方法的好处是不需要在开始排序前为找到初始的间隔而计算序列；而只需要用2整除N。但是，这被证明并不是最好的数列。尽管对于大多数的数据来说这个方法还是比插入排序效果好，但是这种方法有时会使运行时间降到O(N^2)，这并不比插入排序的效率更高。
这个方法的一个变形是用2.2而非2来整除每一个间隔。对于n=100的数组来说，会产生序列45，20，9，4，1。这比用2整除显著改善了效果，因为这样避免了某些导致时间复杂度为O(N^2)的最坏情况的发生。不论N为何值，都需要一些额外的代码来保证序列的最后取值为1。
间隔序列中的数字互质通常被认为很重要：也就是说，除了1之外它们没有公约数。这个约束条件使每一趟排序更有可能保持前一趟排序已经排好的效果。希尔最初以N/2为间隔的低效性就是归咎于它没有遵守这个准则。
或许还可以设计出像如上讲述的间隔序列一样好的（甚至更好的）间隔序列。但是不管这个间隔序列是什么，都应该能够快速地计算，而不会降低算法的执行速度。

Ant 2008-02-19

打赏
举报



package sort;



public class SortDemo {

	public static void main(String args[]){

		int[] bigArr = new int[100000];

		

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

			bigArr[i] = (int)(Math.random()*400000);

		

		Sort.insertSort(bigArr, 100000);

		//Sort.quickSort(0,99999,bigArr);

		

		//display result, optional

		//for(int i=0;i<bigArr.length;i++)

		//	System.out.print(bigArr[i]+",");

		System.out.println("Done");

	}

}



class Sort{

	public static void swap(int x,int y,int[] target){

		int temp = target[x];

		target[x] = target[y];

		target[y] = temp;

	}

	

	public static void insertSort(int[] target,int length){

		for(int i=1;i<length;i++)

			for(int j=i;j>0&&target[j-1]>target[j];j--)

				swap(j-1,j,target);

	}

	

	public static void quickSort(int low, int high, int[] target){

		if(high<=low)

			return;

		int temp = target[low];

		int i = low, j=high+1;

		while(true){

			do{

				i++;

			}while(i<=high&&target[i]<temp);

		

			do{

				j--;

			}while(target[j]>temp);

		

			if(i>j)

				break;

			swap(i,j,target);

		}

		swap(low,j,target);

		quickSort(low,j-1,target);

		quickSort(j+1,high,target);

	}

}

这是笔者曾经写过的一个老例子了，弄了10万个随机数来测试，插入排序比快速排序确实要慢很多。lz可以自己跑一跑这个例子，其实排序的算法有很多，基本都是在不断的优化比较和移动数组元素的次数来提高效率，把握这个才是掌握排序算法的最核心的本质。

至于名字是快速排序，希尔排序，插入排序，冒泡排序，归并排序，选择排序，堆排序，都是各自有自己比较元素和移动元素的此略不同而适应不同的场景。好好学习数据结构就能搞明白了，排序是数据结构中数组这块必须用心体会的……

codeartisan 2008-02-19

打赏
举报

因为是学习笔记，写给自己看的，方便复习，可能表达得不是很好，将就着看吧

希尔排序是插入排序法的改进。
插入排序在最不理想的情况下的效率和选择排序一样，当对一个需要将它排到最左端的元素进行排序的时候，将会移动很多个元素，而希尔排序算法通过加大插入排序中元素之间的间隔，并在这些有间隔的元素中进行插入排序，从而使数据项能够大跨度地移动。当这些数据项排过一趟序后，希尔排序算法减小数据项的间隔再进行排序，这时，因为经过之前的排序，数组已经是“基本有序”的了，减少间隔后再排序，数组越来越有序，最后所有元素的位置与它最终位置的距离非常小（也就是说这时再用插入排序法对其排序需要移动的元素是很少的），这时间隔已经减小到了1，也就是原始的插入排序法了。希尔排序算法大大减小了插入排序的时间复杂度。

下面是我自己写的一个用希尔算法实现的排序代码：

import java.util.Random; 

class Shell{ 

    public void sort(int[] source){ 

        int h = 1; 

        int temp; 

        while (h*3+1<source.length+1){ 

            h = h*3+1; 

        } 

        while (h != 0){ 

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

                for (int j=i; j<source.length-h; j+=h){ 

                    temp = source[j+h]; 

                    int k; 

                    for (k=j; k>i-h; k-=h){ 

                        if (temp<source[k]){ 

                            source[k+h] = source[k]; 

                        } else { 

                            break; 

                        } 

                    } 

                    source[k+h] = temp; 

                } 

            } 

            h = (h-1)/3; 

        } 

    } 

    public static void main(String[] args){ 

        Shell shell = new Shell(); 

        Random random = new Random(); 

        int[] test = new int[10000]; 

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

            test[i] = random.nextInt(10000); 

        } 

        for(int i : test){ 

            System.out.print(i+","); 

        } 

        System.out.println(); 

        long s = System.currentTimeMillis(); 

        shell.sort(test); 

        long e = System.currentTimeMillis(); 

        for(int i : test){ 

            System.out.print(i+","); 

        } 

        System.out.println("\n"+(e-s)/1000.0+"秒"); 

    } 

}

执行结果是0.0秒。
我把数组扩大10倍，结果是0.031秒，比插入排序快得太多了。
对1000000长度的数组排序，平均时间是0.595秒。

codeartisan 2008-02-19

打赏
举报

学数据结构时候做的学习笔记：

奇偶排序的思路是在数组中重复两趟扫描。第一趟扫描所有的数据项对，a[j]和a[j+1]，j是奇数(j = 1,3,5……)。如果它们的关键字的次序颠倒，就交换它们。第二趟扫描所有的偶数数据项进行同样的操作(j = 2,4,6……)。重复进行这样的两趟的排序直到数组全部有序。

自己写了个实现奇偶排序的方法如下：

import java.util.Random; 

public class JoSort { 

     

    public void sort(int[] n){ 

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

            for (int j = 0; j < n.length - 1; j += 2){ 

                if (n[j] > n[j + 1]){ 

                    n[j] = n[j + 1] + n[j]; 

                    n[j + 1] = n[j] - n[j + 1]; 

                    n[j] = n[j] - n[j + 1]; 

                } 

            } 

            for (int j = 1; j < n.length - 1; j += 2){ 

                if (n[j] > n[j + 1]){ 

                    n[j] = n[j + 1] + n[j]; 

                    n[j + 1] = n[j] - n[j + 1]; 

                    n[j] = n[j] - n[j + 1]; 

                } 

            } 

        } 

    } 

     

    public static void main(String[] args){ 

         

        int[] n = new int[10000]; 

        Random r = new Random(); 

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

            n[i] = r.nextInt(10000); 

        } 

        JoSort js = new JoSort(); 

        long s = System.currentTimeMillis(); 

        js.sort(n); 

        long e = System.currentTimeMillis(); 

        for (int i = 0; i < n.length - 1; i++){ 

            System.out.print(n[i]+","); 

        } 

        System.out.println(n[n.length-1]); 

        System.out.println("奇偶排序耗时："+(e - s) / 1000.0 + "秒"); 

         

    } 

     

}

p.s：当数组长度为奇数时，用奇偶排序算法对其进行排序最后会多进行n/2-1次的比较。

在AMD 速龙 3800+，1G内存，JDK6.0的运行环境下耗时0.39秒左右。与冒泡排序法的效率差不多，看不出有什么好处。

但书上说：“奇偶排序实际上在多处理器环境中很有用，处理器可以分别同时处理每一个奇数对，然后又同时处理偶数对。因为奇数对是彼此独立的，每一对都可以用不同的处理器比较和交换。这样可以非常快速的排序。”