本文共 2347 字，大约阅读时间需要 7 分钟。

一、冒泡

时间复杂度：O(n^2)，空间复杂度：O(1)，稳定的算法

冒泡的思路：相邻元素之间进行比较，选出最大或最小的元素放至数组最后一个位置

普通冒泡就不介绍了，这里来写一下，上浮下沉的冒泡排序

public class BubbleBetter {	public static void main(String[] args) {		// TODO 自动生成的方法存根		int[] arr = new int[] {9,5,2,7,4,6,3,1,1,1,8,0};		for(int i=0,j=arr.length-1;i
   
    arr[m]) {					int temp = arr[i];					arr[i] = arr[m];					arr[m] = temp;				}			}			//从后往前排序			for(int n=j;n>=0;n--) {				if(arr[j]
   

二、选择排序O(n^2)

时间复杂度：O(n^2),空间复杂度:O(1),不稳定的排序

是通过每次从头至尾比较一次，得到最大或者最小的元素，一趟只能将一个元素放至数组首部位置

public static void select(int[] arr) {		for(int i=0;i

三、快排

快排思路：选取基准，分别化为小于基准的一边和大于基准的一边，然后递归调用实现

时间复杂度：平均时间复杂度为O(log2N);最差为O(n^2),空间复杂度为：O(log2N),不稳定的排序

public class QuickSort {	public static void main(String[] args) {		// TODO 自动生成的方法存根		int[] a =  {9,5,2,7,4,6,3,1,1,1,8,0};		quickSort(a);		for(int i=0;i
   
    0) {					quickSort(a,0,a.length-1);//		}	}	public static void quickSort(int[] a,int low,int high) {		if(low>high) {			return;		}		int i=low;		int j= high;		int key = a[low];		while(i
    
     key) {				j--;			}			while(i
     
      <=key) {				i++;			}			if(i
     
    
   

四、插入排序

插入排序思路:在当前有序序列中插入元素，直至当前元素插入结束

时间复杂度：O(n^2),空间复杂度：O(1)，稳定的排序

public class test {	public static void main(String[] args) {		// TODO 自动生成的方法存根		int[] a =  {9,5,2,7,4,6,3,1,1,1,8,0};		int n = 0;		for(int i=1;i
   
    =0&&tmp
   

五、归并排序

归并思路：归并就是将当前数组划分为两路，然后再逐层合并，直至合并结束

时间复杂度：最好，最差均为O(log2N),空间复杂度：O(1)，稳定的排序

public class test {	public static void main(String[] args) {		// TODO 自动生成的方法存根		int[] arr =  {9,5,2,7,4,6,3,1,1,1,8,0};		Merger(arr,0,arr.length-1);		for(int i=0;i

六、堆排序

堆排思路：堆排是先构建大小堆，在通过调整堆来实现的排序（想得到升序就构建大根堆，想得到降序就构建小根堆）

时间复杂度：平均和最坏均为O(log2N),空间复杂度：O(1),不稳定排序

public class test {	public static void main(String[] args) {		int[] arr ={9,5,2,7,4,6,3,1,1,1,8,0};		heapSort(arr);	}	public static void heapSort(int[] list) {		//循环建立初始堆		for(int i=list.length/2;i>=0;i--) {			HeapAdjust(list,i,list.length-1);		}		//进行n-1次循环，完成排序		for(int i=list.length-1;i>0;i--) {			//最后一个元素和第一个元素交换			int temp = list[i];			list[i] = list[0];			list[0] = temp;						//筛选R[0]节点，得到i-1个节点的堆			HeapAdjust(list,0,i);			System.out.format("第%d躺:\t",list.length-i);			for(int k=0;k
   
    =array[child]) {				break;			}			//把孩子节点的值赋给父节点			array[parent] = array[child];			//选取孩子节点的左孩子节点，继续向下筛选			parent = child;			child = 2*child+1;		}		array[parent]=temp;	}}
   

七、希尔排序

八、基数排序