文档版本 | 开发工具 | 测试平台 | 工程名字 | 日期 | 作者 | 备注 |
---|---|---|---|---|---|---|
V1.0 | 2016.04.06 | lutianfei | none | |||
V1.1 | 2016.07.16 | lutianfei | 增加了归并排序说明 | |||
V2.0 | 2016.07.19 | lutianfei | 完善了排序算法的总结 |
排序方法 | 平均情况 | 最好情况 | 最坏情况 | 辅助空间 | 稳定性 |
---|---|---|---|---|---|
冒泡排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
简单选择排序 | O(n^2) | O(n^2) | O(n^2) | O(1) | 稳定 |
直接插入排序 | O(n^2) | O(n) | O(n^2) | O(1) | 稳定 |
希尔排序 | O(nlogn)~O(n^2) | O(n^1.3) | O(n^2) | O(1) | 不稳定 |
堆排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(1) | 不稳定 |
归并排序 | O(nlogn) | O(nlogn) | O(nlogn) | O(n) | 稳定 |
快速排序 | O(nlogn) | O(nlogn) | O(n^2) | O(logn)~O(n) | 不稳定 |
public static void main(String[] args) { int[] A = new int[] { 11, 2, 3, 22, 4, 1, 11, 10, 6, 5, 22, 13, 21 }; int n = A.length; int[] A_sort = new int[n]; System.out.println("排序前:"); arrayPrint(A); System.out.println("排序后:"); mSort(A,A_sort,0, n-1); // System.out.println(A); arrayPrint(A_sort); System.out.println("标准答案"); Arrays.sort(A); arrayPrint(A); } /** * * <p>@MethodName : arrayPrint</p> * <p>@Description: 打印数组至控制台</p> * @date : 2016-7-6 ,下午4:51:43 * @param : @param 待打印数组A * @Version : v1.0 */ public static void arrayPrint(int[] A) { System.out.print("[ "); for (int i = 0; i < A.length; i++) { System.out.print(A[i] + " "); } System.out.println("]"); System.out.println(); }
/** * * <p>@MethodName : bubbleSort0</p> * <p>@Description: 初级版冒泡排序</p> * @date : 2016年7月19日 ,上午10:10:53 * @param : @param A * @Version : vx.x */public static void bubbleSort0(int[] A){ for(int i=0;i < A.length-1;i++){ for(int j=i+1;j<A.length;j++){ if(A[i] > A[j]){ swap(A,i,j); } } }}
/** * * <p>@MethodName : buubleSort1</p> * <p>@Description: 优化版冒泡排序算法</p> * @date : 2016年7月19日 ,上午10:57:17 * @param : @param A 带排序数组 * @Version : vx.x */public static void bubbleSort1(int[] A){ for(int i = 0;i<A.length;i++){ for(int j=A.length-1;j>i;j--){ //j从后往前循环 if(A[j-1] > A[j]){ //从下往上依次比较 swap(A,j-1,j); } } }}
上述的优化冒泡排序算法的问题在于如果数据在中间已经排序好,后续的比较工作还会继续进行,造成时间浪费。进一步优化就是增加一个flag,标志是否需要继续比较。
/** * * <p>@MethodName : bubbleSort2</p> * <p>@Description: 进一步优化版冒泡排序算法</p> * @date : 2016年7月19日 ,上午11:26:36 * @param : @param A * @Version : vx.x */public static void bubbleSort2(int [] A){ boolean flag = true; for(int i=0; i<A.length && flag;i++){ flag = false; for(int j=A.length-1;j>i;j--){ if(A[j-1] > A[j]){ swap(A,j-1,j); flag = true; } } }}
n-i
次关键字间的比较,从n-i+1个记录中选出关键字最小的记录,并和第i(1<=i<=n)个记录交换之。/** * * <p>@MethodName : selectSort</p> * <p>@Description: 简单选择排序</p> * @date : 2016年7月19日 ,上午11:48:40 * @param : @param A * @Version : vx.x */public static void selectSort(int[] A){ for(int i=0;i<A.length-1;i++){ int min = i; for(int j=i+1;j<A.length;j++){ if(A[min] > A[j]){ min = j; } } if(i != min){ swap(A,i,min); } }}
简单排序最大的特点:交换移动数据次数相当少,最好情况下交换0次,最差请求交换n-1次;适用于数组个数不多,但每个数组元素较大的情况。
时间复杂度:无论是最好最差情况,比较次数一样多,n(n-1)/2,总的时间复杂度O(n^2)
简单选择排序性能上略优于冒泡排序。
/** * * <p>@MethodName : insertSort</p> * <p>@Description: 直接插入排序</p> * @date : 2016年7月19日 ,下午3:05:31 * @param : @param A * @Version : vx.x */public static void insertSort(int[] A){ for(int i=1;i<A.length;i++){ //从1开始表示:假设A[0] 已经放好位置了,后面的数字就是插入到它左边还是右边的问题。 if(A[i] < A[i-1]){ //发现A[i]比前面的有序数组的最后一个数小了 int tmp = A[i];//缓存下A[i] int j; for(j=i-1; j>=0 && A[j] > tmp; j--){ //从后往前逐个排查哪个位置刚好适合A[i],最后一次j--可能会为负值,这是为了配合后面A[j+1] A[j+1] = A[j]; } A[j+1] = tmp; } }}
/** * * <p>@MethodName : shellSort</p> * <p>@Description: 希尔排序算法</p> * @date : 2016年7月19日 ,下午4:06:41 * @param : @param A * @Version : vx.x */public static void shellSort(int[] A){ int inc = A.length; //希尔排序可以理解为将一个大数组按照间隔inc分为inc个小数组 //每个数组按照直接插入排序进行处理 do{ inc = inc/4 + 1; for(int i=inc;i<A.length;i++){ if(A[i] < A[i-inc]){ int tmp = A[i]; int j=0; for(j=i-inc;j>=0 && tmp < A[j]; j-=inc){ A[j+inc] = A[j]; } A[j+inc] = tmp; } } } while(inc>1);}
大堆顶
格式的完全二叉树
进行排序。以下两步循环n-1次后,可完成排序。
根节点
与最后一个节点
交换位置。注:大堆顶完全二叉树数学定义
/** * * <p>@MethodName : heapSort</p> * <p>@Description: 堆排序函数</p> * @date : 2016年7月19日 ,下午5:29:24 * @param : @param A * @param : @param n * @Version : vx.x */public static void heapSort(int[] A,int n){ for(int i=(n-1)/2 ;i>=0;i--){ //循环从最后一个拥有子节点的节点(A[(n-1)/2])处开始,这样循环可以实现从下到上,从左到右将较大数向上推,最终实现大顶堆。 //循环到0结束因为根节点0,也有两个子节点要比较。 heapAdjust(A,i,n-1); } for(int i=n-1;i>0;i--){ //循环从n-1开始,因为每次要交换根节点A[0],与最后一个节点A[i-1] //循环到1结束,因为此时A[0],A[1]大小已知 swap(A,0,i); heapAdjust(A,0,i-1); }}/** * * <p>@MethodName : heapAdjust</p> * <p>@Description: 进行大顶堆排序</p> * @date : 2016年7月19日 ,下午5:37:06 * @param : @param A * @param : @param s 二叉树根节点坐标 * @param : @param m 二叉树尾节点坐标 * @Version : vx.x */public static void heapAdjust(int[] A, int s, int m){ int tmp = A[s]; for(int j=2*s+1;j<=m;j=j*2+1){ if(j<m && A[j]<A[j+1]){ //比较左右两个子节点谁大,并记录大的坐标; j<m保证了j+1不会超界 j++; } if(tmp > A[j]){ //将父节点A[s]与上面得到的较大子节点比较,为true说明已是大堆顶,退出for循环 break; } else{ //否则将较大子节点的值赋给父节点,并将原父节点的下标s变为较大节点的下标j,实现了将较大数向上推,较小数向下抛 A[s] = A[j]; s=j; } } A[s] = tmp;//整个循环完成后,将最初父节点的值,复制到循环后相应的节点上。}
/** * * <p>@MethodName : mSort</p> * <p>@Description: 递归型归并排序算法</p> * @date : 2016-7-6 ,下午4:27:19 * @param : @param sR :原始数组 * @param : @param tR1 :排序后数组 * @param : @param s :数组起始下标 * @param : @param t :数组结尾下标 * @Version : v1.0 */static void mSort(int[] sR,int[] tR1, int s , int t){ int m; //将数组二等分坐标 int[] tR2 = new int[sR.length]; //二分后数组的临时排序缓冲数组 if(s==t){ tR1[s]=sR[s]; } else { m=(s+t)/2; //将sR[s..t] 平分为 sR[s..m]和sR[m+1..t] mSort(sR, tR2, s, m); //递归将sR[s..m]归并为有序的tR2[s..m] mSort(sR, tR2, m+1, t); //递归将sR[m+1,t]归并为有序tR2[m+1..t] merge(tR2,tR1,s,m,t); //将tR2[s..m]和tR2[m+1,t]归并到tR1[s..t] }}/** * * <p>@MethodName : merge</p> * <p>@Description: 将部分归并数组进行最后排序</p> * @date : 2016-7-6 ,下午4:40:33 * @param : @param sR :部分归并数组 * @param : @param tR :最终有序数组 * @param : @param i :数组起始下标 * @param : @param m :数组中间下标 * @param : @param n :数组结尾下标 * @Version : vx.x */static void merge(int sR[],int tR[] ,int i ,int m ,int n){ int j,k,l; for(j=m+1,k=i;i<=m && j<=n;k++){ if(sR[i] < sR[j]){ tR[k] = sR[i++]; }else { tR[k] = sR[j++]; } } if(i<=m){ for(l=0;l<=m-i;l++){ tR[k+l]=sR[i+l]; } } if(j<=n){ for(l=0;l<=n-j;l++){ tR[k+l]=sR[j+l]; } }}
/** * * <p>@MethodName : mergeSort</p> * <p>@Description: 非递归方式的合并排序</p> * @param : @param sR 带排序的数组 * @date : 2016-7-6 ,下午9:15:30 * @Version : v1.0 */static int[] mergeSort(int[] sR){ int m; //将数组二等分坐标 int[] tR = new int[sR.length]; //二分后数组的临时排序缓冲数组 int k=1; //子序列长度因子 while(k < sR.length){ MergePass(sR,tR,k,sR.length-1); k=k*2; MergePass(tR,sR,k,sR.length-1); k=k*2; } return sR;}/** * * <p>@MethodName : MergePass</p> * <p>@Description: 将sR数组中长度为s的相邻子序列两两归并到tR数组中</p> * @date : 2016-7-6 ,下午9:20:15 * @param : @param sR :原始数组 * @param : @param tR :排序后数组 * @param : @param s :待排序子数组的长度 * @param : @param n :原始数组长度 * @Version : v1.0 */static void MergePass(int sR[] , int tR[], int s , int n){ int i = 0; while(i <= n-2*s+1){ //步进为2s的情况下:能循环的最大次数 merge(sR, tR, i, i+s-1, i+2*s-1); i=i+2*s; } if(i<n-s+1){//将最后剩下的不够2s长度的子序列进行排序 merge(sR, tR, i, i+s-1, n); } else{ for(int j=i;j<=n;j++){ tR[j] = sR[j]; } }}/** * * <p>@MethodName : merge</p> * <p>@Description: 将部分归并数组进行最后排序</p> * @date : 2016-7-6 ,下午4:40:33 * @param : @param sR :部分归并数组 * @param : @param tR :最终有序数组 * @param : @param i :数组起始下标 * @param : @param m :数组中间下标 * @param : @param n :数组结尾下标 * @Version : vx.x */static void merge(int sR[],int tR[] ,int i ,int m ,int n){ int j,k,l; for(j=m+1,k=i;i<=m && j<=n;k++){ if(sR[i] < sR[j]){ tR[k] = sR[i++]; }else { tR[k] = sR[j++]; } } if(i<=m){ for(l=0;l<=m-i;l++){ tR[k+l]=sR[i+l]; } } if(j<=n){ for(l=0;l<=n-j;l++){ tR[k+l]=sR[j+l]; } }}
/** * * <p>@MethodName : quickSort</p> * <p>@Description: 进行快速排序</p> * @date : 2016年7月18日 ,下午7:19:20 * @param : @param A * @return * @Version : vx.x */ public static void quickSort(int[] A,int startIdx,int endIdx){ int pivot; if(startIdx < endIdx){ pivot = partition(A,startIdx,endIdx); //将待排序数组一分为二,返回枢轴值pivot quickSort(A,startIdx,pivot-1); //对于弟子表递归排序 quickSort(A,pivot+1,endIdx); //对高子表递归排序 } } /** * * <p>@MethodName : partition</p> * <p>@Description: 获取枢轴值位置</p> * @date : 2016年7月18日 ,下午11:18:15 * @param : @param A 待排序数组 * @param : @param startIdx 开始坐标 * @param : @param endIdx 结束坐标 * @param : @return 枢纽坐标位置 * @Version : vx.x */ public static int partition(int[] A,int startIdx,int endIdx){ int pivotkey; pivotkey = A[startIdx]; //这里用子表的第一个记录做枢轴记录 while(startIdx < endIdx){ while(startIdx < endIdx && A[endIdx] >= pivotkey){ //此时pivotkey=A[startIdx] endIdx--; } swap(A,startIdx,endIdx); //pivotkey = A[endIdx] while(startIdx < endIdx && A[startIdx] <= pivotkey){ startIdx++; } swap(A,startIdx,endIdx); //pivotkey=A[startIdx] } return startIdx;} /** * * <p>@MethodName : swap</p> * <p>@Description: 交换数组a,b位置的数据</p> * @date : 2016年7月18日 ,下午11:37:53 * @param : @param A * @param : @param a * @param : @param b * @Version : vx.x */static void swap(int[] A , int a, int b){ int temp = A[a]; A[a] = A[b]; A[b] = temp;}
联系客服