一排序的概念排序是算法面试的“基本功”也是很多复杂算法的基础。这篇文章精选了经典排序算法从最直观的暴力排序到高效的递归分治循序渐进带你彻底吃透排序的核心思想。每部分都会讲清楚思路是什么 → 代码怎么写 → 时间复杂度多少。排序有四大概念排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。内部排序:数据元素全部放在内存中的排序外部排序数据元素太多不能同时放在内存中根据排序过程的要求需要在内外存之间移动数据的排序。二基于比较类的排序2.1插入排序2.1.1直接插入排序基本思想其实就是把待排序的记录按照其关键码值的大小逐个插入到一个已经排好序的有序序列里。现实生活中玩扑克牌时就用到了插入思想定义一个临时变量temp每次将i下标的值赋给temp就相当于我们在整理扑克的时候手拿起来的那张这张之前的依次与这张作比较然后排序时间复杂度O(n²空间复杂度O(1)稳定性稳定public static void insertSortzi(int[] array){ for (int i 1; i array.length ; i) { int ji-1; int temparray[i]; for (; j 0; j--) { if(array[j]temp){ array[j]array[j1]; }else{ array[j1]temp; break; } } array[j1]temp; } }2.1.2希尔排序希尔排序法又称缩小增量法。希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成多个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。然后取重复上述分组和排序的工作。当到达1时所有记录在统一组内排好序gap为数组长度/2根据gap将数组分组每组进行大小比较排序。希尔排序是对直接插入排序的优化时间复杂度不固定不同的增量序列决定了分组的策略和排序的效率空间复杂度O(1)稳定性不稳定public static void shellSortzi(int[] array){ int gap array.length; while(gap1){ gap/2; shellzi(array,gap); } } private static void shellzi(int[] array, int gap) { for (int i gap; i array.length; i) { int ji-gap; int temparray[i]; for (; j 0;j-gap) { if(array[j]temp){ array[jgap]array[j]; }else{ array[jgap]temp; break; } } //此时j走到-1位置了 array[jgap]temp; } }2.2选择排序2.2.1直接选择排序每次从待排序的数据元素选出最小或最大的一个元素存放在有序序列的位置直到全部排完时间复杂度O(n²空间复杂度O(1)稳定性不稳定public static void selectSort(int[] array) { // 1. 外循环i 表示当前要确定的位置也是未排序部分的起点 // 注意i array.length - 1因为最后一个元素不用再比了 for (int i 0; i array.length - 1; i) { // 2. 先假设 i 位置的值是最小的 int minIndex i; // 3. 内循环只在【未排序部分】找真正的最小值 for (int j i 1; j array.length; j) { if (array[j] array[minIndex]) { minIndex j; // 记录真正最小值的下标 } } // 4. 将找到的最小值交换到 i 位置 swap(array, i, minIndex); } } private static void swap(int[] array, int i, int j) { int temp array[i]; array[i] array[j]; array[j] temp; }2.2.2堆排序堆排序是指利用堆的这种数据结构来设计的一种排序需要注意的是排升序用大根堆排降序用小根堆创建升序排序就是先创建一个大根堆再将大根堆的堆顶元素一个一个搬到末尾搬一次就重新调整为一个大根堆。以此类推。时间复杂度O(NlogN空间复杂度O(1)稳定性不稳定public static void heapSort(int[] array){ //把大根堆的根最大值一个一个地‘搬’到数组末尾搬完就排好序了。” //先创建堆大根堆 要从小到大排序反过来排 createHeap(array); int end array.length-1; while(end0){ swap(array,0,end); //相当于搬完一轮调整为大根堆 然后继续搬以此类推 siftDown(array,0,end); end--; } } public static void createHeap(int[] array){ for (int parent (array.length-1-1)/2; parent 0 ; parent--) { siftDown(array,parent,array.length); } } public static void siftDown(int[] array,int parent,int length){ int childparent*21; while(childlength){ //找出最大孩子 if(child1lengtharray[child]array[child1]){ child; } if(array[child]array[parent]){ swap(array,parent,child); parentchild; childparent*21; }else{ break; } } }2.3交换排序基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动2.3.1冒泡排序冒泡排序是一种非常容易理解的排序flag记录这一轮有没有发生过交换。如果某一轮从头比到尾一次交换都没发生说明数组已经完全有序直接break结束不用再继续了。时间复杂度O(N²)空间复杂度O(1)稳定性稳定public static void bubbleSort(int[] array){ for (int i 0; i array.length-1; i) { boolean flagfalse; //因为要拿j和j1比较所以j array.length-1-i for (int j 0; j array.length-1-i; j) { if(array[j]array[j1]){ swap(array,j,j1); flagtrue; } } if(!flag){ break; } } }2.3.2快速排序其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。public static void quickSort(int[] array){ quick(array,0, array.length-1); } public static void quick(int[] array,int start,int end){ if(startend) return; int pivotpartiton(array,start,end); quick(array,start,pivot-1); quick(array,pivot1 ,end); } private static int partiton(int[] array, int left, int right) { //找到最新的基准 int temparray[left]; int tempLeftleft; while(leftright){ //右边找比基准小的停下来先从右往左找 while(leftrightarray[right]temp){ right--; } //左边找比基准大的停下来 while (leftrightarray[left]temp){ left; } swap(array,left,right); } //相遇了 把一开始的基准换一下 swap(array,left,tempLeft); return left; }还有一种方法是挖坑法为什么先从右边开始找呢答案非常直接因为基准值pivot选在了最左边array[left]。既然最左边被挖成了“坑”那这个坑里是空的等着别人来填。所以你必须先从右边找一个比基准小的数拿过来填这个坑。这是逻辑上的必然顺序。快速排序可以看做二叉树时间复杂度最好O(N*logN) 最坏O(n^2)空间复杂度最好O(LOGN) 最坏O(N)稳定性不稳定private static int partitonwakeng(int[] array, int left, int right) { int temparray[left]; while(leftright){ //右边找比基准小的停下来先从右往左找 while(leftrightarray[right]temp){ right--; } array[left]array[right]; //左边找比基准大的停下来 while (leftrightarray[left]temp){ left; } array[right]array[left]; } //相遇了 把一开始的基准换一下 array[left]temp; return left; }2.3.3快速排序优化快速排序的优化用的是三数取中这里的中是指不大不小的那个数而不是中位数法给你三个数分别在下标left、mid、right上这个方法不改变数组只是帮你找出这三个数中值排在中间的那个数的下标。快排最怕什么最怕每次选的基准都是最大值或最小值导致树变高复杂度变 O(n²)。private static int getMiddleNum(int[] array,int left,int right) { int mid (leftright)/2; if(array[left] array[right]) { if(array[mid] array[left]) { return left; }else if(array[mid] array[right]) { return right; }else { return mid; } }else { if(array[mid] array[left]) { return left; }else if(array[mid] array[right]) { return right; }else { return mid; } } }2.4归并排序归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。每次合并都要开辟相同大小的临时数组用来存放排序之后的数据元素时间复杂度O(N*logN)空间复杂度O(N)稳定性稳定public static void mergeSort(int[] array){ mergeSortTemp(array,0,array.length-1); } private static void mergeSortTemp(int[] array, int left, int right) { //归并归并 先归分解后并 if(leftright) return; int mid(leftright)/2; mergeSortTemp(array,left,mid); mergeSortTemp(array,mid1,right); //走到这里全部分解完毕 //合并 merge(array,left,mid,right); } private static void merge(int[] array, int left, int mid, int right) { //每次合并都要开辟相同元素大小的临时数组 int[] tempnew int[right-left1]; int k0; int s1left; int s2mid1; while(s1mids2right){ if(array[s1]array[s2]){ temp[k]array[s1]; }else{ temp[k]array[s2]; } } while(s1mid){ temp[k]array[s1]; } while (s2 right) { temp[k] array[s2]; } //可以保证tmp数组 是有序的 for (int i 0; i k; i) { array[ileft] temp[i]; } } }三排序总览