- 1挑战杯 python的搜索引擎系统设计与实现
- 2Unity性能优化系列—加载与资源管理_uwa unity性能优化系列—加载与资源管理
- 3windows搭建ftp，且设置用户_ftp添加用户
- 4el-select数据过多的解决（纯前端）_elementui select数据过多
- 5（十七）unity shader之——————高级纹理之程序纹理_unity shader程序化纹理
- 6UE4 WebUI插件使用指南_ue webui
- 7element表单中一个el-form-item下多个form-item项校验（循环校验）_一个 el-form-item 下多个表单校验(循环校验)
- 8ES集群部署
- 9Caffe版Faster R-CNN可视化——网络模型,图像特征,Loss图,PR曲线
- 10WPF ObservableCollection＜T＞_observablecollection wpf 单个对象
最新十大排序算法详细讲解，以及各种应用场景_十大算法及其应用场景
赞
踩
文章目录
**
十大排序算法汇总
**
比较和非比较的区别
常见的快速排序、归并排序、堆排序、冒泡排序等属于比较排序。在排序的最终结果里，元素之间的次序依赖于它们之间的比较。每个数都必须和其他数进行比较，才能确定自己的位置。
在冒泡排序之类的排序中，问题规模为n，又因为需要比较n次，所以平均时间复杂度为O(n²)。在归并排序、快速排序之类的排序中，问题规模通过分治法消减为logN次，所以时间复杂度平均O(nlogn)。
比较排序的优势是，适用于各种规模的数据，也不在乎数据的分布，都能进行排序。可以说，比较排序适用于一切需要排序的情况。
计数排序、基数排序、桶排序则属于非比较排序。非比较排序是通过确定每个元素之前，应该有多少个元素来排序。针对数组arr，计算arr之前有多少个元素，则唯一确定了arr在排序后数组中的位置。
非比较排序只要确定每个元素之前的已有的元素个数即可，所有一次遍历即可解决。算法时间复杂度O(n)。
非比较排序时间复杂度底，但由于非比较排序需要占用空间来确定唯一位置。所以对数据规模和数据分布有一定的要求。
一些基本的术语
稳定：如果a原本在b前面，而a=b，排序之后a仍然在b的前面；
不稳定：如果a原本在b的前面，而a=b，排序之后a可能出现在b的后面；
内排序：所有的排序操作都在内存中完成；
外排序：由于数据太大，因此把数据放在磁盘中，而排序通过磁盘和内存的数据传输才能进行；
时间复杂度：一个算法执行所消耗的时间；
空间复杂度：运行完一个程序所需内存的大小。
排序算法复杂度及稳定性
一、冒泡排序
算法简介
1.从左向右依次对比相邻元素，将较大值交换到右边；
2.每一轮循环可将最大值交换到最左边
3.重复1.2两个步骤，直至完成整个数组。
动图演示
代码实现
/** * 冒泡算法的实现 * @param array * @return */ public static int[] bubbleSort(int[] array) { if(array.length==0) { return array; } for (int i = 0; i < array.length; i++) { for (int j = 0; j < array.length-1-i; j++) { if(array[j+1]<array[j]) { int temp=array[j]; array[j]=array[j+1]; array[j+1]=temp; } } } return array; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
应用场景
一般在学习的时候作为理解排序原理的时候使用，在实际应用中不会使用
算法分析
最佳情况：T(n) = O(n) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
二、快速排序
算法简介
1.选择一个元素赋值给中间元素temp，默认选择左边第一个元素，这样左边第一个元素的位置就空出来了；
2. 先从最右边的元素开始依次跟temp比较大小，大于等于temp元素的原地不动，遇到小于temp元素的则终止循环，把该元素赋值到左侧空出来的位置，同时左侧索引值自增，这是该元素原来的位置就空出；
3. 然后左侧元素开始依次跟temp比较大小，小于等于temp元素的原地不动，遇到大雨temp元素的则终止循环，把该元素赋值到右侧空出来的位置，同时右侧索引值自减；
4. 依次循环2,3步，直至左侧索引等于右侧索引，则完成一轮循环，把哨兵赋值到该索引的位置。
5. 在分别递归地对temp左右两侧的子数组进行1234步，直至递归子数组只有一个元素则排序完成
动图演示
代码实现
package leetcode; /** * 快速排序算法 * @author acer * */ public class Quick_sort { public void quicksort(int[] n, int left, int right) { int dp; if (left < right) { dp = partition(n, left, right); quicksort(n, left, dp - 1); quicksort(n, dp + 1, right); } } public int partition(int[] n, int left, int right) { int pivot = n[left];//选择第一个为参考点 while (left < right) { while (left < right && n[right] >= pivot)//让参考点与最右边的相比较，小于不动，大于右面减一 right--; if (left < right)//让小于参考点的数，进入空出来的位置， n[left++] = n[right]; while (left < right && n[left] <= pivot)//让参考点与左边的相比较，小于左面加一，大于不动 left++; if (left < right)//让大于参考点的数，进入空出来的位置 n[right--] = n[left]; } n[left] = pivot; return left; } public static void main(String[] args) { int[] a={49,38,65,97,76,13,27,47}; Quick_sort sort=new Quick_sort(); sort.quicksort(a, 0, a.length-1); for(int i=0;i<a.length;i++){ System.out.println(a[i]); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
算法分析
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(nlogn)
三、简单插入排序
算法简介
1.左边第一个元素可作为有序子数组；
2.从第二个元素开始，依次向前比较，大于该元素的则向右移一位，直到比该元素小的元素，插入其后；
3.依次向后推进，直至整个数组成为有序数组
动图演示
代码实现
package leetcode; public class Insert_sort { public static void main(String[] args) { int[] array= {3,3,345,2,753,4765,734658,567}; int[] arrayNew=Insert_sort.insert_sort(array); for (int i = 0; i < arrayNew.length; i++) { System.out.print(arrayNew[i]+" "); } } public static int[] insert_sort(int[] array) { if(array.length==0) { return array; } int current; for (int i = 0; i < array.length-1; i++) { current=array[i+1]; int preIndex=i; while(preIndex>=0&¤t<array[preIndex]) { array[preIndex+1]=array[preIndex]; preIndex--; } array[preIndex+1]=current; } return array; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
应用场景
如果大部分数据距离它正确的位置很近或者近乎有序？例如银行的业务完成的时间
如果是这样的话，插入排序是更好的选择。
算法分析
最佳情况：T(n) = O(n) 最坏情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
四、希尔排序
算法简介
1.首先选择一个步长值gap，以步长值为间隔把数组分为gap个子数组gap=length/2
2.对每个子数组进行插入排序；
3.逐步减小步长 gap = gap/2,重复对数组进行1，2 步骤；
4.当步长值减为1时，相当于对数组进行一次直接插入排序。
图片演示
代码实现
package leetcode; public class Shell_sort { public static void main(String[] args) { int[] array= {3,3,345,2,753,4765,734658,567,7}; int[] arrayNew=Shell_sort.shell_sort(array); for (int i = 0; i < arrayNew.length; i++) { System.out.print(arrayNew[i]+" "); } } public static int[] shell_sort(int[] array) { if(array.length==0) { return array; } int length=array.length; int temp,gap=length/2; while(gap>0) { for (int i = gap; i < length; i++) { temp=array[i]; int preIndex=i-gap; while(preIndex>=0&&array[preIndex]>temp) { array[preIndex+gap]=array[preIndex]; preIndex-=gap; } array[preIndex+gap]=temp; } gap/=2; } return array; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
算法的优点
相对于直接插入排序，希尔排序要高效很多，因为当gap 值较大时，对子数组进行插入排序时要移动的元素很少，元素移动的距离很大，这样效率很高；在gap逐渐减小过程中，数组中元素已逐渐接近排序的状态，所以需要移动的元素逐渐减少；当gap为1时，相当于进行一次直接插入排序，但是各元素已接近排序状态，需要移动的元素很少且移动的距离都很小。
算法分析
最佳情况：T(n) = O(nlog2 n) 最坏情况：T(n) = O(nlog2 n) 平均情况：T(n) =O(nlog2n)
五、简单选择排序
算法简介
首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
动图演示
代码实现
package leetcode; /** * 选择排序 * @author acer * */ public class Selection_sort { public static void main(String[] args) { int[] array= {3,3,345,2,753,4765,734658,567,7}; int[] arrayNew=Selection_sort.selection_sort(array); for (int i = 0; i < arrayNew.length; i++) { System.out.print(arrayNew[i]+" "); } } public static int[] selection_sort(int[] array) { if(array.length==0) { return array; } for(int i=0;i<array.length;i++) { int minIndex=i; for(int j=i;j<array.length;j++) { if(array[j]<array[minIndex])//找到最小的数 minIndex=j;//将最小数的索引保存 } int temp=array[minIndex]; array[minIndex]=array[i]; array[i]=temp; } return array; } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
应用场景
当数据量较小的时候适用
算法分析
最佳情况：T(n) = O(n2) 最差情况：T(n) = O(n2) 平均情况：T(n) = O(n2)
六、堆排序
算法简介
堆排序（Heapsort）是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构，并同时满足堆积的性质：即子结点的键值或索引总是小于（或者大于）它的父节点。堆排序可以说是一种利用堆的概念来排序的选择排序。分为两种方法：
大顶堆：每个节点的值都大于或等于其子节点的值，在堆排序算法中用于升序排列；
小顶堆：每个节点的值都小于或等于其子节点的值，在堆排序算法中用于降序排列；
图片演示
步骤一 构造初始堆。将给定无序序列构造成一个大顶堆（一般升序采用大顶堆，降序采用小顶堆)。
a.假设给定无序序列结构如下
2.此时我们从最后一个非叶子结点开始（叶结点自然不用调整，第一个非叶子结点 arr.length/2-1=5/2-1=1，也就是下面的6结点），从左至右，从下至上进行调整。
此处必须注意，我们把6和9比较交换之后，必须考量9这个节点对于其子节点会不会产生任何影响？因为其是叶子节点，所以不加考虑；但是，一定要熟练这种思维，写代码的时候就比较容易理解为什么会出现一次非常重要的交换了。
4.找到第二个非叶节点4，由于[4,9,8]中9元素最大，4和9交换。
在真正代码的实现中，这时候4和9交换过后，必须考虑9所在的这个节点位置，因为其上的值变了，必须判断对其的两个子节点是否造成了影响，这么说不合适，实际上就是判断其作为根节点的那棵子树，是否还满足大根堆的原则，每一次交换，都必须要循环把子树部分判别清楚。
这时，交换导致了子根[4,5,6]结构混乱，继续调整，[4,5,6]中6最大，交换4和6。
牢记上面说的规则，每次交换都要把改变了的那个节点所在的树重新判定一下，这里就用上了，4和9交换了，变动了的那棵子树就必须重新调整，一直调整到符合大根堆的规则为截。
此时，我们就将一个无序序列构造成了一个大顶堆。
步骤二 将堆顶元素与末尾元素进行交换，使末尾元素最大。然后继续调整堆，再将堆顶元素与末尾元素交换，得到第二大元素。如此反复进行交换、重建、交换。
a.将堆顶元素9和末尾元素4进行交换
这里，必须说明一下，所谓的交换，实际上就是把最大值从树里面拿掉了，剩下参与到排序的树，其实只有总结点的个数减去拿掉的节点个数了。所以图中用的是虚线。
b.重新调整结构，使其继续满足堆定义
c.再将堆顶元素8与末尾元素5进行交换，得到第二大元素8.
后续过程，继续进行调整，交换，如此反复进行，最终使得整个序列有序
代码实现
package leetcode; import java.util.Arrays; /** * 堆排序 * @author acer * */ public class HeapSort { public static void main(String[] args) { int[] array = new int[] { 2, 1, 4, 3, 6, 5, 8, 7 }; // 接下来就是排序的主体逻辑 sort(array); System.out.println(Arrays.toString(array)); } public static void sort(int[] array) { // 按照完全二叉树的特点，从最后一个非叶子节点开始，对于整棵树进行大根堆的调整 // 也就是说，是按照自下而上，每一层都是自右向左来进行调整的 // 注意，这里元素的索引是从0开始的 // 另一件需要注意的事情，这里的建堆，是用堆调整的方式来做的 // 堆调整的逻辑在建堆和后续排序过程中复用的 for (int i = array.length / 2 - 1; i >= 0; i--) { adjustHeap(array, i, array.length); } // 上述逻辑，建堆结束 // 下面，开始排序逻辑 for (int j = array.length - 1; j > 0; j--) { // 元素交换 // 说是交换，其实质就是把大顶堆的根元素，放到数组的最后；换句话说，就是每一次的堆调整之后，都会有一个元素到达自己的最终位置 swap(array, 0, j); // 元素交换之后，毫无疑问，最后一个元素无需再考虑排序问题了。 // 接下来我们需要排序的，就是已经去掉了部分元素的堆了，这也是为什么此方法放在循环里的原因 // 而这里，实质上是自上而下，自左向右进行调整的 adjustHeap(array, 0, j); } } /** * * @description 这里，是整个堆排序最关键的地方，正是因为把这个方法抽取出来，才更好理解了堆排序的精髓，会尽可能仔细讲解 * @author * @param * @return * @time 2018年3月9日 下午2:54:38 */ public static void adjustHeap(int[] array, int i, int length) { // 先把当前元素取出来，因为当前元素可能要一直移动 int temp = array[i]; // 可以参照sort中的调用逻辑，在堆建成，且完成第一次交换之后，实质上i=0；也就是说，是从根所在的最小子树开始调整的 // 接下来的讲解，都是按照i的初始值为0来讲述的 // 这一段很好理解，如果i=0；则k=1；k+1=2 // 实质上，就是根节点和其左右子节点记性比较，让k指向这个不超过三个节点的子树中最大的值 // 这里，必须要说下为什么k值是跳跃性的。 // 首先，举个例子，如果a[0] > a[1]&&a[0]>a[2],说明0,1,2这棵树不需要调整，那么，下一步该到哪个节点了呢？肯定是a[1]所在的子树了， // 也就是说，是以本节点的左子节点为根的那棵小的子树 // 而如果a[0}<a[2]呢，那就调整a[0]和a[2]的位置，然后继续调整以a[2]为根节点的那棵子树，而且肯定是从左子树开始调整的 // 所以，这里面的用意就在于，自上而下，自左向右一点点调整整棵树的部分，直到每一颗小子树都满足大根堆的规律为止 for (int k = 2 * i + 1; k < length; k = 2 * k + 1) { // 让k先指向子节点中最大的节点 if (k + 1 < length && array[k] < array[k + 1]) { k++; } // 如果发现子节点更大，则进行值的交换 if (array[k] > temp) { swap(array, i, k); // 下面就是非常关键的一步了 // 如果子节点更换了，那么，以子节点为根的子树会不会受到影响呢？ // 所以，循环对子节点所在的树继续进行判断 i = k; // 如果不用交换，那么，就直接终止循环了 } else { break; } } } /** * 交换元素 * * @param arr * @param a * 元素的下标 * @param b * 元素的下标 */ 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
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
应用场景
堆排序适合于数据量非常大的场合（百万数据）。
堆排序不需要大量的递归或者多维的暂存数组。这对于数据量非常巨大的序列是合适的。比如超过数百万条记录，因为快速排序，归并排序都使用递归来设计算法，在数据量非常大的时候，可能会发生堆栈溢出错误。
堆排序会将所有的数据建成一个堆，最大的数据在堆顶，然后将堆顶数据和序列的最后一个数据交换。接下来再次重建堆，交换数据，依次下去，就可以排序所有的数据。
算法分析
最佳情况：T(n) = O(nlogn) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
七、二路归并排序
算法简介
分：
1.一直分两组，分别对两个数组进行排序(根据上层对下层在一组的数据通过临时数组排序，再将有序数组挪回上层数组中)。
2. 循环第一步，直到划分出来的“小组”只包含一个元素，只有一个元素的数组默认为已经排好序。
合：（合并时，站在上层合并下层（使组内有序））
1.将两个有序的数组合并到一个大的数组中。
2.从最小的只包含一个元素的数组开始两两合并。此时，合并好的数组也是有序的。最后把小组合成一个组。
图片演示
代码实现
public class MergeSort { /** * 归并排序 * @param arr * @param left * @param right */ public static void mergeSort(int[] arr, int left, int right) { if(null == arr) { return; } if(left < right) { //找中间位置进行划分 int mid = (left+right)/2; //对左子序列进行递归归并排序 mergeSort(arr, left, mid); //对右子序列进行递归归并排序 mergeSort(arr, mid+1, right); //“合”。 进行归并 merge(arr, left, mid, right); } } /** * 进行归并 * @param arr * @param left * @param mid * @param right */ private static void merge(int[] arr, int left, int mid, int right) { int[] tempArr = new int[arr.length]; int leftStart = left; int rightStart = mid+1; int tempIndex = left; while(leftStart <= mid && rightStart <= right) { if(arr[leftStart] < arr[rightStart]) { tempArr[tempIndex++] = arr[leftStart++]; } else { tempArr[tempIndex++] = arr[rightStart++]; } } while(leftStart <= mid) { tempArr[tempIndex++] = arr[leftStart++]; } while(rightStart <= right) { tempArr[tempIndex++] = arr[rightStart++]; } while(left <= right) { arr[left] = tempArr[left++]; } } private static void showArr(int[] arr) { for(int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } } public static void main(String[] args) { int[] arr = {4, 2, 6, 1, 3, 8, 5, 9}; /* * 归并排序 * 对上下限值分别为0和arr.length-1的记录序列arr进行归并排序 */ mergeSort(arr, 0, arr.length-1); showArr(arr); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
应用场景
内存空间不足的时候使用归并排序，能够使用并行计算的时候使用归并排序。
算法分析
最佳情况：T(n) = O(n) 最差情况：T(n) = O(nlogn) 平均情况：T(n) = O(nlogn)
八、计数排序
算法简介
找出待排序的数组中最大和最小的元素；
统计数组中每个值为i的元素出现的次数，存入数组C的第i项；
对所有的计数累加（从C中的第一个元素开始，每一项和前一项相加）；
反向填充目标数组：将每个元素i放在新数组的第C(i)项，每放一个元素就将C(i)减去1。
动图演示
代码实现
public class CountSort { private static int[] countsort(int[] arr) { int max=arr[0]; int min=arr[0]; //step1:得到最大值和最小值，确定构建的数组长度 for (int i = 0; i < arr.length; i++) { if(arr[i]>max) { max=arr[i]; } if(arr[i]<min) { min=arr[i]; } } //step2:构建一个数组，用来存放每一个数对应出现的次数 int d=max-min; int [] countArray=new int [d+1]; //统计次数 for (int i = 0; i < arr.length; i++) { countArray[arr[i]-min]++; } System.out.println("统计不同元素出现的次数："+Arrays.toString( countArray)); //step3:对此时的数组做变形,统计数组从第二个元素开始，每一个元素等于它本身都加上前面所有元素之和。 for(int i=1;i<countArray.length;i++) { countArray[i]+=countArray[i-1]; } System.out.println("变形后的数组："+Arrays.toString( countArray)); //step4:倒序遍历原始数列，从统计数组找到正确位置，输出到结果数组,确保稳定性 int[] sortedArray = new int[arr.length]; for(int i=arr.length-1;i>=0;i--) { sortedArray[countArray[arr[i]-min]-1]=arr[i]; countArray[arr[i]-min]--; } return sortedArray; } public static void main(String[] args) { int arr[]={93,95,98,98,94,92,96,91}; int[] sortedArray=countsort(arr); System.out.println("结果输出："+Arrays.toString(sortedArray)); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
应用场景
计数排序需要占用大量空间，它仅适用于数据比较集中的情况。比如 [0100]，[1000019999] 这样的数据。
算法分析
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n+k)
九、桶排序
算法简介
桶排序(Bucket Sort)的原理很简单，它是将数组分到有限数量的桶子里。
假设待排序的数组a中共有N个整数，并且已知数组a中数据的范围[0, MAX)。在桶排序时，创建容量为MAX的桶数组r，并将桶数组元素都初始化为0；将容量为MAX的桶数组中的每一个单元都看作一个"桶"。
在排序时，逐个遍历数组a，将数组a的值，作为"桶数组r"的下标。当a中数据被读取时，就将桶的值加1。例如，读取到数组a[3]=5，则将r[5]的值+1。
图片演示
bucketSort(a, n, max)是作用是对数组a进行桶排序，n是数组a的长度，max是数组中最大元素所属的范围[0,max)。
假设a={8,2,3,4,3,6,6,3,9}, max=10。此时，将数组a的所有数据都放到需要为0-9的桶中。如下图：
代码实现
package leetcode; /** * 桶排序 * @author acer * */ public class BucketSort { /* * 桶排序 * * 参数说明： * a -- 待排序数组 * max -- 数组a中最大值的范围 */ public static void bucketSort(int[] a, int max) { int[] buckets; if (a==null || max<1) return ; // 创建一个容量为max的数组buckets，并且将buckets中的所有数据都初始化为0。 buckets = new int[max]; // 1. 计数 for(int i = 0; i < a.length; i++) buckets[a[i]]++; // 2. 排序 for (int i = 0, j = 0; i < max; i++) { while( (buckets[i]--) >0 ) { a[j++] = i; } } buckets = null; } public static void main(String[] args) { int i; int a[] = {8,2,3,4,3,6,6,3,9}; System.out.printf("before sort:"); for (i=0; i<a.length; i++) System.out.printf("%d ", a[i]); System.out.printf("\n"); bucketSort(a, 10); // 桶排序 System.out.printf("after sort:"); for (i=0; i<a.length; i++) System.out.printf("%d ", a[i]); System.out.printf("\n"); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
算法分析
桶排序最好情况下使用线性时间O(n)，桶排序的时间复杂度，取决与对各个桶之间数据进行排序的时间复杂度，因为其它部分的时间复杂度都为O(n)。很显然，桶划分的越小，各个桶之间的数据越少，排序所用的时间也会越少。但相应的空间消耗就会增大。
最佳情况：T(n) = O(n+k) 最差情况：T(n) = O(n+k) 平均情况：T(n) = O(n2)
十、基数排序
算法简介
相比其它排序，主要是利用比较和交换，而基数排序则是利用分配和收集两种基本操作。基数 排序是一种按记录关键字的各位值逐步进行排序的方法。此种排序一般适用于记录的关键字为整数类型的情况。所有对于字符串和文字排序不适合。
实现：将所有待比较数值（自然数）统一为同样的数位长度，数位较短的数前面补零。然后，从最低位开始，依次进行一次排序。这样从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。
基数排序的两种方式：
高位优先，又称为最有效键(MSD),它的比较方向是由右至左；
低位优先，又称为最无效键(LSD),它的比较方向是由左至右；
动图演示
代码实现
package leetcode; import java.util.Arrays; /** * 基数排序演示 * * */ public class RadixSort { public static void main(String[] args) { int[] arr = {63, 157, 189, 51, 101, 47, 141, 121, 157, 156, 194, 117, 98, 139, 67, 133, 181, 12, 28, 0, 109}; radixSort(arr); System.out.println(Arrays.toString(arr)); } /** * 高位优先法 * * @param arr 待排序列，必须为自然数 */ private static void radixSort(int[] arr) { //待排序列最大值 int max = arr[0]; int exp;//指数 //计算最大值 for (int anArr : arr) { if (anArr > max) { max = anArr; } } //从个位开始，对数组进行排序 for (exp = 1; max / exp > 0; exp *= 10) { //存储待排元素的临时数组 int[] temp = new int[arr.length]; //分桶个数 int[] buckets = new int[10]; //将数据出现的次数存储在buckets中 for (int value : arr) { //(value / exp) % 10 :value的最底位(个位) buckets[(value / exp) % 10]++; } //更改buckets[i]， for (int i = 1; i < 10; i++) { buckets[i] += buckets[i - 1]; } //将数据存储到临时数组temp中 for (int i = arr.length - 1; i >= 0; i--) { temp[buckets[(arr[i] / exp) % 10] - 1] = arr[i]; buckets[(arr[i] / exp) % 10]--; } //将有序元素temp赋给arr System.arraycopy(temp, 0, arr, 0, arr.length); } } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
算法分析
最佳情况：T(n) = O(n * k) 最差情况：T(n) = O(n * k) 平均情况：T(n) = O(n * k)
基数排序有两种方法：
MSD 从高位开始进行排序 LSD 从低位开始进行排序
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念，但对桶的使用方法上有明显差异：
基数排序：根据键值的每位数字来分配桶
计数排序：每个桶只存储单一键值
桶排序：每个桶存储一定范围的数值
一些基本情况
数据有什么特征
有没有可能包含有大量重复的元素
如果有这种可能的话，三路快排是更好地选择
是否数据的取值范围非常有限，比如对学生的成绩排序。
如果是这样的话，计数排序是更好的选择
对排序有什么额外的要求
是否需要稳定排序
如果是的话，归并排序是更好的选择，快排就不怎么好了
数据的存储状况是怎么样的
快排是依赖于数组的随机存储
如果是使用链表存储的
如果是的话，归并排序是更好的选择，
数据的存储状况是怎么样的
数据的大小是否可以装在在内存里
数据量很大或者内存很小，不足以装载在内存里，需要使用外排序算法。
