1.冒泡排序
从第一个元素开始依次i与i+1元素相比较，若i元素较大，则交换两元素。这样一趟下来最大的元素就到了队尾,第二趟则从第一个元素比到第n-1个元素,这样倒数第二个元素就是从第一个到n-1个元素里最大的。以此类推，经过n-1趟，要比较n-1+n-2+...+1次，故时间复杂度=n*(n-1)/2,为O(n^2).
1 public class Sort { 2 public void BubbleSort(int n,int a[]) { 3 for (int k = n - 1; k > 0; k--) { 4 for (int i = 0; i < k; i++) { 5 if (a[i] > a[i + 1]) 6 exchange(a,i,i+1); 7 } 8 } 9 } 10 11 public void exchange(int a[],int i,int j){ 12 int temp=a[i]; 13 a[i]=a[j]; 14 a[j]=temp; 15 } 16 }
public class Main { public static void main(String[] args) { int N=20; int[] a=new int[20]; System.out.println("排序前"); for(int i=0;i<N;i++){ a[i]=(int)(Math.random()*100+1); System.out.print(a[i]+" "); } Sort sort =new Sort(); sort.BubbleSort(N,a); System.out.println("\n冒泡排序后"); for(int i=0;i<N;i++) System.out.print(a[i]+" "); } }
2.简单选择排序
简单选择排序就是从第一个元素开始，依次和后面每个元素进行对比，把其中较小的元素暂存，每个元素与这个前面比过的最小元素在进行比较，这样一轮下来，就知道最小元素了，把它和第一个元素交换，这样第一个就是最小的了。然后第二趟就是从第二个元素往后，这样一趟完了第二个元素就是后面n-1个元素里最小的......这样一共要进行n-1趟，每i趟比较n-i次，故n-1+n-2+...+1=n*(n-1)/2，故时间复杂度为O(n^2)。简单选择排序是不稳定的排序。
public void SimpleSort(int n,int a[]){
int minIndex;
for(int i=0;i<n-1;i++){
minIndex=i;
for(int j=i+1;j<n;j++){
if(a[j]<a[minIndex])minIndex=j;
}
exchange(a,i,minIndex);
}
}
1 sort.SimpleSort(N,a); 2 System.out.println("\n排序后"); 3 for(int i=0;i<N;i++) System.out.print(a[i]+" ");
3.快速排序
快速排序就是选择第一个数作为基准，然后比它小的元素全部放到它的左边，比它大的元素全部放到右边，再对左右两边递归进行这样的排序，直到等个序列都排完。
编写程序时需要有两个索引，类似于首尾的两个指针。
1 public void QuickSort(int a[],int start,int end){ 2 if(start<end) { 3 int index = getMiddle(a, start, end); 4 QuickSort(a, 0, index - 1); 5 QuickSort(a, index + 1, end); 6 } 7 } 8 9 private int getMiddle(int a[],int start,int end){ 10 int base=a[start]; 11 while(start<end){ 12 while(end>start&&a[end]>=base) end--; 13 a[start]=a[end];//start++; 14 while(end>start&&a[start]<=base) start++; 15 a[end]=a[start];//end--; 16 } 17 a[start]=base; 18 return start; 19 }
1 sort.QuickSort(a,0,N-1); 2 System.out.println("\n排序后"); 3 for(int i=0;i<N;i++) System.out.print(a[i]+" ");
注：快速排序是通常被认为在同数量级（O(nlog2n)）的排序方法中平均性能最好的。但若初始序列按关键码有序或基本有序时，快排序反而蜕化为冒泡排序。
快速排序是一个不稳定的排序方法。
4.插入排序
插入排序就是依次扫描每个数，把它插到前面的有序队列里。从第二个数开始，第一个数就是一个有序队列。假设要比较第i个数了，那么就在它前面的序列从后往前扫描，如果那个数比它大的话，就让它后一个数等于它。依次扫描，等到某个数不大于这个数了，就把这个数插进去。一共进行n-1趟。时间复杂度T(n)=O()
1 public void InsertSort(int n,int a[]){ 2 int i,j; 3 int base; 4 for(i=1;i<n;i++){//i是想往前已经排好的队列里插入的那个数 5 base=a[i]; 6 j=i; 7 while(j>0&&a[j-1]>base){ 8 a[j]=a[j-1]; 9 j--; 10 } 11 a[j]=base; 12 } 13 }
总结：
稳定的：冒泡排序，直接插入排序，归并排序，基数排序
不稳定：简单选择，快速排序，堆排序，希尔排序
原文：http://www.cnblogs.com/HighMoon/p/7468049.html