A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© 寻找人生目标 中级黑马   /  2014-5-19 17:38  /  1900 人查看  /  9 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

本帖最后由 寻找人生目标 于 2014-5-22 14:31 编辑

java中的排序算法有哪些呢  哪个的效率较高
请大神解惑


自己找资料总结了下下   

import java.util.Arrays;

/**

*
*
*

*
*
*
*        排序算法了解的有七种分别是
*
*                1.排序算法 插入排序(InsertSort):
*                       
*                        将n个元素的数列分为已有序和无序两个部分,如插入排序过程示例下所示:   
*
*                                 {{a1},{a2,a3,a4,…,an}}   
*
*                                 {{a1⑴,a2⑴},{a3⑴,a4⑴ …,an⑴}}  
*
*                                 {{a1(n-1),a2(n-1) ,…},{an(n-1)}}   
*
*                         每次处理就是将无序数列的第一个元素与有序数列的元素从后往前逐个进行比较,
*
*                         找出插入位置,将该元素插入到有序数列的合适位置中。
*
*                2.排序算法 归并排序(MergeSort):
*
*                        归并操作(merge),也叫归并算法,指的是将两个已经排序的序列合并成一个序列的操作。   
*
*                         如设有数列{6,202,100,301,38,8,1}   
*
*                         初始状态: [6] [202] [100] [301] [38] [8] [1] 比较次数   
*
*                         i=1 [6 202 ] [ 100 301] [ 8 38] [ 1 ] 3   
*
*                         i=2 [ 6 100 202 301 ] [ 1 8 38 ] 4   
*
*                         i=3 [ 1 6 8 38 100 202 301 ] 4
*
*                3.排序算法 快速排序(QuickSort):
*
*                        一趟快速排序的算法是:   
*                                 1)设置两个变量i、j,排序开始的时候:i=0,j=N-1;  
*  
*                                 2)以第一个数组元素作为关键数据,赋值给key,即 key=A[0];
*   
*                                 3)从j开始向前搜索,即由后开始向前搜索(j=j-1即j--),找到第一个小于key的值A[j],A与A[j]交换;   
*
*                                 4)从i开始向后搜索,即由前开始向后搜索(i=i+1即i++),找到第一个大于key的A,A与A[j]交换;   
*
*                                 5)重复第3、4、5步,直到 I=J;(3,4步是在程序中没找到时候j=j-1,i=i+1,直至找到为止。找到并交换的时候i, j指针位置不变。另外当i=j这过程一定正好是i+或j-完成的最后令循环结束。)
*
*                4.排序算法 冒泡排序(BubbleSort):
*
*                        依次比较相邻的两个数,将小数放在前面,大数放在后面。
*
*                         即在第一趟:首先比较第1个和第2个数,将小数放前,大数放后。
*
*                         然后比较第2个数和第3个数,将小数放前,大数放后,如此继续,
*
*                         直至比较最后两个数,将小数放前,大数放后。至此第一趟结束,
*
*                         将最大的数放到了最后。在第二趟:仍从第一对数开始比较
*
*                         (因为可能由于第2个数和第3个数的交换,使得第1个数不再小于第2个数),
*
*                         将小数放前,大数放后,一直比较到倒数第二个数(倒数第一的位置上已经是最大的),
*
*                         第二趟结束,在倒数第二的位置上得到一个新的最大数
*
*                         (其实在整个数列中是第二大的数)。如此下去,重复以上过程,直至最终完成排序。
*
*                5.排序算法 希尔排序(ShellSort):
*
*                        先取一个小于n的整数d1作为第一个增量,
*
*                         把文件的全部记录分成(n除以d1)个组。所有距离为d1的倍数的记录放在同一个组中。
*
*                         先在各组内进行直接插入排序;然后,取第二个增量d2<d1重复上述的分组和排序,
*
*                         直至所取的增量dt=1(dt<dt-l<…<d2<d1),即所有记录放在同一组中进行直接插入排序为止。
*
*                6.排序算法 选择排序(SelectionSort):
*
*                         把第一个元素依次和后面的所有元素进行比较。
*
*                         第一次结束后,就会有最小值出现在最前面。
*
*                         依次类推
*
*
*                 7.排序算法 堆排序(HeapSort):
*
*                         堆排序利用了大根堆(或小根堆)堆顶记录的关键字最大(或最小)这一特征, 使得在当前无序区中选取最大(或最小)关键字的记录变得简单。   
*
*                         (1)用大根堆排序的基本思想   
*
*                                 ① 先将初始文件R[1..n]建成一个大根堆,此堆为初始的无序区   
*
*                             ②再将关键字最大的记录R[1](即堆顶)和无序区的最后一个 记录R[n]交换,由此得到新的无序区R[1..n-1]和有序区R[n],且满足R[1..n-1].keys≤R[n].key   
*
*                                 ③由于交换后新的根R[1]可能违反堆性质,故应将当前无序区R[1..n-1]调整为堆。然后再次将R[1..n-1]中关键字最大的记录R[1]和该区间的最后一个记录R[n-1]交换,
*                                   
*                                    由此得到新的无序区R[1..n-2]和有序区R[n-1..n],
*
*                                    且仍满足关系R[1..n-2].keys≤R[n-1..n].keys,同样要将R[1..n-2]调整为堆。   直到无序区只有一个元素为止。   
*
*                         (2)大根堆排序算法的基本操作:  
*
*                                 ① 初始化操作:将R[1..n]构造为初始堆;   
*
*                                 ②每一趟排序的基本操作:将当前无序区的堆顶记录R[1]和该区间的最后一个记录交换, 然后将新的无序区调整为堆(亦称重建堆)。
*
*/

/**
*
* 选择排序,冒泡排序这两种效率较高,代码量少等。
*
*/
  1. public class Test4 {
  2.        
  3.         public static void main(String[] args) {
  4.                 //定义一个数组
  5.                 int[] arr = { 2, 5, 3, 1, 4 };
  6.                
  7.                 System.out.println("排序前:" + Arrays.toString(arr));
  8.                
  9.                 SelectionSort(arr);
  10.                
  11.                 BubbleSort(arr);
  12.                
  13.                
  14.         }
  15.         //交换数组中的两个元素
  16.         public static void swap(int[] data, int i, int j) {
  17.                                 int temp = data[i];
  18.                                 data[i] = data[j];
  19.                                 data[j] = temp;
  20.                
  21.         }
  22.        
  23.         //选择排序方法
  24.        
  25. public static void SelectionSort(int[] arr) {
  26.                
  27.                 for (int x = 0; x < arr.length - 1; x++) {
  28.                        
  29.                         for (int y = x + 1; y < arr.length; y++) {
  30.                                
  31.                                 if (arr[y] < arr[x]) {
  32.                                         //调用交换数组中两个元素的方法
  33.                                         Test4.swap(arr, x, y);
  34.                                 }
  35.                         }
  36.                 }
  37.                 //打印将数组转换成字符串
  38.                 System.out.println("选择排序后:" + Arrays.toString(arr));
  39.         }


  40.         //冒泡排序方法
  41.        
  42. public static void BubbleSort(int[] arr) {
  43.                
  44.                 for (int i = 0; i < arr.length - 1; i++) {
  45.                        
  46.                         for (int j = 0; j < arr.length - 1 - i; j++) {
  47.                                 //判断相邻的两个数
  48.                                 if (arr[j] > arr[j + 1]) {
  49.                                         //调用交换数组中两个元素的方法
  50.                                         Test4.swap(arr, j, j + 1);
  51.                                 }
  52.                         }
  53.                 }
  54.                 //打印将数组转换成字符串
  55.                 System.out.println("冒泡排序后:" + Arrays.toString(arr));

  56.         }
  57. }
复制代码




评分

参与人数 1技术分 +1 收起 理由
轻语。 + 1

查看全部评分

9 个回复

倒序浏览
都没人回答麽  
回复 使用道具 举报
数据结构学过。。。没好好学。。。不过用得话JAVA中有Arrays.sort()  一般直接调用JAVA这个写好的方法,还高效
回复 使用道具 举报
本帖最后由 杨韬略 于 2014-5-22 16:54 编辑

解答:java的数组排序算法,整型按从小到大的排序可直接调用Arrays.sort();方法,
例子:
        public class Test {

            public static void main(String[] args) {  

                    int a[] ={5,6,2,10,78,69,7,84,69,31,56,45,16,89,56,46,102};   

                         Arrays.sort(a);  //直接按从小到大排序

                          System.out.println(Arrays.binarySearch(a,84));//二分查找法。更加快捷,该方法是Arrays里的   
                        }
               }                                                                                                                                                                                                                                                                                                                                             
回复 使用道具 举报
书上说,当面试的时候,面试官问你什么排序效率最高的时候,不要直接回答快速排序,而是要问你给的是什么数据结构。快速排序的效率跟基准数的选取有关!
回复 使用道具 举报
136616244 发表于 2014-5-22 18:20
书上说,当面试的时候,面试官问你什么排序效率最高的时候,不要直接回答快速排序,而是要问你给的是什么数 ...

啊  这个怎么说   能详细说说麽   
回复 使用道具 举报
都是高手啊
回复 使用道具 举报
又回头看了下感觉排序还是一个较难的问题啊
回复 使用道具 举报
其实优秀的算法有很多根据不同的情况
回复 使用道具 举报
不同情况下适用算法不一样,应该根据实际需求来选择算法
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马