核心内容摘要
WoWmapper：重新定义魔兽世界手柄操控体验的开源神器
排序的概念:排序所谓排序就是使一串记录按照其中的某个或某些关键字的大小递增或递减的排列起来的操作。
稳定性假定在待排序的记录序列中存在多个具有相同的关键字的记录若经过排序这些记录的相对次序保持不变即在原序列中r[i]r[j]且r[i]在r[j]之前而在排序后的序列中r[i]仍在r[j]之前则称这种排序算法是稳定的否则称为不稳定的。
内部排序数据元素全部放在内存中的排序外部排序数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序。
常见排序算法①直接插入排序从第 2 个元素开始逐个取出未排序区的元素在已排序区从后往前找它该待的位置把比它大的元素往后挪最后把它插入进去。
(对象是每一次遍历的) [直接插入排序对下一个数字与已排序区的数进行比较必须从后往前右往左才能高效腾出插入位置这是由插入排序的核心逻辑决定的]②希尔排序规定d初始然后递减从开始到每隔d个的就连起来(可以连多个只要够)然后把连在一起的直接插入排序(其实就是直接排序)然后d自选递减的下一个反正最后要到1(相当于对全部直接插入排序)③交换排序→冒泡排序冒泡排序就是从第1个开始排序然后排完n-1和n后第n个必定是最大值/最小值然后第二轮还是从第1个开始排序只是最后排的结果是n-2和n-1然后重复上述步骤序列从后往前越来越对④快速排序(填坑)先把最左边和最右边的数都放一个下标指针然后把最左边的数当枢纽这个位置留空。
从右边开始如果找到枢纽的数就填在左边的空然后左边指针向右1格。
然后开始看左边指针如果找到枢纽 的就提空放在右空格然后右指针左移1格(上面都是被填的指针向中间靠)。
然后直到靠到两个指针重合就把当枢纽的放进去以枢纽往两边分分成两个区这两个区在分别进行上述快速排序(到这进行两轮)。
最后执行几轮不确定⑤简单选择排序每次都在未排序的里面选最小的放到已排序的最后一个⑥堆排序:先按给的数组按顺序编号1,
..n,然后按层序遍历存在完全二叉树中然后从第[n/2]向下取整开始往小的去按根≥子树(选最大)/根≤子树(选最小)来调整。
注意从大到小调整完还要回去数字编号大的看会不会第二次排序错误注意输出堆顶元素后不需要重新完整排序整个堆只需要从新的堆顶开始向下做一次 “局部调整” 即可恢复堆的性质。
插入元素按层序遍历放在最后。
然后以这个新节点开始向上进行排序⑦归并排序 初始从每组 1 个元素开始天然有序每轮合并后分组大小翻倍2→4→8…直到分组大小≥数组长度一组内的直接排序就行⑧基数排序先创建下标从
的多个链表按个位数十位数百位数(到最大位数)位数一样的就放一起先出现的放上面后出现的放下面(类似一条横线下面挂坠)然后按从左到右每个从上到下写一遍然后再按刚刚的排不过变为按进一位排最后排完最后一位数就会发现从小到大下面均以从小到大排序为例①插入排序(从小到大):把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中直到所有的记录插入完为止得到一个新的有序序列public static void insertSort(int arr[]){//插入排序 for(int i1;iarr.length;i){ int temparr[i]; int ji-1; for(;j0;j--){ if(arr[j]temp){ arr[j1]arr[j]; } else{ arr[j1]temp; break; } } arr[j1]temp; } }for从1开始到length因为下标为0的时候就1个默认有序。
然后先把下标为i的存在临时变量temp中然后定义一个for循环中的变量j(因为后面要用所以在外面2定义j)然后启动j的循环从ji-1开始不断--每一次--如果j的数值t那就让下标j1处的值为下标j处的值这个部分就是把比下标i处的值小的值往前排留出位置给临时变量temp然后每循环一次就会j--循环到j处比temp小(此时因为上一步前移所以j1处为空)那就把temp赋给j1处然后break最后要补一个那就把temp赋给j1处就是找到比前面已排序的数所有都小的情况②希尔排序希尔排序法又称缩小增量法。
希尔排序法的基本思想是先选定一个整数把待排序文件中所有记录分成多个组所有距离为的记录分在同一组内并对每一组内的记录进行排序。
然后取重复上述分组和排序的工作。
当到达1时所有记录在统一组内排好序。
public static void shellSort(int arr[]){ int gaparr.length; while(gap
{ gapgap/2; shell(arr,gap); } } public static void shell(int arr[],int gap){//插入排序 for(int igap;iarr.length;i){ int temparr[i]; int ji-gap; for(;j0;jj-gap){ if(arr[j]temp){ arr[jgap]arr[j]; } else{ arr[jgap]temp; break; } } arr[jgap]temp; } }希尔排序需要两段方法因为希尔排序的gap有影响所以第一个方法是传入数组和gap第二个方法才是排序gap的取值方法有很多主要看第二个方法首先希尔排序就是分区块然后每个区块进行插入排序但是这里的分区是跳跃性的不方便直接操作但是如果我们从直接插入排序的原理去思考首先第一个循环从1开始也就是0的下一个但是希尔排序是按i,igap,igapgap...这样下去的那就把gap当做没次--的单位也就是-gap这样就可以做到每一次i都处理不同区间的一次排序而不是 先排序完一个区间在排序下一个区间③选择排序:每一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置直到全部待排序的数据元素排完public static void selectSort(int arr[]){ for(int i0;iarr.length;i){ int indexi; for(int ji1;jarr.length;j){ if(arr[index]arr[j]){ indexj; } } int tarr[index]; arr[index]arr[i]; arr[i]t; } }依旧需要双指针一个在后面(未排序序列中)选出最大/最小的另一个在后面指向需要填入的位置找到之后把最小的和需要填入的位置的值交换④堆排序:堆排序(Heapsort)是指利用堆积树堆这种数据结构所设计的一种排序算法它是选择排序的一种。
它是通过堆来进行选择数据。
需要注意的是排升序要建大堆排降序建小堆。
public static void heapSort(int arr[]){ createHeap(arr); int endarr.length-1; while(end
{ int tarr[0]; arr[0]arr[end]; arr[end]t; siftDown(arr,0,end); end--; } } public static void createHeap(int arr[]){ for(int p(arr.length-
/2;p0;p--){ siftDown(arr,p,arr.length); } } public static void siftDown(int arr[],int p,int len){ int child2*p1; while(childlen){ if(child1arr.lengtharr[child]arr[child1]){ child; } if(arr[child]arr[p]){ int tarr[child]; arr[child]arr[p]; arr[p]t; pchild; child2*p1; } else { break; } } }首先是先把数组改成小根堆的结果也就是执行createHeap然后每一次都取出堆顶元素(最小的元素)也就是交换堆顶和最后一个元素后从0到最后一个元素的前一个元素进行一次向下调整(end--)即可获得除去最小元素的新的小根堆⑤交换排序基本思想所谓交换就是根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置交换排序的特点是将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
交换排序-冒泡排序public static void bobbleSort(int arr[]){ for(int i0;iarr.length-1;i){ for(int j0;jarr.length-i-1;j){ boolean flgfalse; if(arr[j]arr[j1]){ int tarr[j]; arr[j]arr[j1]; arr[j1]t; flgtrue; } if(flgfalse){ break; } } } }很基础的排序多了一个判断来优化如果某一轮循环交换没有执行说明已经完全有序了无需继续进行下去所以break交换排序-快速排序快速排序是Hoare于1962年提出的一种二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后最左右子序列重复该过程直到所有元素都排列在相应位置上为止。
快速排序有三种方法
Hoare版(双指针交换版)public static void quickSort(int arr[]){//快速排序-双指针法 quick(arr,0,arr.length-
; } public static void quick(int arr[],int start,int end){ if(startend){ return; } int pivotpartfun(arr,start,end); quick(arr,start,pivot-
; quick(arr,pivot1,end); } public static int partfun(int arr[],int left,int right){ int temparr[left]; int templeftleft; while(leftright){ while(leftrightarr[right]temp){//因为right先循环左移保证了templeft交换后基准值的左边仍然是比基准值小的 right--; } while(leftrightarr[left]temp){//这里两个while都必须取等号否则遇到跟基准值一样的数会死循环 left; } int tarr[left]; arr[left]arr[right]; arr[right]t; } int tarr[left]; arr[left]arr[templeft]; arr[templeft]t; return left; }其实这三个方法本质是两个方法前两个方法可以合并成一个只是传入的时候要手动输入0和arr.length第二个方法如果是startend那就说明结束了直接returnpivot是获取基准最后要填入的下标用于分区的分界点然后从start-pivot-1pivot1和end分别递归两次(不包括pivot是因为pivot左边全部pivot右边全部pivot)第三个方法其实这个方法虽然返回的是最后基准填入的下标但是在过程中完成了排序先把基准也就是最左边的数临时存下来然后再把基准的下标也就是初始的left保存因为这个left是原始数组arr中元素的下标防止丢失。
然后从右边开始找right会停在第一个比基准值小的数上left同理。
然后交换left下标和right下标。
最后把基准值和相遇处(leftright)的值交换位置即可因为第一个循环right先动保证了相遇点的值一定是temp基准值的
挖坑法public static void quickSort(int arr[]){//快速排序-双指针法 quick(arr,0,arr.length-
; } public static void quick(int arr[],int start,int end){ if(startend){ return; } int pivotpartfun(arr,start,end); quick(arr,start,pivot-
; quick(arr,pivot1,end); } private static int partfun(int[] array, int left, int right) { int tmp array[left]; while (left right) { while (left right array[right] tmp) { right--; } array[left] array[right]; while (left right array[left] tmp) { left; } array[right] array[left]; } array[left] tmp; return left; }区别只有partfun方法里先把最左边的数当场基准值然后从右边开始找到比基准值小的填入left下标再到左边开始找到比基准值大的填入right最后相遇点(leftright)是空的填入基准值然后返回此处下标
前后指针public static void quickSort(int arr[]){//快速排序-双指针法 quick(arr,0,arr.length-
; } public static void quick(int arr[],int start,int end){ if(startend){ return; } int pivotpartfun(arr,start,end); quick(arr,start,pivot-
; quick(arr,pivot1,end); } private static int partfun(int[] array, int left, int right) { int prev left; int cur left 1; while (cur right) { if (array[cur] array[left] array[prev] ! array[cur]) { swap(array, cur, prev); } cur; } swap(array, prev, left); return prev; } // 配套的 swap 方法需要自行补充 private static void swap(int[] array, int i, int j) { int temp array[i]; array[i] array[j]; array[j] temp; }
快速排序优化(待)
快速排序非递归(待)⑥归并排序是建立在归并操作上的一种有效的排序算法,该算法是采用分治法Divide andConquer的一个非常典型的应用。
将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。
若将两个有序表合并成一个有序表称为二路归并public static void mergeSortTmp(int arr[],int left,int right){ if(leftright){ return; } int mid(leftright)/2; mergeSortTmp(arr,left,mid); mergeSortTmp(arr,mid1,right); merge(arr,left,mid,right); } public static void merge(int arr[],int left,int mid,int right) { int temp[] new int[right - left 1]; int k 0; int s1 left; int e1 mid; int s2 mid 1; int e2 right; while (s1 e1 s2 e
{ if (arr[s1] arr[s2]) { temp[k] arr[s1]; } else { temp[k] arr[s2]; } } while (s1 e
{ temp[k] arr[s1]; } while (s2 e
{ temp[k] arr[s2]; } for (int i 0; i temp.length; i) { arr[left i] temp[i]; } }依旧是两个方法但是第二个是用来2个数组合并成一个数组的为什么会有序因为这个归并排序是从1→2→4→8这样合并每一个数组的所以从1→2开始就是按有序排的2→4也是两个有序的2合并变成有序的4以此类推所以这里的思路是先取中然后把左边进行一次递归右边进行一次递归然后把leftmidright放进2和1方法里进行合并⑦计数排序:统计相同元素出现次数→根据统计的结果将序列回收到原来的序列中public static void countSort(int arr[]){ int maxarr[0]; int minarr[0]; for(int i1;iarr.length;i){ if(arr[i]max){ maxarr[i]; } if(arr[i]min){ minarr[i]; } } int lenmax-min1; int count[]new int[len]; for(int i0;iarr.length;i){ int indexarr[i]; count[index-min]; } int index0; for(int i0;icount.length;i){ while(count[i]!
{ arr[index]mini; index; count[i]--; } } }其实就是建一个新的数组把每个原数组中出现个个数储存然后按次序输出代码实现先擂台法找到原数组的最大最小值然后新数组容量就是max-min1。
循环原数组把arr[i]-min当做下标(最小化数组容量)然后然后index归零遍历新数组只要新数组元素不为0就把这个数赋值给原数组然后index新数组--⑧基数排序(待)⑨ 桶排序(待)
排序算法复杂度及稳定性分析排序方法最好情况平均情况最坏情况空间复杂度稳定性冒泡排序O(n)O(n^
O(n^
O(
稳定插入排序O(n)O(n^
O(n^
O(
稳定选择排序O(n^
O(n^
O(n^
O(
不稳定希尔排序O(n)O(n^
1.