排序算法的实现及性能分析

排序算法的实现及性能分析

——（java版）

排序是对数据元素序列建立某种有序排列的过程。更确切的说，排序是把一个数据元素序列整理成按关键字递增（或递减）排列的过程。

不过首先，我们必须先解释一下关键字这个词。关键字是要排序的数据元素集合中的一个域，排序是以关键字为基准进行的。而关键字也分为主关键字和次关键字。对于要排序的数据元素集合来说，如果关键字满足数据元素值不同时，该关键字也不同，这样的关键字称为主关键字。不满足主关键字定义的就称为次关键字。

简单来说，排序分为内部排序和外部排序两种。内部排序是把待排序的数据元素全部调入内存中进行的排序。如果数据元素的数量过大，需要分批导入内存，分批导入内存的数据元素排好序后在分批导出到磁盘和磁带外介质上的排序方法称为外部排序。在本篇博客中将只讨论分析内部排序算法的性能。

那么通常比较内部排序算法优劣的标准有如下3个：

<!--[if !supportLists]-->（1）<!--[endif]-->时间复杂度。时间复杂度是衡量排序算法好坏最重要的标准，它是一个函数，定量描述了某个算法的运行时间，时间复杂度通常使用大O符号表述，比如说直接插入排序算法的最差时间复杂度为O(n^2)。

<!--[if !supportLists]-->（2）<!--[endif]-->空间复杂度。空间复杂度用于衡量算法中使用额外内存空间的多少。当排序算法中使用的额外内存空间与要排序数据元素的个数n无关时，其空间复杂度为O(1)，大多数排序算法的空间复杂度都为O(1)。

<!--[if !supportLists]-->（3）<!--[endif]-->稳定性。当使用主关键字排序时，任何排序算法对相同的数据元素序列的排序结果必定是相同的。但使用次关键字排序时，其排序结果有可能相同，也用可能不同。设待排序的数据元素共有n个，设Ki和Kj分表表示第i个数据元素的关键字和第j个数据元素的关键字，设Ri和Rj分别表示第i个数据元素和第j个数据元素。若Ki=Kj，且在排序之前数据元素Ri排在数据元素Rj之前，在排序之后数据元素Ri仍然排在数据元素Rj之前的排序算法称为稳定的排序算法，否则称为不稳定的排序算法。

常见的内部排序算法有以下几种：

<!--[if !supportLists]-->（1）<!--[endif]-->直接插入排序；

<!--[if !supportLists]-->（2）<!--[endif]-->希尔排序；

<!--[if !supportLists]-->（3）<!--[endif]-->直接选择排序；

<!--[if !supportLists]-->（4）<!--[endif]-->堆排序；

<!--[if !supportLists]-->（5）<!--[endif]-->冒泡排序；

<!--[if !supportLists]-->（6）<!--[endif]-->快速排序；

<!--[if !supportLists]-->（7）<!--[endif]-->归并排序；

<!--[if !supportLists]-->（8）<!--[endif]-->基数排序；

直接插入排序

基本思想：顺序地将待排序的数据元素按其值得大小插入到已排序的数据元素子集合的适当位置。

实现代码：

Java代码  

1. public class InsertSort {  
2.     public int[] insertSort(int[] a){  
3.         int i,j,temp;  
4.         int n = a.length;  
5.         for(i = 0;i < n-1;i++){  
6.             temp = a[i+1];  
7.             j = i;  
8.             while(j > -1  && temp <= a[j]){  
9.                 a[j+1] = a[j];  
10.                 j--;  
11.             }  
12.             a[j+1] = temp;  
13.         }  
14.         return a;  
15.     }  
16. }  

直接插入排序算法的时间复杂度在O(n)和O(n^2)之间，即最好情况下是O(n)，最坏情况下是O(n^2)，其空间复杂度是O(1)，是一种稳定的排序算法。

希尔排序

基本思想：把待排序的数据元素分为若干个小组，对同一组内的数据元素用直接插入排序；小组的个数逐次递减；当完成了所有数据元素都在一个组内的排序后排序过程结束。希尔排序又称为缩小增量排序。

演示效果图：

实现代码：

Java代码  

1. public class ShellSort {  
2.     /** 
3.      * 希尔排序实现方法 
4.      * @param a 需要排序的数组 
5.      * @param d 增量数组 
6.      * @param numOfD 增量数组的长度 
7.      * @return 
8.      */  
9.     public int[] shellSort(int[]a,int[]d,int numOfD){  
10.         int i,j,k,m,span;  
11.         int temp;  
12.         int n = a.length;  
13.           
14.         for(m = 0;m < numOfD;m++){  
15.             span = d[m];  
16.             for(k = 0;k < span;k++){  
17.                 for(i = k;i < n - span;i = i + span){  
18.                     temp = a[i + span];  
19.                     j = i;  
20.                     while(j > -1&&temp <= a[j]){  
21.                         a[j + span] = a[j];  
22.                         j = j - span;  
23.                     }  
24.                     a[j + span] = temp;  
25.                 }  
26.             }  
27.         }  
28.         return a;  
29.     }  
30. }  

希尔排序的时间复杂度是O(n(lbn)^2)，空间复杂度是O(1)，由于希尔排序是按增量分组进行的排序，两个相同的数据元素有可能分在不同的组内，因此希尔排序算法是一种不稳定的排序算法。

直接选择排序

基本思想：从待排序的数据元素集合中选取最小的数据元素并将它与原始数据元素集合中的第一个数据元素交换位置；然后从不包括第一个位置上的数据元素集合中选取最小的数据元素并将它与原始数据元素集合中的第二个数据元素交换位置；如此重复，知道数据元素集合只剩下一个数据元素为止。

动态演示图：

实现代码：

Java代码  

1. public class SelectSort {  
2.     /** 
3.      * 不稳定的直接插入排序算法 
4.      * @param a 待排序数组 
5.      * @return  已排序数组 
6.      */  
7.     public int[] selectSort(int[] a){  
8.         int i,j,min;  
9.         int temp;  
10.         int n = a.length;  
11.           
12.         for(i = 0;i < n - 1;i++){  
13.             min = i;  
14.             //找出无序区中最小元素  
15.             for(j = i + 1;j < n;j++){  
16.                 if(a[j] < a[min]){  
17.                     min = j;  
18.                 }  
19.             }  
20.             //将无序区的最小元素与无序区第一个元素交换位置  
21.             if(min != i){//当最小元素为i时不交换位置  
22.                 temp = a[i];  
23.                 a[i] = a[min];  
24.                 a[min] = temp;  
25.             }  
26.               
27.         }  
28.         return a;  
29.     }  
30.       
31.     public int[] selectSort2(int[] a){  
32.         int i,j,min;  
33.         int temp;  
34.         int n = a.length;  
35.           
36.         for(i = 0;i < n - 1;i++){  
37.             min = i;  
38.             //找出无序区中最小元素  
39.             for(j = i + 1;j < n;j++){  
40.                 if(a[j] < a[min]){  
41.                     min = j;  
42.                 }  
43.             }  
44.             //将无序区的最小元素与无序区第一个元素交换位置  
45.             if(min != i){//当最小元素为i时不交换位置  
46.                 temp = a[min];  
47.                 for(j = min;j > i;j--){  
48.                     a[j] = a[j-1];  
49.                 }  
50.                 a[i] = temp;  
51.             }  
52.               
53.         }  
54.         return a;  
55.     }  
56. }  

直接选择排序算法的时间复杂度是O(n^2),其空间复杂度O(1)，直接选择排序算法是不稳定的排序算法，这是由于每次从无序区下半选出最小元素后，与无序区第一个元素交换而引起的，因为交换可能引起相同的数据元素位置发生变化。如果在选出最小元素后，将它前面的无序记录依次后移，然后再将最小记录放在有序区的后面，这样就能保证排序算法的稳定性

堆排序

在直接选择排序中，放在数组的n个数据元素排成一个线性序列(即线性结构)，要从有n个数据元素的数组中选择出一个最小的数据元素需要比较n-1次，如果能把待排序的数据元素集合构造成一个完全二叉树结构，则每次选择出一个最大(或最小)的数据元素只需比较完全二叉树的高度次，即lbn次。

基本思想：循环执行过程（1）——（3）直到数组为空为止。

<!--[if !supportLists]-->(1)<!--[endif]-->把堆顶a[0]元素(最大元素)和当前最大堆的最后一个元素交换；

<!--[if !supportLists]-->(2)<!--[endif]-->最大堆元素个数减一；

<!--[if !supportLists]-->(3)<!--[endif]-->调节新的堆使之满足最大堆的定义。

动态演示：

实现代码：

Java代码  

1. * 保持最大堆的性质  
2.  * @param a 原始元素序列  
3.  * @param n 数组的长度，即待排序元素的个数  
4.  * @param h 以h为根结点元素下标  
5.  */  
6. public static void createHeap(int[] a,int n,int h){  
7.     int i,j,flag;  
8.     int temp;  
9.     i = h;  
10.     j = 2 * i + 1;  
11.     temp = a[i];  
12.     flag = 0;  
13.     //沿左右孩子较大者重复向下筛选  
14.     while(j < n&&flag != 1){  
15.         //寻找左右孩子结点中的较大者，j为其下标  
16.         if(j < n - 1&&a[j] < a[j+1]){  
17.             j++;  
18.         }  
19.         if(temp > a[j]){  
20.             flag = 1;  
21.         }else{  
22.             a[i] = a[j];  
23.             i = j;  
24.             j = 2 * i + 1;  
25.         }  
26.     }  
27.     a[i] = temp;  
28. }  
29.   
30. public static void initCreateHeap(int[] a){  
31.     int n = a.length;  
32.     for(int i = (n - 1) / 2;i >= 0;i--){  
33.         createHeap(a, n, i);  
34.     }  
35. }  
36.   
37. public static int[] heapSort(int[] a){  
38.     int temp;  
39.     int n = a.length;  
40.     initCreateHeap(a);  
41.     for(int i = n - 1;i > 0;i--){  
42.         temp = a[0];  
43.         a[0] = a[i];  
44.         a[i] = temp;  
45.         createHeap(a, i, 0);  
46.     }  
47.     return a;  
48. }  

推排序算法的时间复杂度是O(nlbn),其空间复杂度是O(1),而且该算法是一种不稳定的排序算法。

冒泡排序

基本思想：设数组a中存放了n个数据元素，循环进行n-1次如下的排序过程：第一次时，依次比较相邻两个数据元素a[i]和a[i+1](i=0,1,2……,n-2)，若为逆序，即a[i]>a[i+1]，则交换两个数据元素，否则不交换，这样数值最大的数据元素将被放置在a[n-1]中。第2次时，循环次数减一，即数据元素个数为n-1，操作方法和第一次的类似，这样整个n个数据元素集合中数值较大的数据元素将放置在a[n-2]中。当第n-1次结束时，整个n个数据元素中较小的数据元素中次小的数据元素将被放置在a[1]中，a[0]中放置了最小的数据元素。

动态演示：

实现代码：

Java代码  

1. public static int[] bubbleSort(int[] a){  
2.         int i,j,flag = 1;  
3.         int temp;  
4.         int n = a.length;  
5.         for(i = 1;i < n&&flag == 1;i++){  
6.             flag = 0;  
7.             for(j = 0;j < n - i;j++){  
8.                 if(a[j] > a[j+1]){  
9.                     flag = 1;  
10.                     temp = a[j];  
11.                     a[j] = a[j+1];  
12.                     a[j+1] = temp;  
13.                 }  
14.             }  
15.         }  
16.         return a;  
17.     }  

冒泡排序算法最好情况的时间复杂度是O(n)，最坏情况下的时间复杂度是O(n^2)，而冒泡排序算法的空间复杂度是O(1)，冒泡排序算法是一种稳定的排序算法。

快速排序

基本思想：设数组a中存放了n个数据元素，low为数组的低端下标，high为数组的高端下标，从数组a中任取一个元素(通常取a[low])作为标准元素，以该标准元素为基准来调整数组a中其他各个元素的位置，使排在标准元素前面的元素均小于标准元素，排在标准元素后面均大于或等于标准元素。这样一次排序过程结束后，一方面将标准元素为中心分为了两个子数组，位于标准元素左边子数组中的元素均小于标准元素，位于标准元素右边子数组中的元素均大于或等于标准元素。对于这两个子数组中的元素分别在进行方法类同的递归快速排序。算法的递归出口条件是low>=high。

动态演示:

实现代码：

Java代码  

1. public static int[] quickSort(int[] a,int low,int high){  
2.         int i,j;  
3.         int temp;  
4.         i = low;  
5.         j = high;  
6.         temp = a[low];  
7.           
8.         while(i < j){  
9.             //在数组右端开始扫描  
10.             while(i < j&&temp <= a[j]){  
11.                 j--;  
12.             }  
13.             if(i < j){  
14.                 a[i] = a[j];  
15.                 i++;  
16.             }  
17.             //在数组左端开始扫描  
18.             while(i < j&&a[i] < temp){  
19.                 i++;  
20.             }  
21.             if(i < j){  
22.                 a[j] = a[i];  
23.                 j--;  
24.             }  
25.         }  
26.         a[i] = temp;  
27.         if(low < i){  
28.             quickSort(a, low, i-1);  
29.         }  
30.         if(i < high){  
31.             quickSort(a, j+1, high);  
32.         }  
33.         return a;  
34.     }  

快速排序的时间复杂度是O(nlbn),空间复杂度为O(lbn),最坏情况下的空间复杂度是O(n)，而且该排序算法是一种不稳定的排序算法。

归并排序

基本思想：设数组a中存放了n个数据元素，初始时我们把它们看成是n个长度为1的有序子数组，然后从第一个子数组开始，把相邻的子树组两两合并，得到n/2个（若n/2为小数则向上取整）长度为2的新的有序子数组（当n为奇数时最后一个新的有序子数组的长度为1）;对这些新的有序子数组在两两归并，如此重复，直到得到一个长度为n的有序数组为止。

动态演示：

实现代码：

Java代码  

1. /** 
2.      * 归并排序的实现 
3.      * @param a 待排序数组 
4.      * @param swap 在排序过程中用于存放数组 
5.      * @param k 第一个有序子数组的长度 
6.      */  
7.     public static void merge(int[] a,int[] swap,int k){  
8.         int n = a.length;  
9.         int m = 0,u1,l2,i,j,u2;  
10.           
11.         int l1 = 0;//是第一个有界数组的下界为0  
12.         while(l1 + k <= n - 1){  
13.             l2 = l1 + k;//计算第二个有序子数组下界  
14.             u1 = l2 - 1;//计算第一个有序子数组上界  
15.             u2 = (l2 + k - 1 <= n - 1)?l2 + k -1:n - 1;//计算第二个有序子数组上界  
16.               
17.             for(i = l1,j = l2;i <= u1&&j <= u2;m++){  
18.                 if(a[i] <= a[j]){  
19.                     swap[m] = a[i];  
20.                     i++;  
21.                 }else{  
22.                     swap[m] = a[j];  
23.                     j++;  
24.                 }  
25.             }  
26.               
27.             //子数组2已归并完毕，将子数组1中剩余的元素存放到数组swap中  
28.             while(i <= u1){  
29.                 swap[m] = a[i];  
30.                 m++;  
31.                 i++;  
32.             }  
33.             //子数组1已归并完毕，将子数组2中剩余的元素存放到数组swap中  
34.             while(j <= u2){  
35.                 swap[m] = a[j];  
36.                 m++;  
37.                 j++;  
38.             }  
39.             l1 = u2 + 1;  
40.         }  
41.         //将原数组中只够一组的数据元素存放在数组swap中  
42.         for(i = l1;i < n;i++,m++){  
43.             swap[m] = a[i];  
44.         }  
45.           
46.     }  
47.       
48.     public static int[] mergeSort(int[] a){  
49.         int i;  
50.         int n = a.length;  
51.         int k = 1;//归并长度从1开始  
52.         int[] swap = new int[n];  
53.           
54.   
55.         while(k < n){  
56.             merge(a,swap,k);  
57.             for(i = 0;i < n;i++){  
58.                 a[i] = swap[i];  
59.             }  
60.             k = 2*k;//归并长度翻倍  
61.         }  
62.         return a;  
63.     }  

对n个元素进行一次二路归并排序时，归并的次数约为lbn，任何一次的二路归并排序元素的比较次数都约为n-1，所以，二路归并排序算法的时间复杂度是O(nlbn)；二路归并排序时使用了n个临时内存空间存放数据元素，所以，二路归并排序算法的空间复杂度是O(n)。二路归并排序算法是一种稳定的排序算法。

基数排序

基数排序也成为桶排序，是一种当待排序数据元素为整数类型时非常高效的排序方法。

基本思想：设待排序的数据元素是m位d进制整数（不足m位的在高位补0），设置n个桶，令其编号分别为0,1,2，…，d-1。首先按最低位(即个位)的数值一次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序手机分配在各桶中的数据元素，这样就形成了数据元素集合的一个新的排列，我们称这样的一次排序过程为一次基数排序；对一次基数排序得到的数据元素序列再按次低位(即十位)的数值一次把各数据元素放到相应的桶中，然后按照桶号从小到大和进入桶中数据元素的先后次序收集分配在各桶中的数据元素；这样的过程重复进行，当完成了第m次基数排序后，就得到了排好序的数据元素序列。

实现代码：

Java代码  

1. /** 
2.      * 基数排序的实现方法 
3.      * @param a 尚未排序的方法 
4.      * @param m 数据元素的最大位数 
5.      * @param d 进制的基数 
6.      * @return 已排好序的数组 
7.      * @throws Exception 抛出异常 
8.      */  
9.     public static int[] radixSort(int[] a,int m,int d) throws Exception{  
10.         int n = a.length;  
11.         int i,j,k,l,power = 1;  
12.         LinQueue[] queue_sort = new LinQueue[d];  
13.           
14.         //创建链式队列数组对象  
15.         for(i = 0;i < d;i++){  
16.             LinQueue queue = new LinQueue();  
17.             queue_sort[i] = queue;  
18.         }  
19.           
20.         //进行m次排序  
21.         for(i = 0;i < m;i++){  
22.             if(i == 0){  
23.                 power = 1;  
24.             }else{  
25.                 power = power * d;  
26.             }  
27.             //一次将n个数据元素按第k为的大小放到相应的队列中  
28.             for(j = 0;j < n;j++){  
29.                 k = a[j]/power - (a[j]/(power * d)) * d;//计算k值  
30.                 queue_sort[k].insert(new Integer(a[j]));//将a[j]存储到队列k中  
31.             }  
32.             //顺序回收各队列中的数据元素到数组a中  
33.             l = 0;  
34.             for(j = 0;j < d;j++){  
35.                 while(queue_sort[j].notEmpty()){  
36.                     a[l] = ((Integer)queue_sort[j].delete()).intValue();  
37.                     l++;  
38.                 }  
39.             }  
40.         }  
41.         return a;  
42.     }  
43.       
44.     //生成100个从零到1000的随机数  
45.     public static int[] random(int[] a){  
46.         for(int i = 0;i < 100;i++){  
47.             a[i] = (int)(Math.random()*1000);  
48.         }  
49.         for(int i = 0;i < 100;i++){  
50.             System.out.print(" a["+i+"]:"+a[i]);  
51.         }  
52.         return a;  
53.     }  

基数排序算法的时间复杂度为O（m*n），该排序算法的空间复杂度是O(n),并且基数排序算法是一种稳定的排序算法。

各排序算法的性能比较