排序算法的分类
时间复杂度以及空间复杂度
注：为了进行一定的比较，此处不按照上面的顺序。
直接插入排序
基本思想
在要排序的一组数中，假定前n-1个数已经排好序，现在将第n个数插到前面的有序数列中，使得这n个数也是排好顺序的。如此反复循环，直到全部排好顺序。
场景：
正如当我们打牌的时候，需要对扑克牌排序。抽到牌后(假设每次只抽一张)，依次从排好序的排中与手中的牌进行比较，插入到合适的位置。
/** * 插入排序 * @param a */ public static void sort(int[] a){ int N = a.length; //i需要取到N-1，并且这里的i是从1开始的，可以这么认为第一个就是一个初始的有序的数组 for (int i=1;i<N;i++){ for (int j=i;j>0;j--){ if ((a[j-1]<a[j])){ continue; } int tem = a[j-1]; a[j-1] = a[j]; a[j] = tem; } } }
/** * 插入排序 * @param a 排序数组 */ public static void sort(Comparable[] a){ //将a[] 按升序排序 int N = a.length; for (int i=1; i<N;i++){//i需要取到N-1 //将a[i]插入到a[i-1],a[i-2],a[i-3]...之中 for (int j = i; j>0&& Example.more(a[j-1],a[j]); j--){//Example.less(a[j-1],a[j]) Example.exch(a,j,j-1); } } }
时间复杂度与空间复杂度
因为是内部排序所以空间复杂度可以直接不考虑就是0(1)，我们来看时间复杂度：主要体现在比较所花的时间上，最坏的情况下就是：0+1+ 2 + 3 +…+(n-1)=(n-1)*n/2=0(n2)。
最坏情况：数组已经排序好，但是从大到小的排序，此时每次的比较后都需要交换
最好情况：这个当然就是已经排序好了（从小到大）
选择排序
基本思想：
在长度为N的无序数组中，
第一次遍历n-1个数，找到最小的数值与第一个元素交换；
第二次遍历n-2个数，找到最小的数值与第二个元素交换；
。。。
第n-1次遍历，找到最小的数值与第n-1个元素交换，排序完成
场景：上一个场景中是抽到一张牌后插入到手中已经排好序的手牌之中。而选择排序有点不同，它是从没有排序的牌中选取到最小的放入已排序的末尾。
/** * 选择排序 * @param a 需要排序的数组 */ public static void sort(int[] a){ int N = a.length; //这里是从0开始的，因为后续的操作如果需要的话会对下标为0的位置进行赋值操作 for (int i=0;i<N-1;i++){ int min = i; for (int j=i+1;j<N;j++){ if (a[i]<a[j]){ min = j; continue; } int tem = a[i]; //将交换放到if外面 a[i] = a[j]; a[j] = tem; } } }
public static void sort(Comparable[] a){ //将a[]按升序排序 int N = a.length; for (int i=0;i<N-1;i++){ //书中这里是for (int i=0;i<N;i++) 考虑边界这里只需要执行到a.length-2就可以了 //将a[i]和a[i+1..N]中最小的元素交换 int min = i; for (int j=i+1;j<N;j++){ if (Example.more(a[min],a[j])) {//书中这里为：Example.less(a[j],a[min]) min = j; } } Example.exch(a,i,min); } }
空间复杂度：0(1)，内部排序
时间复杂度：0(n2)主要体现在
最坏情况：以排好序（从大到小）
最好情况：以排序好（从小到大）
直接插入排序与选择排序的可视比较：
希尔排序
也称递减增量排序算法，是插入排序的一种更高效的改进版本。希尔排序是非稳定排序算法。
排序思想：在要排序的一组数中，根据某一增量分为若干子序列，并对子序列分别进行插入排序。
然后逐渐将增量减小,并重复上述过程。直至增量为1,此时数据序列基本有序,最后进行插入排序。
public static void sort(int a[]){ int N = a.length; int h = 1; while (h<N/3){ //获取递增序列 h=3*h+1;//1,4,13,40,121,.... } while (h>=1){ // 将数组变为任意间隔h的元素都是有序的（h有序数组） for (int i = h;i<N;i++){ //将a[i] 插入到a[i-h],a[i-2*h],a[i-3*h]...之中 for (int j=i;j >= h;j-=h){ if (a[j]<a[j-h]){ int tem = a[j-h]; a[j-h] = a[j]; a[j]=tem; } } } h = h/3; } }
public static void sort(Comparable[] a){ int N = a.length; int h = 1; while (h<N/3){ //获取递增序列 h=3*h+1;//1,4,13,40,121,.... } while (h>=1) { // 将数组变为任意间隔h的元素都是有序的（h有序数组） for (int i = h; i < N; i++) { //将a[i] 插入到a[i-h],a[i-2*h],a[i-3*h]...之中 for (int j=i;j >= h&& Example.more(a[j-h],a[j]);j-=h){ Example.exch(a,j-h,j); } } h=h/3; } }
空间复杂度：0(1)，内部排序
时间复杂度： O(n^(1.3—2))
最坏情况：
最好情况：
归并排序
归并：将两个有序的数组归并成一个更大的有序数组。根据这个操作就得到了递归排序算法：归并排序。
原理：要将一个数组排序，可以先（递归的）将它分成两半分别排序，然后归并起来。
归并最吸引人的性质就是它能够保证任意长度为N的数组排序所需要时间和NlogN成正比：主要缺点则是它所需要的额外空间和N成正比。
代码：
public class MergeSort { public static void mergerSort(int[] array){ mergerSort(array,0,array.length-1); } /** * 实现归并排序的具体思路 * 递归每个数组并排序的过程 * @param array * @param low * @param hight */ private static void mergerSort(int[] array, int low, int hight) { int mid = low +(hight - low) /2; if (low<hight) { //处理左边 mergerSort(array, low, mid); // 处理右边 mergerSort(array, mid + 1, hight); // 归并 merger(array, mid, low, hight); } } /** * 将两个有序数组进行归并 * @param array 待排序的数组 * @param middle 中间的位置 * @param low 起始的位置 * @param hight 结束的位置 */ private static void merger(int[] array, int middle, int low, int hight) { int j = middle+1; int[] temp = new int[array.length]; int tIndex = low,cIndex = low; // 核心代码，完成比较 while (low <= middle && j <= hight) { if(array[low] < array[j]){ temp[tIndex++] = array[low++]; }else{ temp[tIndex++] = array[j++]; } } // 将未归并完的数组来进行添加 while(low <= middle){ temp[tIndex++] = array[low++]; } while (j <= hight){ temp[tIndex++] = array[j++]; } // 将排序好数组赋值给原数组 while (cIndex <= hight) { array[cIndex] = temp[cIndex]; cIndex++; } } public static void main(String[] args) { int b[] = {1,4,2,8,5,3,0,12,3,2,7,3}; mergerSort(b); for (int s:b){ System.out.print(" "+s); } } }
快速排序
快速排序是一种分治的排序算法。它将一个数组分为两个数组，两部分独立的排序。快速排序与归并排序是互补的：归并排序将数组分为两个子数组分别排序，并将有序的子数组归并以将整个数组排序；而快速排序将数组排序的方式则是当两个数组都有序时整个数组也就自然有序了。在第一种情况中，递归调用发生在处理整个数组之前；在第二种情况中，递归调用发生在处理整个数组之后。在归并排序中，一个数组被分为两半；在快速排序中，切分的位置取决于数组的内容。
该方法的基本思想：
- 1．先从数列中取出一个数作为基准数。
- 2．分区过程，将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
- 3．再对左右区间重复第二步，直到各区间只有一个数。
public class QuickSort { public static void sort(int[] arr){ quickSort(arr,0,arr.length-1); } public static void quickSort(int[] arr,int start,int end){ if(start<end){ //把数组中的第0个数字作为标准数 int stard = arr[start]; //记录需要排序的下标 int low = start; int high = end; //循环找比标准数大的数和比标准数小的数 while(low<high){ //右边的数字比标准数大 while(low<high && stard<=arr[high]){ high--; } //使用右边的数字替换左边的数 arr[low] = arr[high]; //如果左边的数字比标准数小 while(low<high && arr[low]<=stard){ low++; } arr[high] = arr[low]; } //把标准数赋给low所在位置的元素(low或high都可以，因为它们两个都重复了) arr[low] = stard; //处理所有的小于标准数的左边的数字 quickSort(arr, start, low); //处理所有的大于标准数的右边的数字 quickSort(arr, low+1, end); } } public static void main(String[] args) { int[] arr = new int[]{3,4,6,7,2,7,2,8,0,9,1}; sort(arr); System.out.println(Arrays.toString(arr)); } }
堆排序
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种**选择排序，**它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。
这种逻辑结构映射到数组中就是下面这个样子
public class HeapSort { 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)); } 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);//重新对堆进行调整 } } /** * 调整大顶堆（仅是调整过程，建立在大顶堆已构建的基础上） */ 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; }else{ break; } } arr[i] = temp;//将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 BubbleSort(int[] arr) { for (int i = 1; i < arr.length ; i++) {//排序需要的趟数。 for (int j = 0; j < arr.length - i ; j++) {// if(arr[j + 1] < arr[j]) { int tem = arr[j + 1]; arr[j + 1] = arr[j]; arr[j] = tem; } } } }
基数排序
基本思想：将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后,数列就变成一个有序序列。
算法步骤：
- 将所有待比较数值（正整数）统一为同样的数位长度，数位较短的数前面补零。
- 从最低位开始，依次进行一次排序。
- 这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
动态效果示意图：
/** * 基数排序 */ public class RadixSort { public static void main(String[] args) { int a[] = {1,4,2,8,5,3,0,12,100,3,2,7,3}; sort(a,100); for (Integer i:a){ System.out.print(" "+i); } System.out.println(); } /** * 基数排序 * @param array 待排序数组 * @param d 最高位数 */ public static void sort(int[] array,int d) { int n=1;//代表位数对应的数：1,10,100... int k=0;//保存每一位排序后的结果用于下一位的排序输入 int length=array.length; int [][]bucket=new int[10][length];//排序桶用于保存每次排序后的结果，这一位上排序结果相同的数字放在同一个桶里 int []order=new int[length];//用于保存每个桶里有多少个数字 while(n<=d) { for(int num:array) //将数组array里的每个数字放在相应的桶里 { int digit=(num/n)%10;//计算单位 0-9 bucket[digit][order[digit]]=num; order[digit]++; } for(int i=0;i<length;i++)//将前一个循环生成的桶里的数据覆盖到原数组中用于保存这一位的排序结果 { if(order[i]!=0)//这个桶里有数据，从上到下遍历这个桶并将数据保存到原数组中 { for(int j=0;j<order[i];j++) { array[k]=bucket[i][j]; k++; } } order[i]=0;//将桶里计数器置0，用于下一次位排序 } n*=10; k=0;//将k置0，用于下一轮保存位排序结果 } } }
参考：
https://www.jianshu.com/p/8340dfaea3af
算法（第四版）
工具类：
package utils; /** * TODO 类描述 * * @author qijian. * @date 2021/7/21 21:18 */ public class Example { /** * 对传进来的两个参数进行比肩 第一个参数更大返回1，更小返回-1，相等返回0 * @param v 需比较的参数 * @param w 需比较的参数 * @return v比w大返回1，小返回-1，相等返回0 */ public static boolean more(Comparable v, Comparable w) { //compareTo：v比w大返回1，小返回-1，相等返回0 return v.compareTo(w) > 0;//算法（第四版）这里是v.compareTo(w) < 0，我觉得这里用>更合适并且把方法签名改为了more } /** * 数组内两数交换 * @param a 数组 * @param i 数组下标 * @param j 数组下标 */ public static void exch(Comparable[] a, int i, int j) { Comparable t = a[i]; a[i] = a[j]; a[j] = t; } public static void show(Comparable[] a) { for(int i = 0; i<a.length; i++) { System.out.print(a[i] + " "); } } public static boolean isSorted(Comparable[] a) { for(int i = 1; i < a.length; i++) { if(less(a[i],a [i-1])) return false; } return false; } }
import java.util.Arrays; /** * TODO 类描述 * * @author qijian. * @date 2021/7/22 8:58 */ public class ui { /** * 打印整个数组 * @param a 数组 */ public static void print(int []a) { for(int i = 0;i<a.length;i++) { System.out.print(a[i]+" "); } System.out.println(); } /** * 打印数组排序中的某趟顺序 * @param a 数组 * @param k 趟数 */ public static void process(int []a,int k) { System.out.println("第"+k+"躺:"+ Arrays.toString(a)); } }
return false; }
```java import java.util.Arrays; /** * TODO 类描述 * * @author qijian. * @date 2021/7/22 8:58 */ public class ui { /** * 打印整个数组 * @param a 数组 */ public static void print(int []a) { for(int i = 0;i<a.length;i++) { System.out.print(a[i]+" "); } System.out.println(); } /** * 打印数组排序中的某趟顺序 * @param a 数组 * @param k 趟数 */ public static void process(int []a,int k) { System.out.println("第"+k+"躺:"+ Arrays.toString(a)); } }
