认识达内从这里开始

佛山达内培训的小编在收集到了很多关于Java技术方面的知识和资讯，在这里就相应的分享给大家，关于Java中如何实现排序算法，希望对大家有很大的帮助。下面就一起和佛山达内培训的小编一起看看这些知识和内容吧排序是我们生活中经常会面对的问题。同学们做操时会按照从矮到高排列;老师查看上课出勤情况时，会按学生学号顺序点名;高考录取时，会按成绩总分降序依次录取等。那排序的严格定义是什么呢?

排序的基本概念与分类

对于内排序来说，排序算法的性能主要是受 3 个方面影响:

1.时间性能

排序是数据处理中经常执行的一种操作，往往属于系统的核心部分，因此排序算法的时间开销是衡量其好坏的最重要的标志。在内排序中，主要进行两种操作:比较和移动。比较指关键字之间的比较，这是要做排序最起码的操作。移动指记录从一个位置移动到另一个位置，事实上，移动可以通过改变记录的存储方式来予以避免(这个我们在讲解具体的算法时再谈)。总之，高效率的内排序算法应该是具有尽可能少的关键字比较次数和尽可能少的记录移动次数。

2. 辅助空间

评价排序算法的另一个主要标准是执行算法所需要的辅助存储空间。辅助存储空间是除了存放待排序所占用的存储空间之外，执行算法所需要的其他存储空间。

3. 算法的复杂性

注意这里指的是算法本身的复杂度，而不是指算法的时间复杂度。显然算法过于复杂也会影响排序的性能。

根据排序过程中借助的主要操作，我们把内排序分为:插入排序、交换排序、选择排序和归并排序。可以说，这些都是比较成熟的排序技术，已经被广泛地应用于许许多多的程序语言或数据库当中，甚至它们都已经封装了关于排序算法的实现代码。

因此，我们学习这些排序算法的目的更多并不是为了去在现实中编程排序算法，而是通过学习来提高我们编写算法的能力，以便于去解决更多复杂和灵活的应用性问题。

本章一共要讲解七种排序的算法，按照算法的复杂度分为两大类，冒泡排序 、简单选择排序和直接插入排序属于简单算法，而希尔排序、堆排序、归并排序、快速排序属于改进算法。后面我们将依次讲解。

假设含有 n 个记录的序列为{r1,r2,......,rn}，其相应的关键字分别为{k1,k2,......,kn} ，需确定 1, 2……, n 的一种排列 p1,p2,.......，使其相应的关键字满足 kp1<=kp2<=…… <=kpn (非递减或非递增) 关系，即使得序列成为一个按关键字有序的序列{rp1,rp2,.......,rpn}，这样的操作就称为排序。

1.1排序的稳定性

也正是由于排序不仅是针对主关键字，那么对于次关键字，因为待排序的记录序列中可能存在两个或两个以上的关键字相等的记录，排序结果可能会存在不唯一的情况，我们给出了稳定与不稳定排序的定义。

假设 ki=kj ( 1<=i<=n，1<=j<=n，i≠j) ，且在排序前的序列中 ri领先于 rj (即 i<>

1.2内排序和外排序

根据在排序过程中待排序的记录是否全部被放置在内存中，排序分为:内排序和外排序。

内排序是在排序整个过程中，待排序的所有记录全部被放置在内存中。外排序是由于排序的记录个数太多，不能同时放置在内存，整个排序过程需要在内外存之间多次交换数据才能进行。我们这里主要就介绍内排序的多种方法。

1.3选择排序

选择排序的基本思想是每一趟在n-i+1(i=1,2,…...,n-1)个记录中选取关键字最小的记录作为有序序列的第i个记录。我们这里先介绍的是简单选择排序法。

简单选择排序法 (Simple Selection Sort) 就是通过 n - i 次关键字间的比较，从n-i + 1 个记录中选出关键字最小的记录，并和第 i ( 1 <= i <=n) 个记录交换之。

我们来看代码。

[java] view plain copy

1. /** 简单选择排序 */

2. static int[] bubbleSort0(int[] a) {

3. int min;

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

5. min = i;//将当前下标定义为最小值

6. for (int j = i + 1; j < a.length; j++) {

7. if (a[min] > a[j]) {//如果有小于当前的关键字，将下标赋值给min

8. min = j;

9. }

10. if(min != i){//若min不等于i，则找到最小值，并交换

11. swap(a,min,i);

12. }

13. }

14.

15. }

16. return a;

17. }

简单选择排序复杂度分析

从简单选择排序的过程来看，它最大的特点就是交换移动数据次数相当少， 这样也就节约了相应的时间。分析它的时间复杂度发现，无论最好最差的情况，其比较次数都是一样的多，第 i 趟排序需要进行 n-i 次关键字的比较，此时需要比较n - 1+ n - 2+......... 1=n(n-1)/2次。 而对于交换次教而言，当最好的时候，交换为0次，最差的时候，也就初始降序时，交换次数为 n - 1 次，基于最终的排序时间是比较与交换的次数总和，因此，总的时间复杂度依然为 O(n²) 。

应该说，尽管与冒泡排序同为 O(n²)，但简单选择排序的性能上还是要略优于冒泡排序。

1.4直接插入排序

直接插入排序(Straight Insertion Sort) 的基本操作是将一个记录插入到已经排好序的有序表中，从而得到一个新的、记录数增1的有序表。

顾名思义，从名称上也可以知道它是一种插入排序的方法。我们来看直接插入排序法的代码。

[java] view plain copy

1. /** 插入排序 */

2. static int[] insertSort(int[] a) {

3. int j;// 单独定义，用于记录第二层for循环退出时候的j值

4. for (int i = 1; i < a.length; i++) {

5. if (a[i] < a[i - 1]) {// 如果后一个值比前一个小，则交换

6. int temp = a[i];// 临时变量，存放循环的条件

7. for (j = i - 1; j >= 0 && a[j] > temp; j--) {

8. a[j + 1] = a[j];// 将比temp大的值，依次后移

9. }

10. a[j + 1] = temp;//将跳出循环的后一个记录赋值为temp

11. }

12. }

13. return a;

14. }

直接插入排序复杂度分析

我们来分析一下这个算法，从空间上来看，它只需要一个记录的辅助空间，因此关键是看它的时间复杂度。

当最好的情况，也就是要排序的表本身就是有序的，比如拿到后就是{ 2,3,4,5}时， 那么我们比较次数，其实就是代码中a[i]和a[i-1]比较，共比较了n-1)次，由于每次都是都是a[i-1]< O(n)>

当最坏的情况，即待排序表是逆序的情况，比如 {6,5,4,3,2}，此时需要比较步2+3+......+n =(n+2)(n-1) /2次，而记录的移动次数也达到最大值(n+4)(n-1)/2次。

1.5冒泡排序

冒泡排序 (Bubble Sort) 一种交换排序，它的基本思想是:两两比较相邻记录的关键字，如果反序则交换，直到没有反序的记录为止。冒泡的实现在细节上可以有很多种变化，我们将分别就 3 种不同的冒泡实现代码，来讲解冒泡排序的思想。 这里，我们就先来看看比较容易理解的一段。

[java] view plain copy

1. public class BubbleSort {

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

3. int[] array = { 3, 9, 1, 4, 8, 6, 7, 5, 2, 0 };

4.

5. System.out.println(Arrays.toString(bubbleSort0(array)));

6. }

7.

8. /** 冒泡排序初级版 */

9. static int[] bubbleSort0(int[] a) {

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

11. for (int j = i + 1; j < a.length; j++) {

12. if (a[i] > a[j]) {

13. swap(a, i, j);

14. }

15. }

16. }

17. return a;

18. }

19.

20. /** 交换a数组中的下标为 i 和 j 的值 */

21. static void swap(int[] a, int i, int j) {

22. int temp = a[i];

23. a[i] = a[j];

24. a[j] = temp;

25. }

26. }

这段代码严格意义上说，不算是标准的冒泡排序算法，因为它不满足“两两比较相邻记录"的冒泡排序思想，它更应该是最最简单的交换排序而已。它的思路就是让每一个关键字，都和它后面的每一个关键字比较，如果大则交换，这样第一位置的关键字在一次循环后一定变成最小值。

我们来看看正宗的冒泡算法，有没有什么改进的地方。

[java] view plain copy

1. /** 对数组a进行排序 */

2. static int[] bubbleSort1(int[] a) {

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

4. for (int j = a.length - 2; j >= i; j--) {// j从后往前循环

5. if (a[j] > a[j + 1]) {// 若前一个元素大于后一个元素，则交换

6. swap(a, j, j + 1);// 交换a[j]和a[j+2]的值

7. }

8. }

9. }

10. return a;

11. }

这样的冒泡程序是否还可以优化呢?答案是肯定的。试想一下，如果我们待排序的序列是{2,1,3,4,5,6,7,8,9}，也就是说，除了第一和第二的关键字需要交换外，别的都已经是正常的顺序。当 i=0时，交换了2和1，此时序列已经有序，但是算法仍然不依不饶地将 i=1到8以及每个循环中的j循环都执行了一遍，尽管并没有交换数据，但是之后的大量比较还是大大地多余了。

[java] view plain copy

1. /** 改进后对数组a进行排序 */

2. static int[] bubbleSort2(int[] a) {

3. boolean flag = true; //设置一个标记

4. for (int i = 0; i < a.length - 1 && flag; i++) {//当flag为false时，有序，退出循环

5. flag = false;

6. for (int j = a.length - 2; j >= i; j--) {// j从后往前循环

7. if (a[j] > a[j + 1]) {// 若前一个元素大于后一个元素，则交换

8. swap(a, j, j + 1);// 交换a[j]和a[j+2]的值

9. flag = true;//如果有数据交换，则设置为true，继续循环

10. }

11. }

12. }

13. return a;

14. }

代码改动的关键就是在 i 变量的 for 循环中，增加了对 flag 是否为 true 的判断。经过这样的改进，冒泡排序在性能上就有了一些提升，可以避免因已经有序的情况下的无意义循环判断。

冒泡排序复杂度分析

分析一下它的时间复杂度。当最好的情况，也就是要排序的表本身就是有序的，那么我们比较次数，根据最后改进的代码，可以推断出就是n-1次的比较，没有数据交换，时间复杂度为O(n)。当最坏的情况，即待排序表是逆序的情况，此时需要比较1+2+3+…+ (n-1) =n(n-1)/2次，并作等数量级的记录移动。因此，总的时间复杂度为 O(n²)。

如果排序记录是随机的，那么根据概率相同的原则，平均比较和移动次数约为 n²/4次。因此，我们得出直接插入排序法的时间复杂度为 O(n²) 。 从这里也看出，同样的O(n²)时间复杂度，直接插入排序法比冒泡和简单选择排序的性能要好一些。

看了上面的这些内容之后，我想大家对排序应该有了一定的认识了，大家也可以试着去做一些相应的操作，或者跟着练习，想学一门专业的Java技术，是一个很大的挑战的，你一定要努力的同时还要有耐心，如果想学一门专业的IT技术，欢迎来佛山达内培训机构进行跟更多的了解和咨询。