十大经典排序算法总结

 //冒泡排序，a为数组，n为数组的长度
 public static void bobbleSort(int a[],int n){
 		if(n<=1) return;
 		for(int i=0;i<n;++i){
 		//提前退出冒泡排序的标志
 		boolean flag=false;
 		for(int j=1;j<n-i;++j){
 				if(a[j]<a[j-1]){
 						int tmp=a[j];a[j]=a[j-1];a[j-1]=tmp;//交换元素
 						flag=true;
 				}
 		}
 		if(flag==false) break;//如果没有元素交换，则已经有序，结束
 		}
 }

 public static void selectSort(int[] a,int n){
     for(int i=0;i<n;++i){
         int min=i;//min是最小元素的下标
         //寻找i--n之间最小的元素
         for(int j=i;j<n;++j){
             if(a[j]<a[min]) min=j;
        }
         //交换位置
        { int tmp=a[min];a[min]=a[i];a[i]=tmp; }
    }
 }

 //第一种做法，利用交换简化排序过程
 public static void insertionSort1(int[] a,int n){
 for(int i=0;i<n;++i){
 for(int j=i;j>0&&a[j]<a[j-1];--j)
 { int tmp=a[j];a[j]=a[j-1];a[j-1]=tmp; }//交换元素
 }
 }
 
 //第二种做法，数据搬移，然后插入
 public static void insertionSort2(int [] a,int n){
     for(int i=0;i<n;++i){
         int c=a[i],j;
         for(j=i;j>=0&&a[j]>=c;--j) ;//确定c应该插入的位置
         for(int k=i;k>=j+2;--k)//搬移数据
             a[k]=a[k-1];
         a[j+1]=c;//插入数据a[i]
    }
 }

 //希尔排序
 public static void shellSort(int [] a,int n){
     int h=1;
     while(h<=n/3) h=3*h+1;//初始化间隔h，目的是为了下文的统一
     while(h>=1){
     for(int i=0;i<n;++i){
         for(int j=i;j>=h&&a[j]<a[j-h];j=j-h){
             int tmp=a[j];a[j]=a[j-h];a[j-h]=tmp;//交换元素
        }
    }
     h=h/3;//减小间距
    }
 }

 //归并排序
 private static void sort(int [] a,int lo,int hi){
     if(lo>=hi) return;
     int mid=(lo+hi)/2;
     sort(a,lo,mid);//将左半部分排序
     sort(a,mid+1,hi);//将右半部分排序
     merge(a,lo,mid,hi);//归并结果
 }

 //原地归并算法,任务是将数组 a[lo---mid] 与数组 a[mid+1---hi]合并
 private static void merge(int [] a,int lo,int mid,int hi){
     //将数组 a 中的元素复制到数组 aux 中
     for(int i=lo;i<=hi;++i)
         aux[i]=a[i];
     //归并
     int i=lo,j=mid+1;
     for(int k=lo;k<=hi;++k){
         if(i>mid) a[k]=aux[j++];
         else if(j>hi) a[k]=aux[i++];
         else if(aux[j]<aux[i]) a[k]=aux[j++];
         else a[k]=aux[i++];
    }
 }

 //归并排序的最终代码
 private static int [] aux;
 public static void mergeSort(int [] a,int n){
     aux=new int[n];//申请一个数组提供给 merge算法
     sort(a,0,n-1);
 }

 public static void mergeSort2(int [] a,int n){
     //进行logn次两两归并
     aux=new int[n];
     //size是子数组的长度，lo是子数组的索引（即第一个元素）
     for(int size=1;size<n;size=size*2){
         for(int lo=0;li<n-size;lo+=size+size){
             merge(a,lo,lo+size-1,Math.min(lo+size+size-1,n-1));
        }
    }
 }

 //快速排序的实现
 public static void quickSort(int [] a,int n){
     sort(a,0,n-1);
 }
 //排序方法
 private static void sort(int [] a,int lo,int hi){
     if(lo>=hi) return;
     int i=partition(a,lo,hi);//切分
     sort(a,lo,i);//将左半部分排序
     sort(a,i+1,hi);//将右半部分排序
 }

 private static int partition(int [] a,int lo,int hi){
     int c=a[lo];//切分基准
     int i=lo,j=hi+1;//左右扫描指针
     while(true){
         while(a[--j]>=c) if(j==lo) break;
         while(a[++i]<=c) if(i==hi) break;
         if(i>=j) break;
        { int tmp=a[j];a[j]=a[i];a[i]=tmp; }//交换元素
    }
     a[lo]=a[j];a[j]=c;//将c放入合适的位置
     retrun j;//返回切分元素的位置
     
 }

 public class BucketSort {
     /**
      * 桶排序
      *
      * @param arr 数组
      * @param bucketSize 桶容量
      */
     public static void bucketSort(int[] arr, int bucketSize) {
         if (arr.length <= 1) {
             return;
        }
 
         // 数组最小值
         int minValue = arr[0];
         // 数组最大值
         int maxValue = arr[1];
         for (int i = 0; i < arr.length; i++) {
             if (arr[i] < minValue) {
                 minValue = arr[i];
            } else if (arr[i] > maxValue) {
                 maxValue = arr[i];
            }
        }
 
         // 桶数量
         int bucketCount = (maxValue - minValue) / bucketSize + 1;
         //桶
         int[][] buckets = new int[bucketCount][bucketSize];
         //每个桶中元素的个数
         int[] indexArr = new int[bucketCount];
 
         // 将数组中值分配到各个桶里
         for (int i = 0; i < arr.length; i++) {
             //计算出这个元素arr[i]应该处于哪个桶中
             int bucketIndex = (arr[i] - minValue) / bucketSize;
             buckets[bucketIndex][indexArr[bucketIndex]++] = arr[i];
        }
 
         // 对每个桶进行排序，这里使用了快速排序
         int k = 0;
         for (int i = 0; i < buckets.length; i++) {
             if (indexArr[i] == 0) {
                 continue;
            }
             //在这个桶排序中，我们用到了快速排序去完成桶内的排序
             Sort.quickSort(buckets[i], indexArr[i] - 1);
             for (int j = 0; j < indexArr[i]; j++) {
                 arr[k++] = buckets[i][j];
            }
        }
    }
 }

 public class CountingSort {
 
   // 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
   public static void countingSort(int[] a, int n) {
     if (n <= 1) return;
 
     // 查找数组中数据的范围
     int max = a[0];
     for (int i = 1; i < n; ++i) {
       if (max < a[i]) {
         max = a[i];
      }
    }
 
     // 申请一个计数数组book，下标大小[0,max]
     int[] book = new int[max + 1];
 
     // 计算每个元素的个数，放入book中
     for (int i = 0; i < n; ++i) {
       book[a[i]]++;
    }
 
     // 临时数组r，存储排序之后的结果
     int[] r = new int[n];
 
     //将结果储存在数组 r 中
       int index=0;
       for(int i=0;i<n;++i){
           for(int j=0;j<book[i];++j){
               r[index++]=a[j];
          }
      }
      // 将结果拷贝会a数组
     for (int i = 0; i < n; ++i) {
       a[i] = r[i];
    }
  }
 }

 public class CountingSort {
 
   // 计数排序，a是数组，n是数组大小。假设数组中存储的都是非负整数。
   public static void countingSort(int[] a, int n) {
     if (n <= 1) return;
 
     // 查找数组中数据的范围
     int max = a[0];
     for (int i = 1; i < n; ++i) {
       if (max < a[i]) {
         max = a[i];
      }
    }
 
     // 申请一个计数数组book，下标大小[0,max]
     int[] book = new int[max + 1];
 
     // 计算每个元素的个数，放入book中
     for (int i = 0; i < n; ++i) {
       book[a[i]]++;
    }
 
     // 依次累加
     for (int i = 1; i < max + 1; ++i) {
       book[i] = book[i-1] + book[i];
    }
 
     // 临时数组r，存储排序之后的结果
     int[] r = new int[n];
     // 计算排序的关键步骤了，有点难理解
     for (int i = n - 1; i >= 0; --i) {
       int index = book[a[i]]-1;
       r[index] = a[i];
       book[a[i]]--;
    }
 
     // 将结果拷贝会a数组
     for (int i = 0; i < n; ++i) {
       a[i] = r[i];
    }
  }
 }

 public class RadixSort {
 
     /**
      * 基数排序
      *
      * @param arr
      */
     public static void radixSort(int[] arr) {
         int max = arr[0];
         for (int i = 0; i < arr.length; i++) {
             if (arr[i] > max) {
                 max = arr[i];
            }
        }
 
         // 从个位开始，对数组arr按"指数"进行排序
         for (int exp = 1; max / exp > 0; exp *= 10) {
             countingSort(arr, exp);
        }
    }
 
     /**
      * 计数排序-对数组按照"某个位数"进行排序
      *
      * @param arr
      * @param exp 指数
      */
     public static void countingSort(int[] arr, int exp) {
         if (arr.length <= 1) {
             return;
        }
 
         // 计算每个元素的个数
         int[] book = new int[10];
         for (int i = 0; i < arr.length; i++) {
             book[(arr[i] / exp) % 10]++;
        }
 
         // 计算排序后的位置
         for (int i = 1; i < book.length; i++) {
             book[i] += book[i - 1];
        }
 
         // 临时数组r，存储排序之后的结果
         int[] r = new int[arr.length];
         for (int i = arr.length - 1; i >= 0; i--) {
             r[book[(arr[i] / exp) % 10] - 1] = arr[i];
             book[(arr[i] / exp) % 10]--;
        }
 
         for (int i = 0; i < arr.length; i++) {
             arr[i] = r[i];
        }
    }
 }