网站中常用的功能模块,怎么注销网站查备案,中企动力是做什么的公司,WordPress做的网站源代码排序简介常见排序算法插入排序直接插入排序希尔排序 选择排序选择排序堆排序 交换排序冒泡排序快速排序hoare版挖坑法前后指针法非递归实现快排优化 归并排序非递归实现归并排序海量数据排序问题 基数排序#xff08;不用比较就能够排序#xff09;桶排序计数排序#xff08… 排序简介常见排序算法插入排序直接插入排序希尔排序 选择排序选择排序堆排序 交换排序冒泡排序快速排序hoare版挖坑法前后指针法非递归实现快排优化 归并排序非递归实现归并排序海量数据排序问题 基数排序不用比较就能够排序桶排序计数排序场景在数据指定范围内范围小数据集中的情况下总结 排序简介
排序如果没有特殊说明我们目前是按从小到大的排序 稳定排序假设A3、B2、C3、D4排序后的结果是BACD。A和C值相同它们排序前后的顺序是不变的。 概念稳定排序是指对于待排序序列中相等元素的相对位置保持不变的排序算法。换句话说如果一个排序算法在排序过程中能保持两个相等元素的相对顺序不变那么这个算法就可称为稳定排序算法。这个算法能实现相等的时候不交互位置那么就是稳定排序。一个本身就稳定的排序可以实现为不稳定的排序。但是一个本身就不稳定的排序 不能实现为稳定的排序
内部排序数据元素全部放在内存中的排序 外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序
常见排序算法
插入排序
直接插入排序 1开始只有一个5然后定义i下标为1第一个位置已经有序 然后我们要插入4这个元素定义j下标为0 第一次是5一个元素有序第2次就把4拉进来排序第三次把3也拉进来排序一次拉一个跟插入元素排序一样54321 逆序的情况是很头疼的每一个都要交换 2前面和后面比较如果前面大于后面交换位置然后再往前比较直到前面小于这个要插入的值就把他放进去 如果前面小于后面则不做什么i和j往后走也不需要往前走因为前面已经有序了 代码实现
import java.lang.reflect.Array;
import java.util.Arrays;public class Sort {public static void main(String[] args) {int []arr{3,5,1,4,2};System.out.println(Arrays.toString(insertSort(arr)));}//插入排序public static int[] insertSort(int [] array){int i1;for (; i array.length-1 ; i) {int tmparray[i];int ji-1;while (j0){if(array[j]tmp){//进行交换位置array[j1]array[j];//这里一定得是j1;不能是i。因为j是会往前走的array[j]tmp;}else {break;}j--;}// array[j1]tmp; 这行代码和前面if里的array[j]tmp;可以选其1即可。前面的写法是每比较一个就把tmp放进去交换一个次。后面的写法是最后交互完成了才把这个tmp放进去}return array;}}}接下来的排序都得分析这三个东西 时间复杂度最坏情况下ON^2 公式12…(n-1)n*(n-1)/2 .最好情况On顺序情况 空间复杂度 O1 没开辟额外新空间浪费用完一次循环就回收 稳定性 非常稳定 {if(array[j] tmp)就是我们这里不能加等号如果等了就不稳定;但是稳定的排序也是可以实现为不稳定的形式
希尔排序
比较适用于比较逆序的插入排序也是插入排序一种。比如中间间隔5个步数分一组处理逆序的极端情况有特殊作用。每一次gap都是一个插入排序当gap1时就是全体的直接插入排序 问题在于但是这是一个复杂的过程不知道改分几组几次结束。所以我们实现一下gap5然后等于2最后到1 ji-gap;这样子就一组数据包含着gap个元素i每次1而不是2这样子能够一遍走完就完事。 j要从0开始那么就得i下标从gap开始ji-gap 排序过程如果后面的大tmparray [ j ]; array [ jgap]tmp 交换; array [ jgap]array [ j ]array [ j ]tmp //希尔排序public static void shellSort(int [] array){int gaparray.length;while (gap1){gapgap/2;System.out.println(Arrays.toString(shell(array, gap)));}}public static int[] shell(int[] array, int gap) {//关键在于i不再是1而是gapint igap;for (; i array.length-1 ; i) {int tmparray[i];int ji-1;while (j0){if(array[j]tmp){//进行交换位置array[jgap]array[j];//这里注意隔gpa个位置交换array[j]tmp;}else {break;}j--;}// array[jgap]tmp; 这行代码}return array;}希尔和插入在逆序的情况下差距还是很大的 时间复杂度是真不确定你不知道要进行几次隔空交换gap1就是普通的插入排序。但是这一次的插入排序是比较有序的 最坏情况下它的时间复杂度为O(n2)记一个On1.3。 空间复杂度O(1) 不稳定排序跳跃式分组两个相同的数位置会改变
选择排序
选择排序
每次从待排序的元素中挑选一个最小或者最大的放起始位置直到全部元素有序
逻辑用i下标遍历数组mindex储存最小值的下标。j从i的后一个开始遍历遇到比mindex就更新这个值最后遍历完交换i和mindex下标的值
时间复杂度O(n^2) 空间复杂度O(1) 稳定性不稳定 //选择排序public static void selectSort(int []array){for (int i 0; i array.length; i) {int minarray[i];int minIndexi;int ji1;for (ji1; j array.length; j) {if(array[j]array[minIndex]){minarray[j];minIndexj;}}array[minIndex]array[i];array[i]min; //不管你改变改变反正我这个位置都是放最小值和下标}}优化思路定义left往后走right后往前走第一次过去就记录下最小和最大值。随后交换位置直到它们相遇就结束循环 注意细节1最小和最大值在下一次循环得重置2如果最大值在开头呢和left相等这种情况特殊针对一下不然你把最大值换走了我去哪找最大值。 //优化选择排序public static void selectSort1(int []array){int left0;int rightarray.length-1;while (leftright){int minIndex0;int maxIndex0;for (int j left1; j right ; j) {//找到最大、最小值下标if(array[j]array[minIndex]){minIndexj;}if(array[j]array[maxIndex]){maxIndexj;}}//交换位置swap(array,minIndex,left);//需要注意当最大值是第一个下标的时候你得记录一下不然不知道换哪去了if(maxIndexleft){maxIndexminIndex;//之所以等于minIndex因为最大已经被上面的交换过来了}swap(array,maxIndex,right);left;right--;}}public static void swap(int[]array,int maxIndex,int index){int maxarray[maxIndex];array[maxIndex]array[index];array[index]max;}
堆排序
如果要排序一组数从小到大让下标有序 使用小堆这是不可能实现的每次弹出最小的没有问题但是放到哪去如果放别的地方空间复杂度就变大了但是小堆你也不一定就有序左右谁大谁小不知道。 使用大堆每次堆顶和最后一个交换。然后它再自动的排序好大堆。然后我们就不能包含这个最后的元素。交换位置由最后一个元素往前走一步(反之排序建立小堆)我都不用弹出处理交换直接在原来数组交换。换完排序就好了。所以这才叫堆排序。 代码 建堆这部分知识在文章优先级队列会有详细的介绍
//建堆public class TestHeap {public int[] elem;public int usedSize;//有效的数据个数public static final int DEFAULT_SIZE 10;public TestHeap() {elem new int[DEFAULT_SIZE];}public void initElem(int[] array) {for (int i 0; i array.length; i) {elem[i] array[i];usedSize;}}/*** 时间复杂度O(n)*/public void createHeap() {for (int parent (usedSize - 1 - 1) / 2; parent 0; parent--) {//统一的调整方案shiftDown(parent, usedSize);}}private void shiftDown(int parent, int len) {int child 2 * parent 1;//1. 必须保证有左孩子while (child len) {//child1 len 保证有右孩子if (child 1 len elem[child] elem[child 1]) {child;}//child下标 一定是左右孩子 最大值的下标/* if(elem[child] elem[child1] child1 len ) {child;}*/if (elem[child] elem[parent]) {int tmp elem[child];elem[child] elem[parent];elem[parent] tmp;parent child;child 2 * parent 1;} else {break;}}}//堆排序public void heapSort(int []array){int usedSizearray.length;//usedSize是有效元素个数int endusedSize-1;while (end0){//交换0位置和最后的位置最后的位置放最大值每次往前走int tmpelem[0];elem[0]elem[end];elem[end]tmp;shiftDown(0,end);end--;//end传的是数组元素下标10个元素我减1。是不是只调整9个元素。每次结束就少一个元素调整end--}}
时间复杂度建立堆的复杂度On On Onlogn约等于Onlogn 空间复杂度O1没有浪费创建额外的空间
交换排序
冒泡排序
外循环遍历一遍内循环遍历两两之间如果前一个元素比后一个元素大就交互位置。这样子每一轮下来就把最大值放到最后面。而后面放好的最大值元素就无需在下一次继续比较。所以循环条件是 j array.length-1-i //冒泡排序public static void bubbleSort(int []array){for (int i 0; i array.length-1 ; i) {for (int j 0; j array.length-1-i ; j) {//之所以要减i因为遍历了i次后面的i个元素已经是最大的排好序if(array[j]array[j1]){swap(array,j,j1);}}}}时间复杂度On^2 优化后最好On 空间复杂度O1 稳定性稳定
快速排序
hoare版
逻辑先定义一个pivot 把最开头的6放到里面。。然后从后面往前出发找到比pivor小的数这时候前面往后走找到比pivot大的数。两个交换。 换完之后继续从后面那个往前找比6小找到就前面继续往后找比6大的然后交换。。直到相遇把相遇的东西值放到第一个位置再把这个6放到这个相遇的位置。看图说话 代码实现 代码框架 partition实现
//快排private static void quick(int[] array,int start,int end) {if(start end) {//问题1这里能不能不写大于号呢预防没有左边或者右边情况//假设第一次就是有序的情况下start和end都直到最开始的位置相遇再往下走的 quick(array,start,pivot-1);就数组越界了return;}int pivot partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot1,end);}public static void quickSort(int []array){quick(array,0,array.lemgth-1); }private static int partition(int[] array, int left, int right) {int ileft;int pivotarray[left];whlie(leftright){while(leftrightpivotarray[right]){ //这里的条件就是跳过比基准大的//问题2为什么要从右边先开始找//问题3为什么这里要取等呢right--;}while(leftrightpivotarray[left]){//跳过比基准小的left;} swap(array,left,right);}swap(array,left,i);return left;}
针对问题2为什么从右边开始移动为了保证当left和right相遇时left指向的元素是小于pivot的。因为我们最后是要将pivot和这个相遇的交换位置
针对问题3结合代码分析就会发现;这种情况是两个循环都进不去外部循环却是left一直小于right;死循环
时间复杂度ON*logN找基准一步一步分割向一颗二叉树。每一层总和都是N的大小在找大小遍历范围是N。然后一共有logn层树的高度 空间复杂度Ologn左边结束回收右边一样创建一样大小 稳定性不稳定
挖坑法
逻辑后面R往前找比6小的5放第一个坑位然后前面往后走找到比6大放后面多出来坑位。相遇自己把自己放进去。最后出来把这个基准丢进去 //快排private static void quick(int[] array,int start,int end) {if(start end) {return;}int pivot partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot1,end);}public static void quickSort(int []array){quick(array,0,array.lemgth-1); }public static int partition1(int[] arr,int left,int right) {int pivot arr[left];while(left right) {while(left right arr[right] pivot) {right--;}arr[left]arr[right];//画个图走一遍就好理解while (left right arr[left] pivot) {left;}arr[right]arr[left];}arr[left]pivot;return left;}两种不同的方式实现下来第一次的结果不一样一般情况用挖坑法。还是挖坑法比较好理解和实现。
前后指针法 逻辑prev在0位置cur在1位置开始以第一个为基准。用cur的值去和基准的值比较 如果cur下的值比较小那就prev先走一步。在这时候cur和prev就相遇了这有什么好处呢这样子我们就可以通过判断cur和prev是不是在同一个位置如果在同一个位置就说明当前遇到的值是小的不需要交换。判断需不需要交换的条件 如果遇到cur当前比较大的值prev就先不要动prev是在大于基准值的前一个位置这时候两个if条件都不会进去的cur继续往后走找到一个小于基准的值。然后if条件进去prev往后走一步并且 arr[prev] ! arr[cur]进行交换。
最后prev和头的基准交换当cur走完的时候prev所在的位置就是基准但是你返回前得把开始的基准值跟这个基准位所在的值换一下 //快排private static void quick(int[] array,int start,int end) {if(start end) {return;}int pivot partition(array,start,end);quick(array,start,pivot-1);quick(array,pivot1,end);}public static void quickSort(int []array){quick(array,0,array.lemgth-1); }
public static int partition2(int[] arr,int left,int right) {//前后指针法int prev left;int cur left 1;int pivot arr[left];while(cur right) {if(arr[cur]arr[left]){prevprev;}if(arr[cur] arr[left] arr[prev] ! arr[cur]) {swap(arr,prev,cur);}cur;}swap(arr,left,prev);return prev;}
只能说设计的非常巧妙但是代码非常不好理解自己在画图板进行走一遍比较好理解。 举例开始prev先走一步cur和prev在值为1的位置相遇。我们判断一下他们位置是不是一样一样就不交换。cur往后走。反复这个过程。 直到两个人在2的位置相遇现在cur要走到7的位置判断发现比6大prev就停下来不走。cur往后走遇到比6大的还是继续往后在直到遇到比6小的3prev就可以往后走一步到7的位置然后他们两个位置不相等就进行交换。
非递归实现
模拟递归的流程去走申请一个栈先获取一下基准是在哪里。然后就按基准划分分而治之把两边的left和right加入栈里。判断栈为空吗不为空取出两个去走partition。注意左边和右边只有一个元素时就不需要入栈和出栈存的顺序是先左后右取的话就先赋值给右再赋值给左
public static void quickSort1(int[] arr) {StackInteger stack new Stack();int left 0;int right arr.length - 1;int pivot partition(arr,left,right);//如果只有一个元素那就直接有序没必要再走这些流程//判断左边是不是有两个元素if(left pivot - 1) {stack.push(left);stack.push(pivot - 1);}//判断右边是否有两个元素if(right pivot 1) {stack.push(pivot 1);stack.push(right);}while (!stack.isEmpty()) {right stack.pop();left stack.pop();pivot partition(arr,left,right);//判断左边是不是有两个元素if(left pivot - 1) {stack.push(left);stack.push(pivot - 1);}//判断右边是否有两个元素if(right pivot 1) {stack.push(pivot 1);stack.push(right);}}}
快排优化
优化当数据趋于有序我们都使用插排。当快速排序在最后几层时数组已经趋于有序。因为递归到小的区间这时候的递归量是非常多的而且数据也是比较有序建议使用快排。犹如一颗满二叉树越到下面节点个数越多。 三数取中法 三个数头尾中间找中位值把这个位置换到0位置然后再开始我们的快速排序。三个数一个都不知道怎么求中位值大小 问题是怎么找到这三个数中中间大小的数而且它们是一直在变化的那就只能分情况处理
public static int findMidValueOfIndex(int[] arr,int start,int end) {int mid (end start) / 2;if(arr[start] arr[end]) {if(arr[mid] arr[start]) {return start;}else if(arr[mid] arr[end]) {return end;}else {return mid;}}else {if(arr[mid] arr[end]) {return end;}else if(arr[mid] arr[start]) {return start;}else {return mid;}}}
public static void quick(int[] arr,int start,int end) {if(start end) {return;}//因为随着排序次数增多基准就把元素分组的更多这时候使用插排更快if((end - start 1) 15) {insert(arr,start,end);}//在进行partition尽量去解决不均匀问题int mid findMidValueOfIndex(arr,start,end);swap(arr,mid,start);int pivot partition2(arr,start,end);quick(arr,start,pivot - 1);quick(arr,pivot 1,end);}public static void insert(int[] arr,int left,int right) {for (int i left 1; i right; i) {int j i 1;for (; j 0; j--) {if(arr[j] arr[i]) {arr[j 1] arr[j];}else {break;}}arr[j 1] arr[i];}}private static void insertSort(int[] array,int left,int right) {for (int i left1; i right; i) {int tmp array[i];int j i-1;for (; j left;j--) {if(array[j] tmp) {array[j1] array[j];}else {//array[j1] tmp;break;}}array[j1] tmp;}} 归并排序
分而治之针对一个数组取中间下标的值然后把数组分成以下[start,mid],[mid1,right]两个区间接着把左边部分的数组继续取中间值然后不断递归下去。右边数组同样的方式继续递归下去。直到左下标与右下标相等。 如何分解也是一个二叉树递归过程分解成一个一个元素后返回合并。 代码框架 整体代码 public static void mergeSort1(int[] array) {mergeSortChild(array,0,array.length-1);}private static void mergeSortChild(int[] array,int left,int right) {if(left right) {return;}int mid (leftright) / 2;mergeSortChild(array,left,mid);mergeSortChild(array,mid1,right);//合并merge(array,left,mid,right);}private static void merge(int[] array,int left,int mid,int right) {int s1 left;int e1 mid;int s2 mid1;int e2 right;int[] tmpArr new int[right-left1];int k 0;//表示tmpArr 的下标while (s1 e1 s2 e2) {if(array[s1] array[s2]) {tmpArr[k] array[s1];}else{tmpArr[k] array[s2];}}while (s1 e1) {tmpArr[k] array[s1];}while (s2 e2) {tmpArr[k] array[s2];}//tmpArr当中 的数据 是right left 之间有序的数据for (int i 0; i k; i) {array[ileft] tmpArr[i];}}每一层都有N个元素在不断分解数组的过程当中分解的层数为log以2为底n的对数由于每层都有N个元素因此分解过程的时间复杂度为O(Nlog以2为底N的对数);即O(Nlog(N))。空间复杂度每一层都开辟了一个大小为[end-start1]的数组因此空间复杂度为O(N)。
1.归并的缺点在于需要O(N)的空间复杂度归并排序的思考更多的是解决在磁盘中的外排序问题。 2.时间复杂度O(N*logN) 3.空间复杂度O(N) 4.稳定性稳定
非递归实现归并排序
一个有序变两个有序然后变4个有序再变八个有序。gap先是一个一个有序然后两个四个直到gaparray.length就结束 public static void mergeSort(int[] array) {int gap 1;while (gap array.length) {for (int i 0; i array.length; i gap*2) {int left i;int mid left gap -1;int right midgap;if(mid array.length) {mid array.length-1;}if(right array.length) {right array.length-1;}merge(array,left,mid,right);}gap * 2;}}海量数据排序问题
内存放不下了需要外部排序归并排序是最常用的外部排序。 比如内存只有1G而要排的有100G 1先把文件切分成 200 份每个 512 M 2分别对 512 M 排序因为内存已经可以放的下所以任意排序方式都可以 3进行 2路归并同时对 200 份有序文件做归并过程最终结果就有序了
基数排序不用比较就能够排序
空间换取时间入的次数和出的次数取决于数据里面的最大值。先把个位的排序好这样子然后有相同数字的数或者后面它们十位是相同的那就也是有序的。
桶排序 计数排序场景在数据指定范围内范围小数据集中的情况下
比如范围0-n创建n大小的数组每一个下面都放0然后遍历我的这组数遇到这个数一次就在这个下标放个1再遇到一次就这个下标放的值再加1然后打印这个数组值为0不打印值为1打印下标一次值为2打印下标两次。
实现怎么找n遍历一遍数组找到最大值与最小值的差值。比如90-99.这时候就是90放0下标 //计数排序
public static void countSort(int[] arr) {int min arr[0];int max arr[0];//找最大值 最小值for (int i 0; i arr.length; i) {if(arr[i] min) {min arr[i];}if(arr[i] max) {max arr[i];}}//创建一个计数数组数组大小为数组值的取值范围int lenmax - min 1;int[] countArr new int[len];//统计每个数字出现的次数for (int i 0; i arr.length; i) {int val arr[i];countArr[val-min] ;}int index 0;//遍历计数数组看每个下标的值是几就按顺序给原数组赋值记得加上minfor (int i 0; i countArr.length; i) {while (countArr[i] 0) {arr[index] imin;//index得在循环外面定义赋值这样才能保证是连续往上增加的index;countArr[i]--;//countArr[i]是统计了一个数出现的次数出现几次我们就按顺序赋值几次}}//经过上述操作arr就有序了
}
时间复杂度O(n数值范围) 空间复杂度O范围 稳定的排序
总结
