黑马程序员技术交流社区

标题: JAVA中的排序算法 [打印本页]

作者: 寻找人生目标 时间: 2014-5-19 17:38
标题: JAVA中的排序算法
本帖最后由寻找人生目标于 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]和该区间的最后一个记录交换，然后将新的无序区调整为堆（亦称重建堆）。
*
*/

/**
*
* 选择排序，冒泡排序这两种效率较高,代码量少等。
*
*/

public class Test4 {

public static void main(String[] args) {

//定义一个数组

int[] arr = { 2, 5, 3, 1, 4 };

System.out.println("排序前：" + Arrays.toString(arr));

SelectionSort(arr);

BubbleSort(arr);

}

//交换数组中的两个元素

public static void swap(int[] data, int i, int j) {

int temp = data[i];

data[i] = data[j];

data[j] = temp;

}

//选择排序方法

public static void SelectionSort(int[] arr) {

for (int x = 0; x < arr.length - 1; x++) {

for (int y = x + 1; y < arr.length; y++) {

if (arr[y] < arr[x]) {

//调用交换数组中两个元素的方法

Test4.swap(arr, x, y);

}

}

}

//打印将数组转换成字符串

System.out.println("选择排序后：" + Arrays.toString(arr));

}

//冒泡排序方法

public static void BubbleSort(int[] arr) {

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]) {

//调用交换数组中两个元素的方法

Test4.swap(arr, j, j + 1);

}

}

}

//打印将数组转换成字符串

System.out.println("冒泡排序后：" + Arrays.toString(arr));

}

}

复制代码

作者: 寻找人生目标 时间: 2014-5-22 14:27
都没人回答麽
作者: never615 时间: 2014-5-22 16:10
数据结构学过。。。没好好学。。。不过用得话JAVA中有Arrays.sort()  一般直接调用JAVA这个写好的方法，还高效
作者: 杨韬略 时间: 2014-5-22 16:51
本帖最后由杨韬略于 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
书上说，当面试的时候，面试官问你什么排序效率最高的时候，不要直接回答快速排序，而是要问你给的是什么数据结构。快速排序的效率跟基准数的选取有关！

作者: 寻找人生目标 时间: 2014-5-23 23:44

136616244 发表于 2014-5-22 18:20
书上说，当面试的时候，面试官问你什么排序效率最高的时候，不要直接回答快速排序，而是要问你给的是什么数 ...

啊  这个怎么说能详细说说麽
作者: java木 时间: 2014-5-23 23:55
都是高手啊
作者: 何堂红 时间: 2014-6-16 23:20
又回头看了下感觉排序还是一个较难的问题啊
作者: laibin2 时间: 2014-6-17 01:17
其实优秀的算法有很多根据不同的情况
作者: 夕默 时间: 2014-9-14 11:48
不同情况下适用算法不一样，应该根据实际需求来选择算法

欢迎光临黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2