织梦cms 获得网站流量次数,PHP网站开发项目式教程,福州++网站建设,注册公司需要什么证件和手续文章目录 十大排序排序算法复杂度及稳定性分析一、 排序的概念1.排序#xff1a;2.稳定性#xff1a;3.内部排序#xff1a;4.外部排序#xff1a; 二、插入排序1.直接插入排序2.希尔排序 三、选择排序1.直接选择排序方法一方法二直接插入排序和直接排序的区别 2.堆排序 四… 文章目录 十大排序排序算法复杂度及稳定性分析一、 排序的概念1.排序2.稳定性3.内部排序4.外部排序 二、插入排序1.直接插入排序2.希尔排序 三、选择排序1.直接选择排序方法一方法二直接插入排序和直接排序的区别 2.堆排序 四、交换排序1.冒泡排序2.快速排序1.挖坑法2.Hoare法3.前后指针法4.快速排序的优化方法一随机选取基准值方法二三数取中法选基准值方法三递归到最小区间时、用插入排序 5.快速排序非递归实现 五、归并排序1.递归实现2.非递归实现3.海量数据的排序问题 六、计数排序概念写法一写法二 七、桶排序概念代码 八、基数排序概念1.LSD排序法最低位优先法2.MSD排序法最高位优先法 基数排序VS基数排序VS桶排序 十大排序 排序算法复杂度及稳定性分析
排序方法最好平均最坏空间复杂的稳定性场景冒泡排序O(N)(优化情况)O(N2)O(N2)O(1)稳定和数据有序无序无关除非进行优化插入排序O(N) (有序情况)O(N2)O(N2)O(1)稳定趋于有序时使用把无序插入有序选择排序O(N2)O(N2)O(N2)O(1)不稳定和数据有序无序无关选一个小的值和前面交换希尔排序O(N1.3) 局部结果O(1)不稳定缩小增量分组最后进行插入排序堆排序O(N*log2N)O(N*log2N)O(N*log2N)O(1)不稳定和数据有序无序无关,升序建立大根堆降序小根堆堆顶元素和最后元素交换快速排序O(N*log2N)O(N*log2N)O(N2)O(log2N) ~ON不稳定数据有序时间复杂度为O(N2)O(N*log2N) 最好情况优化三数取中小区间插入排序归并排序O(N*log2N)O(N*log2N)O(N*log2N)ON稳定和数据有序无序无关计数排序O(NK)O(NK)O(NK)O(NK)稳定非比较一组集中在某个范围内的数据基数排序ONKONKONKON稳定按位分割进行排序适用于大数据范围排序打破了计数排序的限制桶排序O(NK)O(N2)O(NK)O(NK)稳定划分多个范围相同的区间每个子区间自排序最后合并
一、 排序的概念
1.排序
一组数据按递增/递减排序
2.稳定性
待排序的序列中存在多个相同的关键字拍完序后相对次序保持不变就是稳定的
3.内部排序
数据元素全部放在内存中的排序
4.外部排序
数据元素太多不能同时放在内存中根据排序过程的要求不能在内外存之间移动数据的排序
二、插入排序
1.直接插入排序 和整理扑克牌类似将乱序的牌按值的大小插入整理好的顺序当中
从头开始比最后一个小的话依次向前挪直到大于之前牌时进行插入 1.如果只有一个值则这个值有序所以插入排序 i 从下标1开始把后面的无序值插入到前面的有序当中 2.j i-1,是i的前一个数先用tmp将 i位置的值要插入的值先存起来比较tmp和j位置的值 3.如果tmp的值比 j位置的值小说明要向前插入到有序的值中把 j位置的值后移移动到 j1的位置覆盖掉 i 的值 4.j 下标向前移动一位再次和 tmp 比较 5.如果tmp的值比 j 位置的值大说明找到了要插入的位置就在当前j位置之后把tmp存的值放到 j1的位置 6.如果tmp中存的值比有序的值都小j位置的值依次向后移动一位j不停减1直到排到第一位的数移动到第二位j的下标从0移动到-1循环结束最后将tmp中存的值存放到 j1的位置也就是0下标 public void insertSort(int[] array) {for (int i 1; i array.length; i) {int tmp array[i];//tmp存储i的值int j i - 1;for (; j 0; j--) {if (tmp array[j]) {array[j 1] array[j];} else {// array[j1] tmp;break;}}array[j 1] tmp;}}
插入就是为了维护前面的有序 元素越接近有序直接插入排序算法的时间效率越高 时间复杂度O( N 2 ) 空间复杂度O ( 1 ) 稳定性稳定 如果一个排序是稳定的可以改变实现为不稳定的 如果是不稳定的排序则没有办法改变
2.希尔排序 希尔排序shellSort 叫缩小增量排序是对直接插入排序的优化先分组对每组插入排序让整体逐渐有序
利用了插入排序元素越有序越快的特点 先确定一个整数把待排序数分成多个组每个组中的数距离相同对每一组进行排序然后再次分组排序减少分组数组数多每组数据就少找到分组数1时基本有序了只需要再排一次插入排序即可 一开始组数多每组数据少可以保证效率 随着组数的减少每组数据变多数据越来越有序同样保证了效率 到达1分组之前前面的排序都是预排序 public static void shellSort2(int[] array) {int gap array.length;while (gap 1) { //gap1时缩小增量gap / 2;//直接在循环内进行最后一次排序shell(array, gap);}}/**** 希尔排序* 时间复杂度O(N^1.3---N^1.5)* param array*/public static void shellSort1(int[] array) {int gap array.length;while (gap 1) { //gap1时缩小增量shell(array, gap);gap / 2;//gap1时不进入循环再循环为再次排序}shell(array, gap);//组数为1时进行插入排序}public static void shell(int[] arr, int gap) {//本质上还是插入排序但是i和j的位置相差为组间距for (int i gap ; i arr.length; i) {int tmp arr[i];int j i-gap;for (; j 0; j - gap) {if (tmparr[j]){arr[jgap] arr[j];}else {break;}}arr[jgap] tmp;}}
时间复杂度O( N^1.3 ^) ---- O( N^1.5 ^)空间复杂的O(1)稳定性不稳定
三、选择排序 在待排序序列中找到最小值大的下标和排好序的末尾交换放到待排序列的开头直到全部待排序元素排完
1.直接选择排序 方法一
/*** 选择排序** param array*/public static void selectSort(int[] array) {for (int i 0; i array.length; i) {int minIndex i;for (int j i 1; j array.length; j) {//找最小值if (array[j] array[minIndex]) {minIndex j;//只要比minIndex小放进去}}//循环走完后minIndex存的就是当前未排序的最小值//将当前i的值和找到的最小值进行交换swap(array,i,minIndex);}}public static void swap(int[] array, int i, int j) {int tmp array[i];array[i] array[j];array[j] tmp;}1.遍历数组长度i从0开始 2.每次循环都由minIndex i 来记录最小值的下标 3.j 从i1开始遍历只要比记录的最小值小就让minIndex记录。找到未排序中的最小值进行交换 4.如果遍历完后未排序中没有比minIndex存的值小i的值就是最小值i; 效率低, 如果较为有序的序列在交换时会破坏有序性时间复杂度O ( N2 )空间复杂的O ( 1 )稳定性不稳定
方法二 上面的方法只是先选出最小的值然后和i的位置交换 进行优化在遍历时选出最大值和最小值和收尾进行交换 /*** 选择排序---选最大值和最小值** param array*/public static void selectSort2(int[] array) {int left 0;int right array.length - 1;while (left right) {int minIndex left;int maxIndex left;//选出最大值和最小值for (int i left 1; i right; i) {if (array[i] array[maxIndex]) {maxIndex i;}if (array[i] array[minIndex]) {minIndex i;}}//用最大值和最小值交换首位swap(array, left, minIndex);//把left和最小值交换//如果left恰好就是最大值就有可能把最大值换到minIndex的位置if(left maxIndex){maxIndex minIndex;//最大值位置不是left了而是换到了minIndex}swap(array, right, maxIndex);left;right--;}}1.在遍历的过程中选出最大值的下标和最小值的下标 2.将left和最小值进行交换 3.如果left恰好为最大值left和最小值交换完成后最大值就在原来最小值的位置上 4.maxIndex minIndex,修正最大值的位置 4.将right和最大值进行交换 直接插入排序和直接排序的区别
和插入排序不同的是插入排序会持续对已排序的数进行比较把合适的数放在合适的位置直接选择排序就是不断找到最小的值依次放在排好序的末尾不干预排好的序列
2.堆排序 时间复杂度: O( N * log N)空间复杂的O (1) 升序建大堆 降序建小堆
将一组数据从小到大排序 —— 建立大根堆 为什么不用小根堆小根堆只能保证根比左右小不能保证左右孩子的大小顺序并且要求对数组本身进行排序 大根堆保证堆顶元素是最大值最大值跟最后一个元素交换将最大的放在最后usedSize–向下调整调整0下标的树维护大根堆最大值继续交换到最后一个有效元素的位置从后往前从大到小依次排列保证在原来数组本身进行排序 /*** 堆排序* 时间复杂度: N*logN* 空间复杂的o(1)** param array*/public static void heapSort(int[] array) {createBigHeap(array);//创建大根堆int end array.length-1;while (end0){swap(array,0,end);//堆顶元素和末尾互换shiftDown(array,0,end);//维护大根堆end--;}}/*** 创建大根堆** param array*/public static void createBigHeap(int[] array) {//最后一个结点的下标 array.length - 1//它的父亲结点的下标就为array.length - 1 - 1) / 2for (int parent (array.length - 1 - 1) / 2; parent 0; parent--) {shiftDown(array, parent, array.length);}}/*** 向下调整** param array* param parent* param len*///向下调整每棵树从父结点向下走public static void shiftDown(int[] array, int parent, int len) {int child parent * 2 1;while (child len) {//child len:最起码要有一个左孩子if (child 1 len array[child] array[child 1]) {child;}//child 1len:保证一定有右孩子的情况下和右孩子比较//拿到子节点的最大值if (array[child] array[parent]) {swap(array, child, parent);parent child;//交换完成后让parent结点等于等于当前child结点child 2 * parent 1;//重新求子节点的位置再次进入循环交换} else {break;//比父结点小结束循环}}} 时间复杂度: O( N * log 2N)空间复杂的O (1)稳定性不稳定 四、交换排序
根据序列中两个记录键值的比较结果来对换这两个记录在序列中的位置将键值较大的记录向序列的尾部移动键值较小的记录向序列的前部移动。
1.冒泡排序 /*** 冒泡排序* 时间复杂度 n^2* 空间复杂度 1* param array*/public static void bubbleSort(int[]array){for (int i 0; i array.length-1; i) {//趟数boolean flg false;for (int j 0; j array.length-1-i; j) {if (array[j]array[j1]){swap(array,j,j1);flg true;}}if (flg false){return;}}} 1.遍历 i 代表交换的趟数遍历 j 进行两两交换 2.j array.length-1-i 是对于趟数的优化每走一趟交换就少一次 3.boolean flg false;当两两交换时flg变为true 4.进一步优化如果遍历完没发生交换flg还是false,直接返回排序结束 时间复杂度O ( N2 )空间复杂度O ( 1 )稳定性稳定 2.快速排序 时间复杂度 最好情况O (N*log2N) 树的高度为log2N每一层都是N 最坏情况:O (N2)有序、逆序的情况下,没有左树只有右树单分支树树的高度是N,每一层都是N 空间复杂的 最好情况O (log2N)满二叉树均匀分割待排序的序列效率最高树高为 log2N 最坏情况ON:单分支树,树高为N 稳定性不稳定 二叉树结构的交换排序方法 任取一个待排序元素作为基准值把序列一分为二左子序都比基准值小右子序都比基准值大左右两边再重复进行 左边找比基准值大的右边找比基准值小的
1.挖坑法 基准值位置挖一个坑后面找一个比基准值小的把坑埋上前面找一个比基准值大的埋后面的坑当lr时把基准值填入剩下的坑中 左右两边重复进行上述步骤直到排完为止左右两边都以同样的方法进行划分运用递归来实现 /*** 快速排序* 时间复杂度:N*log~2~N* 空间复杂度* * param array*/public static void quickSort(int[] array) {quick(array, 0, array.length - 1);}private static void quick(int[] array, int start, int end) {if (start end) {return;//结束条件// start end说明只剩一个了是有序的返回//start end ,说明此时的基准值在开头或者末尾//在开头start不变endpivot-1,start end end-1 没有左树//在结尾end不变start pivot1,start end,超出索引没有右树}//不断递归quickint pivot partition(array, start, end);// 进行排序划分找到pivot//然后递归划分法左边递归划分的右边quick(array, start, pivot - 1);quick(array, pivot 1, end);}// ---挖坑法 划分返回基准值private static int partition(int[] array, int left, int right) {int tmp array[left];//挖一个坑取left位置为基准值while (left right) {//在右边找一个比基准值小的把坑填上while (left right array[right] tmp) {//防止越界right--;}array[left] array[right];//找到比tmp小的数填坑,//在左边找一个比tmp大的值填到右边的坑while (left right array[left] tmp) {//防止越界left;}array[right] array[left];}//如果相遇了退出循环array[left] tmp;//填坑return left;} 先划分序列递归左边然后再递归右边 递归结束条件 start end时说明只剩一个了是有序的返回 start end 时 ,说明此时的基准值在开头或者末尾 如果基准值在开头start不变endpivot-1,start end end-1 没有左树 如果基准值在结尾end不变start pivot1,start end,超出索引没有右树 2.Hoare法 不同的方法找出基准值排的序列是不一样的 i记录基准值一开始在left位置的下标r找到比基准值小的停下来l找到比基准值大的停下来互相交换l和r相遇的时候把i 记录基准值的初始下标和相遇位置交换
以左边为基准先找右边再找左边相遇的位置就是以右边为基准的值要比基准小才能交换 /*** Hoare法 划分排序找基准值* param array* param left* param right* return*/private static int partition2(int[] array, int left, int right) {int tmp array[left];int i left;//记录基准值一开始在left位置的下标while (left right) {while (left right array[right] tmp) {right--;}while (left right array[left] tmp) {left;}swap(array,left,right);}swap(array,i,left);return left;}3.前后指针法 prev记录了比key小的最后一个位置cur去找比key值小的找到后放到prev的下一个位置最后找到基准值并且基准值的左边都比它小右边都比他大 /*** 前后指针法划分排序找基准值** param array* param left* param right* return*/private static int partition3(int[] array, int left, int right) {int prev left; //prev从left位置开始left为当前的基准值int cur left 1;//cur在prev的后一个while (cur right) {//遍历完当前数组段if (array[cur] array[left] array[prev] ! array[cur]) {//只要cur指向的值小于left位置的基准值//并且prev后不等于cur的值swap(array, cur, prev);//将cur和prev位置的值交换//cur;}//如果cur的值大于基准值,或者prev下一位的值等于cur,cur后移cur;}//cur越界循环结束最后交换基准值和prev位置的值//prev记录的就是比基准值小的最后一个数swap(array, prev, left);return prev;//prev为基准值}
4.快速排序的优化 时间复杂度 最好情况O (N*log2N) 树的高度为log2N每一层都是N 最坏情况:O (N2)有序、逆序的情况下,没有左树只有右树单分支树树的高度是N,每一层都是N 空间复杂的 最好情况O (log2N)满二叉树均匀分割待排序的序列效率最高树高为 log2N 最坏情况ON:单分支树,树高为N 稳定性不稳定 快速排序有可能发生栈溢出异常需要进行优化 所以要能均匀分割待排序的序列
递归的次数多了会导致栈溢出所以优化的方向就是减少递归的次数
在最坏情况下比如顺序基准值都取自左边本身没有左树
方法一随机选取基准值
看人品有概率
方法二三数取中法选基准值
三数第一个数、中间的数、最后一个数 在这三个数中选出中等值 有可能会变成二分查找 避免了出现最坏情况从中值来比较排序左右树都有 public static void quickSort(int[] array) {quick2(array, 0, array.length - 1);}private static void quick2(int[] array, int start, int end) {if (start end) {return;//结束条件}//三数取中法int index midThree(array, start, end);//选出的数和开头交换swap(array,index,start);int pivot partition(array, start, end);// 进行排序划分找到pivot//然后递归划分法左边递归划分的右边quick2(array, start, pivot - 1);quick2(array, pivot 1, end);}/*** 三数取中* param array* param left* param right* return*/private static int midThree(int[] array, int left, int right) {int mid (left right) / 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[right]) {return right;} else if (array[mid] array[left]) {return left;} else {return mid;}}}方法三递归到最小区间时、用插入排序
进一步优化减少递归的次数 把快排的递归想象成二叉树最后两层包含了大部分数我们要减少这部分的递归 前几次的找基准值排序导致后面几层趋于有序用直接插入法来排序进一步提高效率有点像希尔排序
如果树的高度为h,最后一层就有 2 h-1 个结点 后两层占了绝大部分
设置条件end-start1 就是当前待排序列的长度如果小于等于某个较小的值直接采用插入排序来排剩下的 private static void quick2(int[] array, int start, int end) {if (start end) {return;//结束条件}//优化----减少递归的次数if(end-start120){//如果当前数列的长度小于15的时候// 用插入排序,然后退出insertSortQ(array,start,end);return;}//三数取中法int index midThree(array, start, end);swap(array,index,start);int pivot partition(array, start, end);// 进行排序划分找到pivot//然后递归划分法左边递归划分的右边quick2(array, start, pivot - 1);quick2(array, pivot 1, end);}/*** 插入排序---来排剩下的待排部分给定需要的区间*/private static void insertSortQ(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[j 1] array[j];} else {break;}}array[j 1] tmp;}}
5.快速排序非递归实现
1.通过使用栈来实现2.每次找到基准值后把两段序列的开头和末尾压栈3.从栈顶取出两个元素作为新序列的首尾再次找基准值4.找到基准值后如果右边有一个元素不进栈有两个元素的才能进栈5.pivot end-1:证明右边有两个元素pivots1证明左边有两个元素6.栈为空的时候排完元素 /*** 非递归实现快速排序** param array*/public static void quickSortNonRecursive(int[] array) {DequeInteger stack new LinkedList();//利用栈来实现int left 0;int right array.length - 1;//先找到基准值int pivot partition(array, left, right);//左边有两个元素时根据基准值进栈if (pivot left 1) {stack.push(left);stack.push(pivot - 1);}//有边有两个元素时根据基准值进栈if (pivot right - 1) {stack.push(pivot 1);stack.push(right);}//栈不为空的时候取两个栈顶元素做为区间//再次进栈出栈while (!stack.isEmpty()) {right stack.pop();left stack.pop();pivot partition(array, left, right);//左边有两个元素时根据基准值进栈if (pivot left 1) {stack.push(left);stack.push(pivot - 1);}//有边有两个元素时根据基准值进栈if (pivot right - 1) {stack.push(pivot 1);stack.push(right);}}}五、归并排序 时间复杂度O ( N * logzN ) 每一层都是N,有log2N层空间复杂度ON每个区间都会申请内存最后申请的数组大小和array大小相同稳定性稳定 目前为止稳定的排序有插入、冒泡、归并 归并排序MERGE-SORT是建立在归并操作上的一种有效的排序算法采用了分治法 将待排序列分解先使每个子序列有序再使子序列段间有序将已有序的子序列合并得到完全有序的序列若将两个有序表合并成一个有序表称为二路归并
1.递归实现 1.确定递归的结束条件求出中间数mid,2.进行分解根据mid来确定递归的区间大小3.递归分解完左边然后递归分解右边4.左右分解完成后进行合并5.申请新数组进行合并比较两个数组段记得查漏补缺6.和并的时候要对齐下标每个tmp的下标要找到array中对应的下标
/*** 归并排序* param array*/public static void mergeSort(int[] array) {mergeSortFunc(array,0,array.length-1);}private static void mergeSortFunc(int[] array, int left, int right) {//结束条件if (left right) {return;}//进行分解int mid (left right) / 2;mergeSortFunc(array, left, mid);mergeSortFunc(array, mid 1, right);//左右分解完成后进行合并merge(array, left, right, mid);}//进行合并private static void merge(int[] array, int start, int end, int mid) {int s1 start;int s2 mid 1;int[] tmp new int[end - start 1];int k 0;//k为tmp数组的下标while (s1 mid s2 end) {//两个数组中都有数据//进行比较放到新申请的数组if (array[s1] array[s2]) {tmp[k] array[s1];} else {tmp[k] array[s2];}}//因为有条件数组不一定走完while (s1 mid) {tmp[k] array[s1];}while (s2 end) {tmp[k] array[s2];}//此时将排好的tmp数组的数组拷贝到arrayfor (int i 0; i tmp.length; i) {array[istart] tmp[i];//对齐下标}}2.非递归实现 1.从1开始分组先保证每个数都是独立有序的2.进行循环i下标从0开始每次跳转组数的两倍3.根据left i,求出mid和right4.要避免mid和right越界5.分组进行合并6.二倍数扩大组数
/**** 归并排序非递归实现* param array*/public static void mergeSort2(int[] array) {int gap 1;while (gap array.length) {//i gap * 2 i每次跳到下一组for (int i 0; i array.length; i gap * 2) {int left i;//要避免mid和right越界int mid left gap - 1;if(midarray.length){mid array.length-1;//修正越界的情况}int right mid gap;if (rightarray.length){//修正越界的情况right array.length-1;}merge(array,left,right,mid);//进行合并}gap *2;//2倍数扩大组数}}//进行合并private static void merge(int[] array, int start, int end, int mid) {int s1 start;int s2 mid 1;int[] tmp new int[end - start 1];int k 0;//k为tmp数组的下标while (s1 mid s2 end) {//两个数组中都有数据//进行比较放到新申请的数组if (array[s1] array[s2]) {tmp[k] array[s1];} else {tmp[k] array[s2];}}//因为有条件数组不一定走完while (s1 mid) {tmp[k] array[s1];}while (s2 end) {tmp[k] array[s2];}//此时将排好的tmp数组的数组拷贝到arrayfor (int i 0; i tmp.length; i) {array[i start] tmp[i];//对齐下标}}3.海量数据的排序问题
外部排序排序过程需要在磁盘等外部存储进行的排序
前提内存只有 1G需要排序的数据有 100G
因为内存中因为无法把所有数据全部放下所以需要外部排序而归并排序是最常用的外部排序
先把文件切分成 200 份每个 512 M分别对 512 M 排序因为内存已经可以放的下所以任意排序方式都可以进行 2路归并同时对 200 份有序文件做归并过程最终结果就有序了
六、计数排序 时间复杂度空间复杂度稳定性稳定
概念 非基于比较的排序 计数排序又称为鸽巢原理是对哈希直接定址法的变形应用 1.统计相同元素出现的个数 2.根据统计的结果将序列回收到原来的序列中 计数排序使用的场景给出指定范围内的数据进行排序 使用场景一组集中在某个范围内的数据
写法一
通过遍历计数数组循环输出计数数组存的次数 1.遍历数组找到最小值最大值2.根据最大最小值申请一个计数数组3.遍历待排数组进行计数4.遍历计数数组进行输出 /*** 计数排序*无法保证稳定* param array*/public static void countSort2(int[] array) {//1.遍历数组找到最大值和最小值int MAX array[0];int MIN array[0];for (int i 1; i array.length; i) {if (array[i] MAX) {MAX array[i];}if (array[i] MIN) {MIN array[i];}}//2.根据最大最小值申请一个计数数组int len MAX - MIN 1;//长度int[] count new int[len];//3. 遍历待排数组进行计数for (int i 0; i array.length; i) {count[array[i] - MIN];}//4.遍历计数数组进行输出int index 0;//array数组新的下标for (int i 0; i count.length; i) {while (count[i] 0) {array[index] i MIN;//最小值求出真正的数count[i]--;index;}}}写法二
写定数组的大小用临时数组存储结构计算每个元素在排序后的数组中的最终位置根据计数数组将元素放到临时数组b中实现排序从后往前根据原来数组的内容在计数数组中找到要填写在b数组中的位置计数数组记录的不再是数字出现是次数而是应该在数组中存放的位置下标 /*** 计数排序*稳定* param array*/public static void countSort(int[] array) {int len array.length;final int MAX 256;//常量确定数组大小int[] c new int[MAX];//计数数组int[] b new int[MAX];//临时数组存放结果//统计每个元素的出现次进行计数for (int i 0; i len; i) {c[array[i]];// 将a[i]作为索引对应计数数组c中的位置加1}// 计算每个元素在排序后的数组中的最终位置for (int i 1; i MAX; i) {c[i] c[i - 1];// 计数数组中每个元素的值等于它前面所有元素的值之和}// 根据计数数组将元素放到临时数组b中实现排序for (int i len - 1; i 0; i--) {b[c[array[i]] - 1] array[i];// 将a[i]放入临时数组b中的正确位置c[array[i]]--;// 对应计数数组c中的位置减1确保相同元素能够放在正确的位置}// 将临时数组b中的元素复制回原数组a完成排序for (int i 0; i len; i) {array[i] b[i];}}
七、桶排序
概念
划分多个范围相同的区间每个子区间自排序最后合并 桶排序是计数排序的扩展版本计数排序每个桶只存储单一键值 桶排序 每个桶存储一定范围的数值确定桶的个数和范围 将待排序数组中的元素映射到各个对应的桶中对每个桶进行排序 最后将非空桶中的元素逐个放入原序列中 代码 public static void bucketSort(int[] array){// 计算最大值与最小值int max Integer.MIN_VALUE;int min Integer.MAX_VALUE;for(int i 0; i array.length; i){max Math.max(max, array[i]);min Math.min(min, array[i]);}// 计算桶的数量int bucketNum (max - min) / array.length 1;ArrayListArrayListInteger bucketArr new ArrayList(bucketNum);for(int i 0; i bucketNum; i){bucketArr.add(new ArrayListInteger());}// 将每个元素放入桶for(int i 0; i array.length; i){int num (array[i] - min) / (array.length);bucketArr.get(num).add(array[i]);}// 对每个桶进行排序for(int i 0; i bucketArr.size(); i){Collections.sort(bucketArr.get(i));}// 将桶中的元素赋值到原序列int index 0;for(int i 0; i bucketArr.size(); i){for(int j 0; j bucketArr.get(i).size(); j){array[index] bucketArr.get(i).get(j);}}}
八、基数排序
概念 基数排序是一种非比较型整数排序算法 将整数按位数切割成不同的数字然后按每个位数分别比较 使用场景按位分割进行排序适用于大数据范围排序打破了计数排序的限制 稳定性稳定 按位分割技巧arr[i] / digit % 10其中digit为10^n。 1.LSD排序法最低位优先法 从最低位向最高位依次按位进行计数排序。 进出的次数和最大值的位数有关 桶可以用队列来表示 数组的每个元素都是队列 1.先遍历找到最大值2.求出最高位 public static void radixSortR(int[] array) {//10进制数有10个桶每个桶最多存array.length个数int[][] bucket new int[10][array.length];//桶里面要存的具体数值int[] bucketElementCounts new int[10];//用来计算统计每个桶所存的元素的个数每个桶对应一个元素//1.求出最大数int MAX array[0];for (int i 1; i array.length; i) {if (array[i] MAX) {MAX array[i];}}//求最大值的位数先变成字符串求字符串长度int MAXCount (MAX ).length();//最大位数的个数进行几次计数排序for (int i 0; i MAXCount; i) {//i代表第几次排序//放进桶中for (int k 0; k array.length; k) {//k相当于遍历待排数值//array[k] /(int) Math.pow(10, i)%10 求出每次要比较位的数//求的是个位并且是对应趟数的个位int value (array[k] / (int) Math.pow(10, i)) % 10;//根据求出的位数找到对应桶放到对应桶的位置bucket[value][bucketElementCounts[value]] array[k];//不管value 为多少bucketElementCounts[value]的值都为0//相当于存到对应桶的0位bucket[value][0]bucketElementCounts[value]; //从0-1//对应桶的技术数组开始计数}//取出每个桶中的元素赋值给数组int index 0;//array新的下标for (int k 0; k bucketElementCounts.length; k) {//遍历每个桶if (bucketElementCounts[k] ! 0) {//桶里有元素for (int j 0; j bucketElementCounts[k]; j) {//比那里每个桶的元素array[index] bucket[k][j];index;}}bucketElementCounts[k] 0;//每个桶遍历完后清空每个桶的元素}}}
2.MSD排序法最高位优先法 从最高位向最低位依次按位进行排序。按位递归分组收集1.查询最大值获取最高位的基数2.按位分组存入桶中3.组内元素数量1,下一位递归分组4.组内元素数量1.收集元素 /*** 基数排序--MSD--递归* param array*/public static void radixSortMSD(int[] array) {//1.求出最大数int MAX array[0];for (int i 1; i array.length; i) {if (array[i] MAX) {MAX array[i];}}//求最大值的位数先变成字符串求字符串长度int MAXCount (MAX ).length();// 计算最大值的基数int radix new Double(Math.pow(10, MAXCount - 1)).intValue();int[] arr msdSort(array, radix);System.out.println(Arrays.toString(arr));}public static int[] msdSort(int[] arr, int radix){// 递归分组到个位退出if (radix 0) {return arr;}// 分组计数器int[] groupCounter new int[10];// 分组桶int[][] groupBucket new int[10][arr.length];for (int i 0; i arr.length; i) {// 找分组桶位置int position arr[i] / radix % 10;// 将元素存入分组groupBucket[position][groupCounter[position]] arr[i];// 当前分组计数加1groupCounter[position];}int index 0;int[] sortArr new int[arr.length];// 遍历分组计数器for (int i 0; i groupCounter.length; i) {// 组内元素数量1递归分组if (groupCounter[i] 1) {int[] copyArr Arrays.copyOf(groupBucket[i], groupCounter[i]);// 递归分组int[] tmp msdSort(copyArr, radix / 10);// 收集递归分组后的元素for (int j 0; j tmp.length; j) {sortArr[index] tmp[j];}} else if (groupCounter[i] 1) {// 收集组内元素数量1的元素sortArr[index] groupBucket[i][0];}}return sortArr;}基数排序VS基数排序VS桶排序 都是非比较型排序 三种排序算法都利用了桶的概念 1.计数排序每个桶只存储单一键值 2.基数排序根据键值的每位数字来分配桶 3.桶排序 每个桶存储一定范围的数值
点击移步博客主页欢迎光临~
