排序算法是数据结构中十分基础的内容，本文总结了常用的排序算法的原理和性能，还给出了相关的图解，并且采用java语言实现了算法，最后给了一个面试中实际的例子，以及算法复杂度的比较
最基本的排序算法，原理看图就可以理解：
// 选择排序 public int[] selectsort(int[] arr) { for(int x=0;x<arr.length-1;x++) //最后一个数不用在自己和自己进行比较了，n-1轮 { for(int y=x+1;y<arr.length;y++) { if(arr[x]>arr[y]) { int temp=arr[x]; arr[x]=arr[y]; arr[y]=temp; } } } return arr; }
将当前元素和左边的元素比较，若当前元素小，就交换两者，也就相当于插入
// 插入排序 public int[] insertionSort(int[] arr) { int len = arr.length; for (int i = 1; i < len; i++) { // j表示当前元素的位置，将其和左边的元素比较，若当前元素小，就交换，也就相当于插入 // 这样当前元素位于j-1处，j--来更新当前元素,j一直左移不能越界，因此应该大于0 for(int j=i; j>0 && arr[j]<arr[j-1];j--) { int temp = arr[j]; // 元素交换 arr[j] = arr[j-1]; arr[j-1] = temp; } } return arr; }
相邻的两个元素进行比较，如果符合条件就换位，这样第一轮，最大的数会在最后面，长度在依次递减
// 冒泡排序 public int[] bubbleSort(int[] arr) { int len = arr.length; for (int i = 0; i < len - 1; i++) { for (int j = 0; j < len - 1 - i; j++) { if (arr[j] > arr[j+1]) { // 相邻元素两两对比 int temp = arr[j+1]; // 元素交换 arr[j+1] = arr[j]; arr[j] = temp; } } } return arr; }
/** * 将数组的某一段元素进行划分，小的在左边，大的在右边 */ public static int divide(int[] a, int start, int end){ //每次都以最右边的元素作为基准值 int base = a[end]; //start一旦等于end，就说明左右两个指针合并到了同一位置，可以结束此轮循环。 while(start < end){ while(start < end && a[start] <= base) //从左边开始遍历，如果比基准值小，就继续向右走 start++; //上面的while循环结束时，就说明当前的a[start]的值比基准值大，应与基准值进行交换 if(start < end){ //交换 int temp = a[start]; a[start] = a[end]; a[end] = temp; //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值右边)，因此右边也要同时向前移动一位 end--; } while(start < end && a[end] >= base) //从右边开始遍历，如果比基准值大，就继续向左走 end--; //上面的while循环结束时，就说明当前的a[end]的值比基准值小，应与基准值进行交换 if(start < end){ //交换 int temp = a[start]; a[start] = a[end]; a[end] = temp; //交换后，此时的那个被调换的值也同时调到了正确的位置(基准值左边)，因此左边也要同时向后移动一位 start++; } } //这里返回start或者end皆可，此时的start和end都为基准值所在的位置 return end; } /** * 排序 */ public static void sort(int[] a, int start, int end){ if(start > end){ //如果只有一个元素，就不用再排下去了 return; } else{ //如果不止一个元素，继续划分两边递归排序下去 int partition = divide(a, start, end); sort(a, start, partition-1); sort(a, partition+1, end); } }
治的最后过程举例
package cn; import java.util.Arrays; // 归并排序 public class MergeSort { public static void main(String []args) { int []arr = {9,8,7,6,5,4,3,2,1}; sort(arr,0,8); System.out.println(Arrays.toString(arr)); } private static void sort(int[] arr,int start,int end) { if(start<end) { int mid = (start+end)/2; sort(arr,start,mid);//左边归并排序，使得左子序列有序 sort(arr,mid+1,end);//右边归并排序，使得右子序列有序 merge(arr,start,mid,mid+1,end);//将两个有序子数组合并操作 } } private static void merge(int[] arr,int start1,int end1,int start2,int end2) { // 建立辅助数组 int len=end2-start1+1; int[] temp=new int[len]; int i = start1;//左序列指针 int j = start2;//右序列指针 int t = 0;//临时数组指针 while (i<=end1 && j<=end2) { // 将小的放入辅助数组 if(arr[i]<=arr[j]) { temp[t++] = arr[i++]; }else { temp[t++] = arr[j++]; } } //若左序列此时还有有剩余的，将左边剩余元素填充进temp中 while(i<=end1) { temp[t++] = arr[i++]; } //若右序列此时还有有剩余的，将右序列剩余元素填充进temp中 while(j<=end2) { temp[t++] = arr[j++]; } t = 0; //将temp中的元素全部拷贝到原数组中 while(start1 <= end2){ arr[start1++] = temp[t++]; } } }
结果
[1, 2, 3, 4, 5, 6, 7, 8, 9]
堆排序是利用堆这种数据结构而设计的一种排序算法，堆排序是一种选择排序，它的最坏，最好，平均时间复杂度均为O(nlogn)，它也是不稳定排序。首先简单了解下堆结构。堆是具有以下性质的完全二叉树：每个结点的值都大于或等于其左右孩子结点的值，称为大顶堆；或者每个结点的值都小于或等于其左右孩子结点的值，称为小顶堆。如下图： 父节点比较大的是大顶堆，父节点比较小的是小顶堆 堆排序基本思想及步骤 堆排序的基本思想是：将待排序序列构造成一个大顶堆，此时，整个序列的最大值就是堆顶的根节点。 将最大值放到末尾（最大值和末尾元素交换），此时末尾就为最大值。 然后将剩余n-1个元素重新构造成一个堆，这样会得到n个元素的次小值。如此反复执行，便能得到一个有序序列了. 再简单总结下堆排序的基本思路： a.将无需序列构建成一个堆，根据升序降序需求选择大顶堆或小顶堆; b.将堆顶元素与末尾元素交换，将最大元素”沉”到数组末端; c.重新调整结构，使其满足堆定义，然后继续交换堆顶元素与当前末尾元素，反复执行调整+交换步骤，直到整个序列有序。
package cn; import java.util.Arrays; /* * 堆排序demo */ public class HeapSort { public static void main(String []args) { int []arr = {1,7,2,9,3,8,6,5,4}; 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--) { //从最后一个一个非叶子结点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) { //i是父节点 while(2*i+1<length) { // k是子节点 int k=i*2+1; //从i结点的左子结点开始，也就是2i+1处开始，使得k指向i的左右子节点中较大的一个 // 如果不存在右子节点，就不用比较了 if(k+1<length && arr[k]<arr[k+1]) { //如果左子结点小于右子结点，k指向右子结点 k++; } // 比较该较大节点与父节点 if(arr[k] <arr[i]) break; //如果子节点大于父节点，将子节点和父节点交换 swap(arr,i,k); // 更新父节点，调整下面的子树 i = k; } } /* * 交换元素 */ public static void swap(int []arr,int a ,int b) { int temp=arr[a]; arr[a] = arr[b]; arr[b] = temp; } }
结果： [1, 2, 3, 4, 5, 6, 7, 8, 9]
希尔排序为了加快速度简单地改进了插入排序。 使数组中任意间隔为gap的元素都是有序的。下图中gap=4：
package cn; import java.util.Arrays; /* *希尔排序 */ public class ShellSort { public static void main(String []args){ int []arr ={1,4,2,7,9,8,3,6}; sort(arr); System.out.println(Arrays.toString(arr)); } public static void sort(int [] arr) { //确定初始的增量gap，保证其不能越界 int gap=1; while(gap<arr.length/3) gap=3*gap+1; // 对于相隔gap的元素进行插入排序 while(gap>=1) { for(int i=gap;i<arr.length;i++) { for(int j=i;j>=gap && arr[j]<arr[j-gap]; j-=gap) swap(arr,j,j-gap); } gap=gap/3; } } /* * 交换数组元素 */ public static void swap(int []arr,int a,int b){ arr[a] = arr[a]+arr[b]; arr[b] = arr[a]-arr[b]; arr[a] = arr[a]-arr[b]; } }
结果： [1, 2, 3, 4, 6, 7, 8, 9]
对于公司中所有员工的年龄进行排序，员工大概有几万人，要求时间效率是o(n),可以使用辅助空间但是不能超过O（n）
package cn; import java.util.Arrays; public class SortAges { public static void SortAges(int ages[],int length) { if(ages==null || length<=0) return; // 存放各个年龄出现的次数，年龄范围是0-99,初始值全都是0 int[] timesOfAge=new int[100]; for(int i=0;i<=99;i++) { timesOfAge[i]=0; } // 遍历数组，统计次数 for(int i=0;i<length;i++) { int age=ages[i]; if(age<0||age>99) throw new RuntimeException(); timesOfAge[age]++; } // 年龄排序一定是0 1 2、、99这种，关键在于需要设置几次，遍历所有年龄，该年龄出现几次，就在ages数组中写几次该年龄 int index=0; for(int i=0;i<=99;i++) { for(int j=0;j<timesOfAge[i];j++) { ages[index]=i; index++; } } } public static void main(String[] args) { // TODO Auto-generated method stub int[] arr={1,3,3,44,5,6,55,55,55}; SortAges(arr,9); System.out.println(Arrays.toString(arr)); } }
结果： [1, 3, 3, 5, 6, 44, 55, 55, 55]
原文链接：https://blog.csdn.net/wang18741337665/article/details/82120413
