1.   太久没复习基础了，写个冒泡排序都要想一会。今天手痒总结一下排序算法。目前网上博客普遍都有详细介绍，写的很清楚。说实话我是没必要再写一遍的，感觉就是在啰嗦、还是重复性的，但是如果只是单纯看的话，不到3分钟我就忘记了（可能是健忘症晚期）。所以还是自己亲手“教训”一下印象比较深刻。

算法复杂度

1.时间复杂度

含义：基本操作执行次数
常见的：O（1）< O（logn）< O（n）<O(nlogn)< O（n^2）

2.空间复杂度

含义：存储空间的度量
空间复杂度O(1)：当一个算法的空间复杂度为一个常量，即不随被处理数据量n的大小而改变时，可表示为O(1)。
空间复杂度O(log2N)：当一个算法的空间复杂度与以2为底的n的对数成正比时，可表示为O(log2n) ， ax=N，则x=logaN。
空间复杂度O(n)：当一个算法的空间复杂度与n成线性比例关系时，可表示为0(n)。
常见排序算法 - 图1

（1）冒泡排序

1、简介：
重复地走访过要排序的元素列，依次比较两个相邻的元素，如果他们的顺序（如从大到小、首字母从A到Z）错误就把他们交换过来
2、步骤：
1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2.对每一对相邻元素做同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。
3.针对所有的元素重复以上的步骤，除了最后一个。
4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较
[

](https://blog.csdn.net/cs_lwb/article/details/84556693)

  1. public static void bubblesort(int[] a){
  2.         for (int i =0 ; i<a.length;i++){
  3.             for (int j =i+1 ; j<a.length;j++){
  4.                 if (a[i]>a[j]){
  5.                     int t =a[j];
  6.                     a[j]=a[i];
  7.                     a[i]=t;
  8.                 }
  9.             }
  10.         }
  11.     }

（2）选择排序

1、简介：
每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到全部待排序的数据元素排完。 选择排序是不稳定的排序方法。
2、步骤：
1.首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置。
2.再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。
3.重复第二步，直到所有元素均排序完毕。
[

](https://blog.csdn.net/cs_lwb/article/details/84556693)

  1.  public static void selectsort(int [] a){
  2.         for (int i = 0; i < a.length; i++) {
  3.             int min =a[i];
  4.             for (int j = i+1; j < a.length; j++) {
  5.                 if (a[j]<min){
  6.                     int t =min;
  7.                     min=a[j];
  8.                     a[j]=t;
  9.                 }
  10.                 a[i]=min;
  11.             }
  12.         }
  13.     }

（3）插入排序

1、简介：
插入算法把要排序的数组分成两部分：第一部分包含了这个数组的所有元素，但将最后一个元素除外（让数组多一个空间才有插入的位置），而第二部分就只包含这一个元素（即待插入元素）。在第一部分排序完成后，再将这个最后元素插入到已排好序的第一部分中。
2、步骤：
1.从第一个元素（下标0）开始，该元素可以认为已经被排序
2.取出下一个（下标1）元素，在已经排序的元素序列中从后向前扫描
3.如果该元素（已排序）大于新元素，将该元素移到下一位置
4.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5.将新元素插入到下一位置中
6.重复步骤2~5

  1. public static void insertsort(int [] a){
  2.         for (int i = 1; i < a.length; i++) {
  3.             int get = a[i];
  4.             int j = i-1;
  5.             //如果已排的部分值大于要插入的值就后移
  6.             while (j >= 0 && a[j] > get) {
  7.                 a[j + 1] = a[j];
  8.                 j--;
  9.             }
  10.             a[j + 1] = get;
  11.         }
  12.     }

（4）快速排序

1、简介：
在数组中随机选一个数（默认数组首个元素），数组中小于等于此数的放在左边，大于此数的放在右边，再对数组两边递归调用快速排序，重复这个过程。(思想是分治法思想)
2、步骤：
1.先从数列中取出一个数作为key值；（一开始默认是第一个）
2.将比这个数小的数全部放在它的左边，大于或等于它的数全部放在它的右边；
3.对左右两个小数列重复第二步，直至各区间只有1个数。

  1. public static void quicksort(int[] a, int left, int right) {
  2.         if (left < right) {
  3.             //获取上一个key所在的点 left
  4.             int i = getMiddle(a, left, right);
  5.             quicksort(a, left, i - 1);
  6.             quicksort(a, i + 1, right);
  7.         }
  8.     }
  9.     private static int getMiddle(int[] a, int low, int high) {
  10.         int pivot = a[low];
  11.         int i = low;
  12.         int j = high;
  13.         while (i < j) {
  14.             //确保右边的比这个数大 直到遇到一个数比key值小的
  15.             while (pivot <= a[j] && i < j) j--;
  16.             //左边的比这个数小   直到遇到一个数比key值大的
  17.             while (pivot >= a[i] && i < j) i++;
  18.             //交换 这个2个值
  19.             if (i < j) {
  20.                 int temp = a[i];
  21.                 a[i] = a[j];
  22.                 a[j] = temp;
  23.             }
  24.         }
  25.         //上面循环结束的条件其实是J=I 而这个点就是key值要放的点
  26.         a[low] = a[i];
  27.         a[i] = pivot;
  28.         return i;
  29.     }

[

](https://blog.csdn.net/cs_lwb/article/details/84556693)

（5）归并排序

1、简介：
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并。该算法采用经典的分治法
2、步骤：
常见排序算法 - 图2常见排序算法 - 图3

  1. public static void mergesort(int[] a,int left, int right){
  2.     //控制数组分裂的终止条件    
  3.     if(left<right) {
  4.             int mid = (left + right)/2;
  5.             mergesort(a, left, mid);//将数组左边进行分
  6.             mergesort(a, mid + 1, right);//将数组右边进行分
  7.             merge(a,left,mid,right);//分完后 将左右数组进行合并
  8.         }
  9.     }
  10.     public static void merge(int [] a,int left ,int mid, int right ){
  11.         int [] temp =new int [a.length];//创建临时数组
  12.         int l =left;//获取左边数组的起始点
  13.         int m =mid+1;//获取右边数组的起始点
  14.         int p=0;//临时数组的起点坐标
  15.         //判断核心 取左右数组的索引上的最小值 易错点：判断条件是mid right 不是m 可以等于
  16.         while (l<=mid&&m<=right) {
  17.             if (a[l] <= a[m]) {
  18.                 temp[p++] = a[l++];
  19.             } else {
  20.                 temp[p++] = a[m++];
  21.             }
  22.         }
  23.           while(l<= mid){
  24.               temp[p++]=a[l++];
  25.           }
  26.           while(m<= right){
  27.                 temp[p++]=a[m++];
  28.             }
  29.              p=0;
  30.           while (left<=right){
  31.               a[left++]=temp[p++];
  32.           }
  34.     }

[

](https://blog.csdn.net/cs_lwb/article/details/84556693)

（6）堆排序

（7）基数排序（桶排序）

[

](https://blog.csdn.net/cs_lwb/article/details/84556693)