首页 > 代码库 > 八大排序算法总结
八大排序算法总结
排序算法总结：
排序法 | 平均时间 | 最差情形 | 稳定度 | 额外空间 | 备注 |
冒泡 | O(n2) | O(n2) | 稳定 | O(1) | n小时较好 |
交换 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
选择 | O(n2) | O(n2) | 不稳定 | O(1) | n小时较好 |
插入 | O(n2) | O(n2) | 稳定 | O(1) | 大部分已排序时较好 |
基数 | O(logRB) | O(logRB) | 稳定 | O(n) | B是真数(0-9)， R是基数(个十百) |
Shell | O(nlogn) | O(ns) 1<s<2 | 不稳定 | O(1) | s是所选分组 |
快速 | O(nlogn) | O(n2) | 不稳定 | O(nlogn) | n大时较好 |
归并 | O(nlogn) | O(nlogn) | 稳定 | O(1) | n大时较好 |
堆 | O(nlogn) | O(nlogn) | 不稳定 | O(1) | n大时较好 |
插入排序
java实现：
package sort;public class InsertSort { public static void main(String[] args) { int[] arr={70,80,31,37,10,1,48,60,33,80}; insertSort(arr); for(int each:arr) System.out.print(each+" "); } public static void insertSort(int[] arr) { int len=arr.length; for(int i=1; i<len; i++) { for(int j=0; j<i; j++) { if(arr[i]<arr[j]) { int temp=arr[i]; for(int k=i; k>j; k--) arr[k]=arr[k-1]; arr[j]=temp; break; } } } }}c++实现
#include<iostream>using namespace std;void insertSort(int a[],int len);int main(){ int a[]={70,80,31,37,10,1,48,60,33,80}; int len=sizeof(a)/sizeof(int); insertSort(a,len); for(int i=0; i<len; i++) cout<<a[i]<<" ";}void insertSort(int a[],int len){ int i,j; for(i=1; i<len; i++) { for(j=0; j<i; j++) { if(a[i]<a[j]) { int k,temp=a[i]; for(k=i; k>j; k--) a[k]=a[k-1]; a[k]=temp; } } }}
选择排序
java实现
package sort;public class SelectSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] arr={70,80,31,37,10,1,48,60,33,80}; selectSort(arr); for(int i=0; i<arr.length; i++) System.out.print(arr[i]+" "); } public static void selectSort(int[] arr){ int i,j; int min,temp; for(i=0; i<arr.length; i++) { min=i; for(j=i; j<arr.length; j++) { if(arr[j]<arr[min]) { min=j; } } if(min!=i) { temp=arr[i]; arr[i]=arr[min]; arr[min]=temp; } } }}
c++实现
#include<iostream>using namespace std;void insertSort(int a[],int len);int main(){ int a[]={70,80,31,37,10,1,48,60,33,80}; int len=sizeof(a)/sizeof(int); insertSort(a,len); for(int i=0; i<len; i++) cout<<a[i]<<" ";}void insertSort(int a[],int len){ int i,j; for(i=1; i<len; i++) { for(j=0; j<i; j++) { if(a[i]<a[j]) { int k,temp=a[i]; for(k=i; k>j; k--) a[k]=a[k-1]; a[k]=temp; } } }}
冒泡排序
java实现
package sort;public class BubbleSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] arr={70,80,31,37,10,1,48,60,33,80}; bubbleSort(arr); for(int i=0; i<arr.length; i++) System.out.print(arr[i]+" "); } private static void bubbleSort(int[] arr) { // TODO Auto-generated method stub int i,j; int temp; for(i=arr.length-1; i>0; i--) { for(j=0; j<i; j++) { if(arr[j]>arr[j+1]) { temp=arr[j]; arr[j]=arr[j+1]; arr[j+1]=temp; } } } }}c++实现
#include<iostream>using namespace std;void bubbleSort(int a[],int len);int main(){ int a[]={70,80,31,37,10,1,48,60,33,80}; int len=sizeof(a)/sizeof(int); bubbleSort(a,len); for(int i=0; i<len; i++) cout<<a[i]<<" ";}void bubbleSort(int a[],int len){ int i,j; int temp; for(i=len-1; i>0; i--) { for(j=0; j<i; j++) { if(a[j]>a[j+1]) { temp=a[j+1]; a[j+1]=a[j]; a[j]=temp; } } }}
交换排序
java实现
package sort;public class SwapSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] arr={70,80,31,37,10,1,48,60,33,80}; swaptSort(arr); for(int i=0; i<arr.length; i++) System.out.print(arr[i]+" "); } private static void swaptSort(int[] arr) { // TODO Auto-generated method stub int i,j; int temp; for(i=1; i<arr.length; i++) { for(j=0; j<i; j++) { if(arr[i]<arr[j]) { temp=arr[i]; arr[i]=arr[j]; arr[j]=temp; } } } }}
快速排序
java实现
package sort;public class QuickSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int []a={16,7,3,20,17,8}; for(int i=0; i<a.length; i++) System.out.print(a[i]+" "); quickSort(a); System.out.println(); for(int i=0; i<a.length; i++) System.out.print(a[i]+" "); } public static void quickSort(int a[]) { quickSort(a,0,a.length-1); } public static void quickSort(int a[],int l,int r){ int i=l,j=r; int x=a[i]; while(i<j) { while(i<j && x<=a[j]) j--; if(i<j) a[i]=a[j]; while(i<j && x>a[i]) i++; if(i<j) a[j]=a[i]; } if(l<i-1) quickSort(a,l,i-1); if(i+1<r) quickSort(a,i+1,r); a[i]=x; }}c++实现
#include<iostream>using namespace std;void quickSort(int a[],int len);void quickSort(int a[],int l,int r);int main(){ int a[]={70,80,31,37,10,1,48,60,33,80}; int len=sizeof(a)/sizeof(int); quickSort(a,len); for(int i=0; i<len; i++) cout<<a[i]<<" ";}void quickSort(int a[],int len){ quickSort(a,0,len-1);}void quickSort(int a[],int l,int r){ int i=l,j=r; int x=a[i]; while(i<j) { while(i<j && x<=a[j]) j--; if(i<j) a[i]=a[j]; while(i<j && x>a[i]) i++; if(i<j) a[j]=a[i]; } if(l<i-1) quickSort(a,l,i-1); if(i+1<r) quickSort(a,i+1,r); a[i]=x;}
希尔排序
java实现
package sort;public class ShellSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] arr={70,80,31,37,10,1,48,60,33,80}; shellSort(arr); for(int i=0; i<arr.length; i++) System.out.print(arr[i]+" "); } private static void shellSort(int[] arr) { // TODO Auto-generated method stub int i,j,k; int gap,temp; for(gap=arr.length/2; gap>0; gap=gap/2) { for(i=0; i<gap; i++) { for(j=i+gap; j<arr.length; j=j+gap) { if(arr[j]<arr[j-gap]) { temp=arr[j]; arr[j]=arr[j-gap]; arr[j-gap]=temp; } } } } }}
归并排序
java实现
package sort;public class MergeSort { /** * @param args */ public static void main(String[] args) { // TODO Auto-generated method stub int[] arr={16,7,3,20,17,8}; int[] result=mergeSort(arr); for(int i=0; i<result.length; i++) System.out.print(result[i]+" "); } private static int[] mergeSort(int[] arr) { // TODO Auto-generated method stub if(arr.length==1) return arr; int half=arr.length/2; int[] a=new int[half]; int[] b=new int[arr.length-half]; System.arraycopy(arr, 0, a, 0, half); System.arraycopy(arr, half, b, 0, b.length); a=mergeSort(a); b=mergeSort(b); return mergeSortSub(a,b); } private static int[] mergeSortSub(int[] a,int[] b){ int[] result=new int[a.length+b.length]; int i=0,j=0,k=0; while(i<a.length && j<b.length) { if(a[i]<b[j]) result[k++]=a[i++]; else result[k++]=b[j++]; } while(i<a.length) result[k++]=a[i++]; while(j<b.length) result[k++]=b[j++]; return result; }}
堆排序
package sort;public class CheapSort { public static final int MAX=10; public static void main(String[] args){ int []a={0,16,7,3,20,17,8}; int len=a.length; buildHeap(a,len-1); for(int i=1; i<len; i++) System.out.print(a[i]+","); sort(a,len-1); System.out.println(); for(int i=1; i<len; i++) System.out.print(a[i]+","); } public static void sort(int[] a,int size){ int n=size-1; if(n==1) return; swap(a,1,size); adjustHeap(a,1,n); sort(a,n); } public static void swap(int[] a,int i,int j){ int temp; temp=a[i]; a[i]=a[j]; a[j]=temp; } public static void buildHeap(int[] a,int size){ for(int i=size/2; i>0; i--) adjustHeap(a,i,size); } private static void adjustHeap(int[] a, int i, int size) { // TODO Auto-generated method stub int lchild=i*2; int rchild=i*2+1; int max=i; if(lchild<size && a[lchild]>a[max]) max=lchild; if(rchild<size && a[rchild]>a[max]) max=rchild; if(max!=i) { swap(a,i,max); adjustHeap(a,max,size); } }}
八大排序算法总结
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。