本文共 8299 字，大约阅读时间需要 27 分钟。
| 排序算法 | 平均时间复杂度 | 最好时间复杂度 | 最坏时间复杂度 | 空间复杂度 | 稳定性 |
|---|---|---|---|---|---|
| 冒泡排序 | O（n2） | O(n) | O（n2） | O(1) | 稳定 |
| 选择排序 | O（n2） | O（n2） | O（n2） | O(1) | 不稳定 |
| 插入排序 | O（n2） | O(n) | O（n2） | O(1) | 稳定 |
| 希尔排序 | O（n log n） | O（n log2 n） | O（n log2 n） | O(1) | 不稳定 |
| 归并排序 | O（n log n） | O（n log n） | O（n log n） | O(n) | 稳定 |
| 快速排序 | O（n log n） | O（n log n） | O（n2） | O(log n) | 不稳定 |
| 堆排序 | O（n log n） | O（n log n） | O（n log n） | O(1) | 不稳定 |
| 基数排序 | O（n x k） | O（n x k） | O（n x k） | O(n + k) | 稳定 |
| 桶排序 | O（n + k） | O（n + k） | O（n2） | O（n + k） | 稳定 |
注：
1.稳定与不稳定：对于相同的元素a和b而言，如果排序过后a仍旧在b的前面，那么a和b就是稳定，如果改变了原来的顺序，那就是不稳定的 2.内排序与外排序：上述表中排序都是内排序。内排序就是所有的排序过程都是在内存中完成，外排序是处理的数据太大，要通过磁盘才能处理 3.时间复杂度：一个算法程序执行完需要的时间 4.空间复杂度：运行完一个算法程序所需要的内存大小 5.n指的是数据规模，就是你要排多少数据 6.k是桶的个数，一般情况下是10public static void mergeSort(int[] arr,int left,int right,int[] temp){ int mid = (left + right) / 2; //定义中间点,然后以中间点为结点,开始对半分,设置重点,而真正开始便利的时候 //也是需要中点,从两边开始,按照固定的顺序开始遍历 if (left < right){ //加一个判定条件,说明只要有两个元素,那就开始循环,只有一个那就不循环 mergeSort(arr,left,mid,temp); mergeSort(arr,mid + 1,right,temp); merge(arr,left,mid,right,temp); } } public static void merge(int[] arr,int left,int mid,int right,int[] temp){ //真实的排序过程,涉及到遍历,就要设置两个遍历索引 int l = left; int r = mid + 1; int t = 0; //在中转数组中设置遍历索引 while (l <= mid && r <= right){ if (arr[l] < arr[r]){ temp[t] = arr[l]; t ++; l ++; }else{ temp[t] = arr[r]; t ++; r ++; } } //针对某一边到了,而另外一边没到的情况 //将没到末尾的一边完全 while (l <= mid){ temp[t] = arr[l]; t ++; l ++; } while (r <= right){ temp[t] = arr[r]; t ++; r ++; } //然后将中转数组中的数据根据索引,完全转到原始数组中去 t = 0; //中转数组索引归零 int templeft = left; //设置一个变量是从你开始扫描的数据开始的 while (templeft <= right){ arr[templeft] = temp[t]; templeft ++; t ++; } } public static void radixSort(int[] arr){ //获取最大值 int max = arr[0]; for (int i = 1;i < arr.length;i ++){ if(max < arr[i]){ max = arr[i]; } } //获取最大值的位数,从而决定着如同与出桶的次序 int length = (max + "").length(); int[][] bucket = new int[10][arr.length]; //设置十个桶,分别是0-9各个位数,然后设置桶的长度 int[] bucketElementsCount = new int[10]; //设置一个长度为10的数组,专门用来表示桶计数的索引,然后小表就是对应的通的序号 int digit = 0; //获取相应的位数,第一轮获取个位数 for(int i = 0,n = 1;i < length;i ++,n *= 10){ int index = 0; //这个就是原始桶的索引, for(int j = 0;j < arr.length;j ++){ //遍历各个数,然后获取各个数的的值 digit = arr[j] / n % 10; bucket[digit][bucketElementsCount[digit]] = arr[j]; //bucket[桶的序号==对应位数上的值][该放入桶的位置的索引==通的计数器[第几号桶]] bucketElementsCount[digit] ++; //设置索引添加,必须要将索引后移 } //入完桶了,然后开始出桶 //出桶是按照先进先出的队列顺序,所以出桶的时候就得按照从头到尾的顺序 for(int j = 0;j < 10;j ++){ //这个j应该是桶的序号,十个桶,一次次遍历 //遍历至前,确定这个桶是不是空的 if(bucketElementsCount[j] != 0){ //这里是有一个问题,因为桶用过了,索引是归零了,但是桶的内容还是在的 //既然有索引,可以根据索引,索引本来就是显示是否又元素入桶的最佳标志 for (int m = 0;m < bucketElementsCount[j];m ++){ arr[index] = bucket[j][m]; index ++; } } bucketElementsCount[j] = 0; } } } public static void quickSort(int[] arr,int left,int right){ //采用交换的方式,由中间向两边逐渐过渡 int mid = (left + right) / 2; int l = left; int r = right; int pivot = arr[mid]; //设置中间值进行比较,中间值左边的应该比中间值小,中间值右边的应该比中间值大 int temp = 0; //设置中间值进行交换 while (left < right){ //设置递归截至的条件,只要仅仅只剩一个元素,那就跳出循环 while (arr[l] < pivot){ //检测出左边的比pivot大的值 l ++; } while (arr[r] > pivot){ //检测出右边的比pivot小的值 r --; } if (l == r){ //设置两者相同的出口,因为不能有效处理两者相遇的情况 break; } //进行值交换 temp = arr[l]; arr[l] = arr[r]; arr[r] = temp; //针对有好几个值是相同的情况 //交换完了之后,就是说当前元素是满足左边小于中值,右边大于中值的情况 //不满足说明有一边已经到达中值, if (arr[l] == pivot){ r --; } if (arr[r] == pivot){ l ++; } } //对应两者同时交汇于中值的情况设置出口 if(r == l){ r --; l ++; } if (r > left){ //这里是是否包含等于,不过结果都影响不大 //填了等于也没事,交换有个循环判定,有两个元素才能进去,然后再被错开,不满足条件, //就不能继续在填,但是小于更好,一个元素不会再进行一次判定了 quickSort(arr,left,r); } if (l < right){ quickSort(arr,l,right); } } public static void bubblesort(int[] arr){ //冒泡排序比较简单,必将相邻的两个值,由后之前确定顺序 int temp = 0; boolean isFlag = true; for (int i = 0;i < arr.length - 1;i ++){ //大排序小于总数减一,因为是从后往前确定值,随后一个又不要确定 for(int j = 0;j < arr.length - i - 1;j ++){ //每一次都是从头开始比较,尾部元素在一次一次大循环中已经确定不会再变化 //重点会有变化,但是头不变 if(arr[j] < arr[j + 1]){ //按照逆序来的,逆序是从小到大,那么正序就是从大到小 temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp; isFlag = false; } //改良就是如果于此都没有改变循环,那就可以跳出循环,因为已经确定好顺序了,还要再修改干嘛 } if (isFlag){ break; //注意啊,每一次都是比较所有的数字,所以有一次成功,那就跳出循环,没有必要再去比较了 //因为所有的数字都是按照固定顺序排列的 } isFlag = true; //每一次都要把值给重置了,因为每一次都要试试看,万一不用比完,某一次就成功了那 } } public static void selectSort(int[] arr){ //选择排序是每一次都选出最小值,从前往后确定值的排序方法 int min = 0; int minIndex = 0; //无论是选择排序,还是插入排序,在没有确定最值之前都不能改变数组 for(int i = 0;i < arr.length - 1;i ++){ //大排序是从前往后排序,只剩下最后一个值,那就没有必要再排了,所以是-1 min = arr[i]; minIndex = i; //当前循环都是确定当前i对应的最大值和最小值 for (int j = i + 1;j < arr.length;j ++){ //小排序是始于每一次大排序确定的最大值,终于最后一个,所以尾部始终都不变 //i是假设的最大值,所以直接对其下一个进行循环就行了 if (min > arr[j]){ min = arr[j]; minIndex = j; } } if (minIndex != i){ //如果当前循环没有检测到变化,那就没有必要再交换值了,那就是最小值 arr[minIndex] = arr[i]; arr[i] = min; } } } public static void shellSort(int[] arr){ //希尔排序是通过缩小增量来实现分治运算的 int gap ; int insertVal = 0; int insertIndex = 0; for(gap = arr.length / 2;gap > 0;gap /= 2 ){ //gap是决定了大的循环次数, for (int i = gap;i < arr.length;i ++){ //对于插入排序而言,第一个是默认的,要少一个数据长度,不在末尾减,在开头减 insertVal = arr[i]; insertIndex = i - gap; while (insertIndex >= 0 && arr[insertIndex] > insertVal){ arr[insertIndex + gap] = arr[insertIndex]; insertIndex -= gap; } if (insertIndex != i - gap){ arr[insertIndex + gap] = insertVal; } } } } public static void insertSort(int[] arr){ //插入排序是设置了两个组,其中一个是有序的,其中一个是无序的,将无序的插入有序的 int insertVal = 0; int insertIndex = 0; //设置带出入的数据和索引 for(int i = 0;i < arr.length - 1;i ++){ //第一个数据默认是有序数组中的元素,然后不就少了一个吗 insertVal = arr[i + 1]; insertIndex = i; //待插入的值是当前索引的下一个 //待插入的位置是当前索引// //上述方法也行,不过麻烦,建议用while,因为是先判定,在循环,所以更加方便 while (insertIndex >= 0 && arr[insertIndex] > insertVal){ arr[insertIndex + 1] = arr[insertIndex]; insertIndex --; } if (insertIndex != i){ arr[insertIndex + 1] = insertVal; } } } 转载地址：http://zqgpb.baihongyu.com/