时间复杂度：
冒泡，选择，插入 O(n^2)
归并，快排，堆排序，希尔排序 O(nlogn)
计数，基数排序 O（n）
空间复杂度
O（1）:冒泡，选择，插入，堆排序，希尔排序
O（logn）~O（n）: 快排
O（n）:归并
O（m）:计数，基数排序
一、冒泡排序
思想：冒泡排序顾名思义就是整个过程像气泡一样往上升（假设由小到大排序）：对于给定n个数，从头开始让相邻的两个元素进行比较，前面的数大于后面的数就交换位置，进行一趟排序之后，最大的数在第n位。然后对前（n-1）个数进行第二趟比较排序，次大值在第n-2位；重复该过程，直到数剩下一个为止。即n个数，比较n-1趟。
代码：
public void bubbleSort(int[] arr)
{
int n=arr.length;
for (int i = 0; i < n - 1; i++) //外循环控制排序趟数，n个数，比较n-1趟,[0,n-1)
{
for (int j = 0; j < n -i- 1; j++) //内层循环控制每一趟排序多少次,[0,n-i-1)
{ //第0趟排序，需要比较n-1次，第i趟排序，需要比较n-(i+1)次，
if (arr[j] > arr[j+1])
{
int temp = arr[j];
arr[j] = arr[j+1];
arr[j+1] = temp;
}
}
}
}复杂度分析：
当最好的情况：待排序的序列本身就是有序的，需要进行一趟（n-1）次比较，没有数据交换，时间复杂度为O(n).
当最坏的情况：待排序的序列是逆序的，此时需要比较次数为：1+2+3+…+(n-1)=n(n-1)/2 次，并作等数量级的记录移动，因此总的时间复杂度为O(n^2)。
二、选择排序
思想：找到数组中的最小元素，将它与数组的第一个元素交换位置。再从剩下的元素中找到最小的元素，将它与数组的第二个元素交换位置。不断进行这样的操作，直到将整个数组排序。
代码：
public void selectSort(int[]arr)
{
int n=arr.length;
for (int i = 0; i <n ; i++)
{
int min=i;//先设当前所遍历的下标i所在的元素值本身就是最小值
for (int j = i+1; j <n ; j++)//遍历第i个时，要寻找下标[i+1,n)内最小元素下标min
{
if(arr[j]<arr[min])//存在arr[j]比当前值arr[i]=arr[min]小的，就更新最小值下标
min=j;
}
swap(arr,i,min);//交换arr[i] , arr[min]
}
}
public void swap(int[] arr,int i,int min)
{
if (arr[i] > arr[min])
{
int temp = arr[i];
arr[i] = arr[min];
arr[min] = temp;
}
}复杂度
选择排序需要 ~N2/2 次比较和 ~N 次交换，它的运行时间与输入无关，这个特点使得它对一个已经排序的数组也需要这么多的比较和交换操作。
三、插入排序
思想
代码
复杂度
四、快速排序
1、基本算法
1）基本思想：
归并排序将数组分为两个子数组分别排序，并将有序的子数组归并使得整个数组排序；
快速排序通过一个划分值将数组分为两个子数组，左子数组小于等于划分值，右子数组大于等于划分值，将这两个子数组排序也就将整个数组排序了。,
public class QuickSort {
public void qSort(int[] arr)
{
qSort(arr,0,arr.length-1);
}
private void qSort(int[] arr,int lo,int hi)
{
if(hi<=lo)
return;
int j= partition(arr,lo,hi);//将数组分成两部分，j就是每次划分值下标
qSort(arr,lo,j-1); //递归排序左子数组
qSort(arr,j+1,hi); //递归排序右子数组
}
}2）切分思想：
取 arr[lo] 作为切分元素，然后从数组的左端向右扫描直到找到第一个大于等于它的元素，再从数组的右端向左扫描找到第一个小于等于它的元素，交换这两个元素，并不断进行这个过程，就可以保证左指针 i 的左侧元素都不大于切分元素，右指针 j 的右侧元素都不小于切分元素。当两个指针相遇时，将切分元素 arr[lo] 和 arr[j] 交换位置。
//划分函数如下：
private int partition(int[] arr, int lo, int hi)
{
int i = lo;
int j = hi;
int key = arr[lo];//设置划分值key为数组的第一个元素
while (i<j)
{
while(i<j&&arr[j]>=key)//先看右边，如果右边值比划分值大，则依次向左边递减j--
j--;
while(i<j&&arr[i]<=key)//再看左边，如果左边值比划分值小，则依次向右递增i++
i++;
swap(arr, i, j);//否则，满足交换条件就交换,即左边值比key大，右边值比key小了，则对应交换
}
swap(arr, lo, j);//当i==j相遇时，将划分值arr[lo]与相遇i/j位置的值交换，即key与arr[j]交换
return j;
}3）完整代码如下：
public class QuickSort {
public void qSort(int[] arr)
{
qSort(arr,0,arr.length-1);
}
private void qSort(int[] arr,int lo,int hi)
{
if(hi<=lo)
return;
int j= partition(arr,lo,hi);//将数组分成两部分，j就是每次划分值下标
qSort(arr,lo,j-1); //递归排序左子数组
qSort(arr,j+1,hi); //递归排序右子数组
}
private int partition(int[] arr, int lo, int hi)
{
int i = lo;
int j = hi;
int key = arr[lo];//设置划分值key为数组的第一个元素
while (i<j)
{
while(i<j&&arr[j]>=key)//先看右边，如果右边值比划分值大，则依次向左边递减j--
j--;
while(i<j&&arr[i]<=key)//再看左边，如果左边值比划分值小，则依次向右递增i++
i++;
swap(arr, i, j);//否则，满足交换条件就交换,即左边值比key大，右边值比key小了，则对应交换
}
swap(arr, lo, j);//当i==j相遇时，将划分值arr[lo]与相遇i/j位置的值交换，即key与arr[j]交换
return j;
}
private void swap(int[] arr, int i, int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
//主函数验证
public static void main(String[] args) {
QuickSort quickSort=new QuickSort();
int[] arr=new int[]{3,5,4,1,2};
System.out.println(Arrays.toString(arr));
quickSort.qSort(arr);
System.out.println(Arrays.toString(arr));
/*for (int val : arr) { System.out.print(val+" "); }*/
}
}2、性能分析
快速排序是原地排序，不需要辅助数组，但是递归调用需要辅助栈。
快速排序最好的情况下是每次都正好能将数组对半分，这样递归调用次数才是最少的。这种情况下比较次数为 CN=2CN/2+N，复杂度为 O(NlogN)。
最坏的情况下，第一次从最小的元素切分，第二次从第二小的元素切分，如此这般。因此最坏的情况下需要比较 N2/2。为了防止数组最开始就是有序的，在进行快速排序时需要随机打乱数组。
快速排序为什么快？
快速排序之所比较快，因为相比冒泡排序，每次交换是跳跃式的。每次排序的时候设置一个基准点，将小于等于基准点的数全部放到基准点的左边，将大于等于基准点的数全部放到基准点的右边。这样在每次交换的时候就不会像冒泡排序一样每次只能在相邻的数之间进行交换，交换的距离就大的多了。因此总的比较和交换次数就少了，速度自然就提高了。当然在最坏的情况下，仍可能是相邻的两个数进行了交换。因此快速排序的最差时间复杂度和冒泡排序是一样的都是O(N^2)，它的平均时间复杂度为O(NlogN)。其实快速排序是基于一种叫做“二分”的思想。
参考：https://blog.csdn.net/as02446418/article/details/47395867
3、基于切分的快速选择算法（找出数组第k大元素）
快速排序的 partition() 方法，会返回一个整数 j 使得 a[lo..j-1] 小于等于 a[j]，且 a[j+1..hi] 大于等于 a[j]，此时 a[j] 就是数组的第 j 大元素。
可以利用这个特性找出数组的第 k 个元素。
public class QuickSort {
//基于快排思想，找出第k大元素
public int select(int[]arr,int k){
int lo=0;
int hi=arr.length-1;
while(lo<hi)
{
int j=partition(arr,lo,hi);
if(j==k)
return arr[k];
else if(k<j)//在左边找
hi=j-1;
else //在右边找
lo=j+1;
}
return arr[k];
}
//划分函数
private int partition(int[] arr, int lo, int hi)
{
int i = lo;
int j = hi;
int key = arr[lo];//设置划分值key为数组的第一个元素
while (i<j)
{
while(i<j&&arr[j]>=key)//先看右边，如果右边值比划分值大，则依次向左边递减j--
j--;
while(i<j&&arr[i]<=key)//再看左边，如果左边值比划分值小，则依次向右递增i++
i++;
swap(arr, i, j);//否则，满足交换条件就交换,即左边值比key大，右边值比key小了，则对应交换
}
swap(arr, lo, j);//当i==j相遇时，将划分值arr[lo]与相遇i/j位置的值交换，即key与arr[j]交换
return j;
}
//交换函数
private void swap(int[] arr, int i, int j)
{
int temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
//主函数验证
public static void main(String[] args) {
QuickSort quickSort=new QuickSort();
int[] arr=new int[]{3,5,4,1,2};
int res=quickSort.select(arr,3);
System.out.println(res);
}
}五、堆排序
堆排序的基本思想：
将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值。然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了
堆排序的基本思路：
a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆;
b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端;
复杂度分析
堆排序是一种选择排序，整体主要由构建初始堆+交换堆顶元素和末尾元素并重建堆两部分组成。其中构建初始堆经推导复杂度为O(n)，在交换并重建堆的过程中，需交换n-1次，而重建堆的过程中，根据完全二叉树的性质，[log2(n-1),log2(n-2)…1]逐步递减，近似为nlogn。所以堆排序时间复杂度一般认为就是O(nlogn)级。
参考：https://www.cnblogs.com/chengxiao/p/6129630.html
代码如下：
import java.util.Arrays;
public class heapSort {
public static void sort(int []arr)
{
//1.将序列构建成大顶堆
for(int i=arr.length/2-1;i>=0;i--)
{
//从第一个非叶子结点从下至上，从右至左调整结构
adjustHeap(arr,i,arr.length);
}
//2.交换堆顶元素与末尾元素+调整堆结构
for(int j=arr.length-1;j>0;j--)
{
swap(arr,0,j);//将堆顶元素与末尾元素进行交换
adjustHeap(arr,0,j);//重新对剩下的堆进行调整
}
}
/** * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上） * @param arr * @param i * @param length */
public static void adjustHeap(int []arr,int i,int length)
{
int temp = arr[i];//先取出当前元素i
for(int k=i*2+1;k<length;k=k*2+1)
{
//从i结点的左子结点开始，也就是2i+1处开始
if(k+1<length && arr[k]<arr[k+1])
{//如果左子结点小于右子结点，k指向右子结点
k++;
}
if(arr[k] >temp) //子节点上浮
{//如果子节点大于父节点，将子节点值赋给父节点（不用进行交换）
arr[i] = arr[k];
i = k; //将i指向子节点下标
}
else{
break;
}
}
arr[i] = temp;//将父节点值交换给子节点
}
//交换元素
public static void swap(int []arr,int a ,int b)
{
int temp=arr[a];
arr[a] = arr[b];
arr[b] = temp;
}
public static void main(String []args){
int []arr = {9,8,7,6,5,4,3,2,1};
sort(arr);
System.out.println(Arrays.toString(arr));
}
}