冒泡排序

  • 算法复杂度 ：O(n)
  • 实现代码
    1. public static void BubbleSort(int []arr){
    2.   int temp;
    3.   for(int i=0;i<arr.length-1;i++){
    4.       for(int j=arr.length-1;j>i;j--){
    5.           if(arr[j]<arr[j-1]){
    6.               temp=arr[j];
    7.               arr[j]=arr[j-1];
    8.               arr[j-1]=temp;
    9.           }
    10.       }
    11.   }
    12. }

选择排序

  • 基本思想：

    在长度为N的数组中，第一次遍历n-1个数，找到最小的数1与第一个交换 第二次遍历n-2个数，找到最小的数与第二个元素交换 。。。 第n-1次遍历，找到最小的数与第n-1个元素交换，排序完成。

  • 平均时间复杂度：O(n)

  • java代码

    1. public static void SelectSort(int arr[]){
    2.   for(int i=0;i<arr.length-1;i++){
    3.       int minIndex=i;
    4.   }
    5.   for(int j=i+1;j<arr.length;j++){
    6.       if(arr[j]<arr[minIndex]) minIndex=j;
    7.       if(minIndex!=i){
    8.           int temp=arr[i];
    9.           arr[i]=arr[minIndex];
    10.           arr[minIndex]=temp;
    11.       }
    12.   }
    13. }

    插入排序

  • 基本思想

    在要排序的一组数中，假定前n-1个数已经排序好，现将第n个数岔道前面的有序数列的恰当位置中。

  • 平均时间复杂度：O(n)

  • java代码

    1. public static void insertSort(int arr[]){
    2.   int temp;
    3.   for(int i=0;i<arr.length-1;i++){
    4.       for(int j=i+1;j>0;j--){
    5.           if(arr[j]<arr[j-1]){
    6.               temp=arr[j-1];
    7.               arr[j-1]=arr[j];
    8.               arr[j]=temp;
    9.           }else{
    10.               break;
    11.           }
    12.       }
    13.   }
    14. }

    快速排序

  • 基本思想：分治

    • 先从数列中取出一个数作为key值
    • 将比这个数小的数全部放在它左边，大于等于它的数放在右边
    • 对左右区间重复上一步，直至各个区间只有一个数

  • java代码

    1. public static void quickSort(int a[],int l,int r){
    2.   if(l>=r)
    3.       return;
    4.   int i=l;
    5.   int j=r;
    6.   int key=a[l];
    7.   while(i<j){
    8.       while(i<j&&a[j]>=key)
    9.           j--;
    10.       if(i<j){
    11.           a[i]=a[j];
    12.           i++;
    13.       }
    14.       while(i<j&&a[i]<key)
    15.           i++;
    16.       if(i<j){
    17.           a[j]=a[i];
    18.           j--;
    19.       }
    20.   }
    21.   a[i]=key;
    22.   quickSort(a,l,i-1);
    23.   quickSort(a,i+1,r);
    24. }

    希尔排序

  • 基本思想：

    在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。然后逐渐减小增量。 重入上述步骤，直至增量为1，此时数据基本有序，最后进行插入排序。

  • java代码

    1. public static void shellSort(int arr[]){
    2.   int temp=0;
    3.   int incre=arr.length;
    4.   while(true){
    5.       incre=incre/2;
    6.       for(int k=0;k<incre;k++){
    7.           for(int i=k+incre;i<arr.length;i+=incre){
    8.               for(int j=i;>k;j-=incre){
    9.                   if(arr[j]<arr[j-incre]){
    10.                       temp=arr[j-incre];
    11.                       arr[j-incre]=arr[j];
    12.                       arr[j]=temp;
    13.                   }else{
    14.                       break;
    15.                   }
    16.               }
    17.           }
    18.       }
    19.       if(incre==1){
    20.           break;
    21.       }
    22.   }
    23. }

    归并排序

  • 平均时间复杂度：O(NlogN)

  • java代码

    1. public static void mergeSort(int a[],int first,int last,int temp[]){
    2.   if(first<last){
    3.       int middle=(firstt+last)/2;
    4.       mergeSort(a,first,middle,temp);
    5.       mergeSort(a,middle+1,last,temp);
    6.       mergeArray(a,first,middle,last,temp);
    7.   }
    8. }
    9. public static void mergeArray(int a[],int firstt,int middle,int end,int temp[]){
    10.   int i=first;
    11.   int m=middle;
    12.   int j=middle+1;
    13.   int n=end;
    14.   int k=0;
    15.   while(i<=m&&j<=n){
    16.       if(a[i]<=a[j]){
    17.           temp[k]=a[i];
    18.           k++;
    19.           i++;
    20.       }else{
    21.           temp[k]=a[j];
    22.           k++;
    23.           j++;
    24.       }
    25.   }
    26.   while(i<=m){
    27.       temp[k]=a[i];
    28.       k++;
    29.       i++;
    30.   }
    31.   while(j<=n){
    32.       temp[k]=a[j];
    33.       k++;
    34.       j++;
    35.   }
    36.   for(int _i=0;_i<k;_i++){
    37.       a[first+_i]=temp[_i];
    38.   }
    39. }

    堆排序

  • 平均时间复杂度：O(NlogN)

  • java代码 ```java public static void makeMinHeap(int a[],int n){ for(int i=(n-1)/2;i>=0;i—){

    1.   minHeapFixDown(a,i,n);

    } } public static void minHeapFixDown(int a[],int i,int n){ int j=2*i+1; int temp=0; while(j<n){

      if(j+1<n&&a[j+1]<a[j]) j++;
  if(a[i]<=a[j]) break;
  temp=a[i];
  a[i]=a[j];
  a[j]=temp;

  i=j;
  j=2*i+1;

    } }

public static void minHeapSort(int a[],int n){ int temp=0; makeMinHeap(a,n); for(int i=n-1;i>0;i—){ temp=a[0]; a[0]=a[i]; a[i]=temp; minHeapFixDown(a,0,i); } }

<a name="JkSXS"></a>
# 基数排序

- 在长度为10的数组中，首先根据个位数分类，放在十个表头中，再根据十位数，大小插入到链表中适当位置
- java代码
```java
public static void radixSort(int a[],int temp[],int n,int k,int r,int cnt[]){
    //n:序列的数字个数 
    //k:最大的位数2
    //r:基数10
    //cnt:存储bin[i]的个数
    for(int i=0;rtok=1;i<k;i++,rtok=rtok*r){
        for(int j=0;j<r;j++){
            cnt[j]=0;
        }
        for(int j=0;j<n;j++){
            cnt[(a[j]/rtok)%r]++;
        }
        for(int j=n-1;j>=0;j--){
            cnt[(a[j]/rtok)%r]--;
            temp[cnt[(a[j]/rtok)%r]]=a[j];
        }
        for(int j=0;j<n;j++){
            a[j]=temp[j];
        }
    }
}