教务处网站建设,wordpress sql过滤,装饰网站开发背景,人设生成器网站冒泡算法 依次比较两个相邻的子元素#xff0c;如果他们的顺序错误就把他们交换过来#xff0c;重复地进行此过程直到没有相邻元素需要交换#xff0c;即完成整个冒泡#xff0c;时间复杂度。 比较相邻的元素。如果第一个比第二个大#xff0c;就交换它们两个#xff1b;…冒泡算法 依次比较两个相邻的子元素如果他们的顺序错误就把他们交换过来重复地进行此过程直到没有相邻元素需要交换即完成整个冒泡时间复杂度。 比较相邻的元素。如果第一个比第二个大就交换它们两个对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对这样在最后的元素应该会是最大的数针对所有的元素重复以上的步骤除了最后一个重复步骤1~3直到排序完成。 Java /*** 冒泡排序* param array* return*/public static int[] bubbleSort(int[] array){if(array.length 0){for(int i 0;iarray.length;i){for(int j 0;jarray.length - 1 - i;j){if(array[j] array[j1]){int temp array[j];array[j] array[j1];array[j1] temp;}}}}return array;} 优化后可减少循环次数 //定义标志位用于判定最外层每一轮是否进行了交换boolean flag false;for (int i 0; i arr.length - 1; i) {for (int j 0; j arr.length - 1 - i; j) {if (arr[j] arr[j 1]) {//进入这个if分支里边则说明有元素进行了交换//所以将flagtrueflag true;int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}//在进行一轮的排序后判断是否发生了元素是否交换if (!flag) {// 没有交换数组已是有序则结束排序break;} else {//如果发生交换将flag再次置为false进行下一轮排序flag false;}}
Python
from typing import List# 冒泡排序
def bubble_sort(arr: List[int]):冒泡排序(Bubble sort):param arr: 待排序的List,此处限制了排序类型为int:return: 冒泡排序是就地排序(in-place)length len(arr)if length 1:returnfor i in range(length):设置标志位若本身已经有序则直接breakis_made_swap Falsefor j in range(length - i - 1):if arr[j] arr[j 1]:arr[j], arr[j 1] arr[j 1], arr[j]is_made_swap Trueif not is_made_swap:breakreturn arrif __name__ __main__:arr bubble_sort([55, 34, 55, 33, 13, 45, 67])print(arr)Js
for(var i0;iarr.length-1;i){//确定轮数for(var j0;jarr.length-i-1;j){//确定每次比较的次数if(arr[j]arr[j1]){tem arr[j];arr[j] arr[j1];arr[j1] tem;}}}选择排序 每一趟从待排序数组中选出最小的数字按顺序放在已经排好序的数组的后面直到全部排完。 时间复杂度 空间复杂度(常规) 初始状态无序区为R[1..n]有序区为空第i趟排序(i1,2,3…n-1)开始时当前有序区和无序区分别为R[1..i-1]和R(i..n。该趟排序从当前无序区中-选出关键字最小的记录 R[k]将它与无序区的第1个记录R交换使R[1..i]和R[i1..n)分别变为记录个数增加1个的新有序区和记录个数减少1个的新无序区n-1趟结束数组有序化了 选择排序 Java
private static Integer[] selectSort(Integer[] arr) {/*初始化左端、右端元素索引*/int left 0;int right arr.length - 1;while (left right) {/*初始化最小值、最大值元素的索引*/int min left;int max right;for (int i left; i right; i) {/*标记每趟比较中最大值和最小值的元素对应的索引min、max*/if (arr[i] arr[min])min i;if (arr[i] arr[max])max i;}/*最大值放在最右端*/int temp arr[max];arr[max] arr[right];arr[right] temp;/*此处是先排最大值的位置所以得考虑最小值arr[min]在最大位置right的情况*/if (min right)min max;/*最小值放在最左端*/temp arr[min];arr[min] arr[left];arr[left] temp;/*每趟遍历元素总个数减少2左右端各减少1left和right索引分别向内移动1*/left;right--;}return arr;}// 测试public static void main(String[] args) {Integer[] arr new Integer[]{77, 22, 3, 4, 1, 44, 34, 41};Integer[] arrs selectSort(arr);for (Integer integer : arrs) {System.out.println(integer);}}
Python
def selectionSort(A):le len(A)for i in range(le): # 遍历次数for j in range(i 1, le): # 查找待排序序列中的最小元素并交换if A[i] A[j]:A[i], A[j] A[j], A[i]print(A)tes [22, 41, 55, 46, 4, 5, 3, 32, 454]
selectionSort(tes) # [3, 4, 5, 22, 32, 41, 46, 55, 454]Js
var arr [2, 8, 6, 2, 9, 7, 3, 11, 6]//从第0次开始for (var j 0; j arr.length - 1; j) {var minIndex jfor (var i j 1; i arr.length; i) {if (arr[i] arr[minIndex]) minIndex i}if (minIndex ! j) {var tmp arr[j]arr[j] arr[minIndex]arr[minIndex] tmp}
}console.log(arr)插入排序 将一个记录插入到已经排序好的有序表中从而得到一个新的、记录增加1的有序表。在实现过程中使用双层循环外层循环对除了第一个元素之外的所有元素内层循环对当前元素前面有序表进行待插入位置查找进行移动。时间复杂度 空间复杂度(常规) 从第一个元素开始该元素可以认为已经被排序取出下一个元素在已经排序的元素序列中从后向前扫描如果该元素已排序大于新元素将该元素移到下一位置重复步骤3直到找到已排序的元素小于或者等于新元素的位置将新元素插入到该位置后重复步骤2~5。 Java 直接插入排序
public static void insertSort2 (int[] numbers) {//控制循环轮数for (int i 1; i numbers.length; i) {int temp numbers[i]; //定义待交换元素int j; //定义待插入的位置for (j i; j 0 temp numbers[j - 1]; j --) {numbers[j] numbers[j - 1];}numbers[j] temp;System.out.println(第 i 轮的排序结果为 Arrays.toString(numbers));}System.out.println(排序后的结果为 Arrays.toString(numbers));} 折半插入排序 在直接插入排序的基础上将查找方法从顺序查找改为折半查找就是在将 将要插入到现有 有序序列的数字寻找适当插入位置的比较次数减少了。 private static void bInsertSort(int[] s){for(int i1;is.length;i){int temps[i];//保存要插入的数的数值int low0;//设置查找区间初始值 下区间值int highi-1;//上区间值while(lowhigh){//查找结束条件int mid(highlow)/2;//折半中间值if(s[mid]temp){//待插入值小于中间值highmid-1;//上区间值变为中间值-1}else {//待插入值大于中间值lowmid1;//下区间值变为中间值1}}for (int ji-1;jlow;j--){s[j1]s[j];//将low及low之前的数向前移动一位}s[low]temp;//low就是待插入值的适当插入点}System.out.println(Arrays.toString(s));//输出排好序的数组}Python
import pandas as pd
import random
import timeimport seaborn as sns
import matplotlib.pyplot as plt# 解决win 系统中文不显示问题
from pylab import mpl
mpl.rcParams[font.sans-serif][SimHei]def insert_sort(tg_list): 排序算法插入排序 for i in range(1,len(tg_list)):for j in range(i,0,-1):if tg_list[j] tg_list[j-1]:tg_list[j-1], tg_list[j] tg_list[j], tg_list[j-1]else:breakdef get_runtime(n): 获取排序耗时 time_start time.clock() # 记录开始时间list_ [random.randint(1,n) for i in range(n)]insert_sort(list_)time_end time.clock() # 记录结束时间time_sum time_end - time_start # 计算的时间差为程序的执行时间单位为秒/sreturn [n,time_sum]def plot(df): 绘制折线图 pd.options.display.notebook_repr_htmlFalse # 表格显示plt.rcParams[figure.dpi] 75 # 图形分辨率sns.set_style(styledarkgrid) # 图形主题plt.figure(figsize(4,3),dpi150)sns.lineplot(datadf,x数量,y耗时(s))if __name__ __main__:nums range(100,10000,100)res list(map(get_runtime,nums))res_df pd.DataFrame(res,columns[数量,耗时(s)])plot(res_df)Js function insertSort(arr) {var len arr.length;for (var i1;ilen; i) {var temparr[i];var ji-1;//默认已排序的元素while (j0 arr[j]temp) { //在已排序好的队列中从后向前扫描arr[j1]arr[j]; //已排序的元素大于新元素将该元素移到一下个位置j--;}arr[j1]temp;}return arr} 二分插入排序
function binaryInsertSort(arr) {var len arr.length;for (var i1;ilen; i) {var keyarr[i],left0,righti-1;while(leftright){ //在已排序的元素中二分查找第一个比它大的值var mid parseInt((leftright)/2); //二分查找的中间值if(keyarr[mid]){ //当前值比中间值小 则在左边的子数组中继续寻找 right mid-1;}else{leftmid1;//当前值比中间值大 在右边的子数组继续寻找}} for(var ji-1;jleft;j--){arr[j1]arr[j];}arr[left]key;}return arr;}
快速排序 每趟排序时选出一个基准值然后将所有元素与该基准值比较并按大小分成左右两堆然后递归执行该过程直到所有元素都完成排序。 从数列中挑出一个元素称为 “基准”pivot重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序 Java ##--------------------------第一版----------------------------------------public static void quickSort1(int[] arr) {if (arr null || arr.length 2) {return;}process1(arr, 0, arr.length - 1);}//第一版快排这一版的时间复杂度为O(n2)public static void process1(int[] arr, int L, int R) {if (L R) {return;}//在[L,R]范围上根据arr[R]模仿netherlandsFlag方法//将数组分为三个部分arr[R]的部分arr[R]本身//arr[R]的部分这样确定了在最终的数组中arr[R]的位置//并返回这个位置int M partition(arr, L, R);//接下来只要在左右两侧重复这个过程就行process1(arr, L, M - 1);process1(arr, M 1, R);}public static int partition(int[] arr, int L, int R) {if (L R) {return -1;}if (L R) {return L;}int lessEqual L - 1;int index L;while (index R) {if (arr[index] arr[R]) {swap(arr, index, lessEqual);}index;}swap(arr, lessEqual, R);return lessEqual;}##--------------------------第二版----------------------------------------public static void quickSort2(int[] arr) {if (arr null || arr.length 2) {return;}process2(arr, 0, arr.length - 1);}//第二版快排相比第一版的区别/优势在于一次可以确定//相等基准值的一个区域而不再只是一个值//第二版的时间复杂度为O(n2)public static void process2(int[] arr, int L, int R) {if (L R) {return;}int[] equalArea netherlandsFlag(arr, L, R);process2(arr, L, equalArea[0] - 1);process2(arr, equalArea[1] 1, R);}//这个方法的目的是按arr[R]为基准值将arr数组划分为小于基准值、//等于基准值、大于基准值三个区域//在arr[L...R]上以arr[R]做基准值在[L...R]范围内arr[R]的数//都放在左侧arr[R]的数放在中间arr[R]的数放在右边//返回的值为和arr[R]相等的范围的数组public static int[] netherlandsFlag(int[] arr, int L, int R) {if (L R) {return new int[] { -1, -1 };}if (L R) {return new int[] { L, R };}//小于基准值的区域的右边界int less L - 1;//大于基准值的区域的左边界int more R;int index L;while (index more) {//等于基准值不做处理判断下一个数据if (arr[index] arr[R]) {index;//当前数小于基准值} else if (arr[index] arr[R]) {//将当前值和小于区域右边的一个值交换swap//判断下一个数据index//小于区域右移less先是为了完成swapswap(arr, index, less);} else {//将当前值和大于区域左边的一个值交换swap//大于区域左移--more先--是为了完成swapswap(arr, index, --more);}}//因为最开始是把arr[R]作为基准值的所以在进行接下来的一步之前//arr[R]实际是在大于区域的最右侧的所以还需要进行一步交换这样//整个数组就成了小于区域、等于区域、大于区域的样子swap(arr, more, R);//less 1是等于区域的起始位置more经过上一步的和arr[R]交换后//就成了等于区域的结束位置return new int[] { less 1, more };}##--------------------------第三版----------------------------------------public static void quickSort3(int[] arr) {if (arr null || arr.length 2) {return;}process3(arr, 0, arr.length - 1);}//第三版快排不再固定去arr[R]改为去随机位置的值然后//和arr[R]进行交换接下来的过程就和第二版一样//第三版的复杂度变化了是O(nlogn)该事件复杂度是最终求//的是数学上的一个平均期望值public static void process3(int[] arr, int L, int R) {if (L R) {return;}swap(arr, L (int) (Math.random() * (R - L 1)), R);int[] equalArea netherlandsFlag(arr, L, R);process3(arr, L, equalArea[0] - 1);process3(arr, equalArea[1] 1, R);}public static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;}Python
# codingutf-8
def quick_sort(array, start, end):if start end:returnmid_data, left, right array[start], start, endwhile left right:while array[right] mid_data and left right:right - 1array[left] array[right]while array[left] mid_data and left right:left 1array[right] array[left]array[left] mid_dataquick_sort(array, start, left-1)quick_sort(array, left1, end)if __name__ __main__:array [11, 14, 34, 7, 30, 14, 27, 45, 25, 5, 66, 11]quick_sort(array, 0, len(array)-1)print(array) Js
function quickSort( arr ) {if(arr.length 1) return arr;const num arr[0];let left [], right [];for(let i 1;i arr.length; i) {if(arr[i]num) left.push(arr[i]);else right.push(arr[i]);}return quickSort(left).concat([num],quickSort(right));
}堆排序 利用堆这种数据结构而设计的一种排序算法堆排序是一种选择排序它的最坏最好平均时间复杂度均为0(nlogn)它也是不稳定排序。 将初始待排序关键字序列(R1,R2….Rn)构建成大顶堆此堆为初始的无序区将堆顶元素R[1]与最后一个元素R[n]交换此时得到新的无序区(R1,R2,……Rn-1)和新的有序区(Rn),且满足R[1,2…n-1]R[n]由于交换后新的堆顶R[1]可能违反堆的性质因此需要对当前无序区(R1,R2,……Rn-1)调整为新堆然后再次将R[1]与无序区最后一个元素交换得到新的无序区(R1,R2….Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数为n-1则整个排序过程完成。 Java public static void sort(int []arr){//1.构建大顶堆for(int iarr.length/2-1;i0;i--){//从第一个非叶子结点从下至上从右至左调整结构adjustHeap(arr,i,arr.length);}//2.调整堆结构交换堆顶元素与末尾元素for(int jarr.length-1;j0;j--){swap(arr,0,j);//将堆顶元素与末尾元素进行交换adjustHeap(arr,0,j);//重新对堆进行调整}}/*** 调整大顶堆仅是调整过程建立在大顶堆已构建的基础上* param arr* param i* param length*/public static void adjustHeap(int []arr,int i,int length){int temp arr[i];//先取出当前元素ifor(int ki*21;klength;kk*21){//从i结点的左子结点开始也就是2i1处开始if(k1length arr[k]arr[k1]){//如果左子结点小于右子结点k指向右子结点k;}if(arr[k] temp){//如果子节点大于父节点将子节点值赋给父节点不用进行交换arr[i] arr[k];i k;}else{break;}}arr[i] temp;//将temp值放到最终的位置}/*** 交换元素* param arr* param a* param b*/public static void swap(int []arr,int a ,int b){int temparr[a];arr[a] arr[b];arr[b] temp;}Python
建堆-调堆-排序 def heapify(unsorted, index, heap_size):largest indexleft_index 2 * index 1right_index 2 * index 2if left_index heap_size and unsorted[left_index] unsorted[largest]:largest left_indexif right_index heap_size and unsorted[right_index] unsorted[largest]:largest right_indexif largest ! index:unsorted[largest], unsorted[index] unsorted[index], unsorted[largest]heapify(unsorted, largest, heap_size)
def heap_sort(unsorted):n len(unsorted)for i in range(n // 2 - 1, -1, -1):heapify(unsorted, i, n)for i in range(n - 1, 0, -1):unsorted[0], unsorted[i] unsorted[i], unsorted[0]heapify(unsorted, 0, i)return unsortedif __name__ __main__:test [4,3,2,1]print(heap_sort(test)) Js
/*调整函数param arr 待排序的数组param i 表示等待调整的那个非叶子节点的索引param length 待调整长度
*/
function adjustHeap(arr,i,length){var notLeafNodeVal arr[i]; //非叶子节点的值//for循环,k的初始值为当前非叶子节点的左孩子节点的索引//k 2*k1表示再往左子节点找for(var ki*21;klength;k2*k1){//如果k1还在待调整的长度内且右子树的值大于等于左子树的值//将k,此时为当前节点的右孩子节点的索引if(k1length arr[k]arr[k1]){k;}//如果孩子节点大于当前非叶子节点if(arr[k]notLeafNodeVal){arr[i] arr[k]; //将当前节点赋值为孩子节点的值i k;//将i赋值为孩子的值,再看其孩子节点是否有比它大的}else{break; //能够break的保证是从左到右、从上到下进行调整//只要上面的不大于,下面的必不大于}}//循环结束后,将i索引处的节点赋值为之前存的那个非叶子节点的值arr[i] notLeafNodeVal;
}//堆排序函数
function heapSort(arr){//进行第一次调整for(var iparseInt(arr.length/2)-1;i0;i--){adjustHeap(arr,i,arr.length);}for(var jarr.length-1;j0;j--){/*进行交换:第一次调整的时候从左到右、从上到下的;交换时只是变动了堆顶元素和末尾元素,末尾元素不用去管,因为已经是之前长度最大的了,只需要把当前堆顶元素找到合适的位置即可*/var temp arr[j];arr[j] arr[0];arr[0] temp;adjustHeap(arr,0,j);}
}var arr [0,2,4,1,5];
console.log(排序前的数组,arr);
heapSort(arr);
console.log(排序后的数组,arr);
希尔排序 插入排序的一种算法先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录基本有序时再对全体记录进行依次直接插入排序。时间复杂度O(N^1.3) 选择一个增量序列t1t2…tk其中titjtk1按增量序列个数k对序列进行k 趟排序每趟排序根据对应的增量ti将待排序列分割成若干长度为m 的子序列分别对各子表进行直接插入排序。仅增量因子为1 时整个序列作为一个表来处理表长度即为整个序列的长度。 Java /*初始化划分增量*/int increment len; int j,temp,low,mid,high;/*每次减小增量直到increment 1*/while (increment 1){ /*增量的取法之一除三向下取整1*/increment increment/3 1;/*对每个按增量划分后的逻辑分组进行直接插入排序*/for (int i increment; i len; i) { low 0;high i-1;temp arr[i];while(low high){mid (lowhigh)/2;if(arr[mid]temp){high mid-1;}else{low mid1;}}j i-increment;/*移动元素并寻找位置*/while(j high1){ arr[jincrement] arr[j];j - increment;} /*插入元素*/arr[jincrement] temp; }}Python
# 希尔排序
def shell_sort(input_list):# 希尔排序三重循环依次插入直接插入法的优化版l input_list # 简化参数名gaps [701, 301, 132, 57, 23, 10, 4, 1] # Marcin Ciuras gap sequencefor gap in gaps:for i in range(gap, len(l)):insert_value l[i] # 终止条件j iwhile j gap and l[j - gap] insert_value:l[j] l[j - gap]j - gapif j ! i:l[j] insert_value # 循环终止插入值return l
# 另外一种写法
def shell_sort(input_list):# 希尔排序三重循环依次插入直接插入法的优化版l input_list # 简化参数名gap len(l) // 2 # 长度取半while gap 0:for i in range(gap, len(l)):insert_value l[i] # 终止条件j iwhile j gap and l[j - gap] insert_value:l[j] l[j - gap]j - gapif j ! i:l[j] insert_value # 循环终止插入值gap // 2return l
if __name__ __main__:test [4,3,2,1]print(shell_sort(test))
Js
function shellSort(arr) {let len arr.length;for (let gap Math.floor(len / 2); gap 0; gap Math.floor(gap / 2)) {for (let i gap; i len; i) {let j i;let current arr[i];while (j - gap 0 arr[j - gap] current) {arr[j] arr[j - gap];j j - gap;}arr[j] current;}}return arr;
}归并排序 归并排序是建立在归并操作上的一种有效的排序算法该算法是采用分治法的一个非常典型的应用。将已有序的子 序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序 表称为二路归并。时间复杂度为O(nlogn) 把长度为n的输入序列分成两个长度为n/2的子序列对这两个子序列分别采用归并排序将两个排序好的子序列合并成一个最终的排序序列。 Java
public class Merge02 {private static Comparable[] assist;public void sort(Comparable[] arr) {assist new Comparable[arr.length];sort(arr, 0, arr.length - 1);}public void sort(Comparable[] arr, int lo, int hi) {if (lo hi) {return;}int mid lo (hi - lo) / 2;sort(arr, lo, mid);sort(arr, mid 1, hi);merge(arr, lo, mid, hi);}public void merge(Comparable[] arr, int lo, int mid, int hi) {int i lo;int p1 lo;int p2 mid 1;while (p1 mid p2 hi) {if (arr[p1].compareTo(arr[p2]) 0) {assist[i] arr[p2];} else {assist[i] arr[p1];}}while (p1 mid) {assist[i] arr[p1];}while (p2 hi) {assist[i] arr[p2];}for (int index lo; index hi; index) {arr[index] assist[index];}}
}Python
#merge的功能是将前后相邻的两个有序表归并为一个有序表的算法。
def merge(left, right):ll, rr 0, 0result []while ll len(left) and rr len(right):if left[ll] right[rr]:result.append(left[ll])ll 1else:result.append(right[rr])rr 1resultleft[ll:]resultright[rr:]return resultdef merge_sort(alist):if len(alist) 1:return alistnum len(alist) // 2 # 从中间划分两个子序列left merge_sort(alist[:num]) # 对左侧子序列进行递归排序right merge_sort(alist[num:]) # 对右侧子序列进行递归排序return merge(left, right) #归并tesl[1,3,45,23,23,12,43,45,33,21]
print(merge_sort(tesl))
#[1, 3, 12, 21, 23, 23, 33, 43, 45, 45]Js
// 合并做分支数组和右分支数组左分支和右分支在自己数组里面已经是有序的。所以就方便很多。
function merge(left, right){// 剪枝优化if(left[left.length -1] right[0]){return left.concat(right)}if(right[right.length-1] left[0]){return right.concat(left)}let tmp [];let leftIndex 0, rightIndex 0;while(leftIndex left.length rightIndex right.length) {if(left[leftIndex] right[rightIndex]) {tmp.push(left[leftIndex]);leftIndex ;}else{tmp.push(right[rightIndex]);rightIndex ;}}// 最后检查一下是否有数组内容没有拷贝完if(leftIndex left.length){tmp tmp.concat(left.slice(leftIndex))}if(rightIndex right.length){tmp tmp.concat(right.slice(rightIndex))}return tmp;
}function mergeSort(arr){// 拆到只有一个元素的时候就不用再拆了。if(arr.length 2){return arr;}const mid arr.length/2;const left arr.slice(0, mid);const right arr.slice(mid);const leftSplited mergeSort(left);const rightSplited mergeSort(right);return merge(leftSplited, rightSplited);
} 基数排序Radix Sort 基数排序是按照低位先排序然后收集再按照高位排序然后再收集依次类推直到最高位。有时候有些属性是有优先级顺序的先按低优先级排序再按高优先级排序。最后的次序就是高优先级高的在前高优先级相同的低优先级高的在前。基数排序基于分别排序分别收集所以是稳定的。 基数排序的平均时间复杂度为 O(nk)k 为最大元素的长度最坏时间复杂度为 O(nk)空间复杂度为 O(n) 是稳定排序。 取得数组中的最大数并取得位数即为迭代次数n例如数组中最大数为123则 n3arr为原始数组从最低位或最高位开始根据每位的数字组成radix数组radix数组是个二维数组其中一维长度为10例如123在第一轮时存放在下标为3的radix数组中将radix数组中的数据从0下标开始依次赋值给原数组重复2~3步骤n次即可。 Java
public static void radixSort(int[] arr) {if (arr.length 2) return;int maxVal arr[0];//求出最大值for (int a : arr) {if (maxVal a) {maxVal a;}}int n 1;while (maxVal / 10 ! 0) {//求出最大值位数maxVal / 10;n;}for (int i 0; i n; i) {ListListInteger radix new ArrayList();for (int j 0; j 10; j) {radix.add(new ArrayList());}int index;for (int a : arr) {index (a / (int) Math.pow(10, i)) % 10;radix.get(index).add(a);}index 0;for (ListInteger list : radix) {for (int a : list) {arr[index] a;}}}}Python
def radix_sort(input_list):RADIX 10placement 1max_digit max(input_list)while placement max_digit:buckets: list[list] [list() for _ in range(RADIX)]for i in input_list:tmp int((i / placement) % RADIX)buckets[tmp].append(i)a 0for b in range(RADIX):for i in buckets[b]:input_list[a] ia 1# move to nextplacement * RADIXreturn input_listif __name__ __main__:test [4,3,2,1]print(radix_sort(test))
Js
function radixSort(array) {let length array.length;// 如果不是数组或者数组长度小于等于1直接返回不需要排序if (!Array.isArray(array) || length 1) return;let bucket [],max array[0],loop;// 确定排序数组中的最大值for (let i 1; i length; i) {if (array[i] max) {max array[i];}}// 确定最大值的位数loop (max ).length;// 初始化桶for (let i 0; i 10; i) {bucket[i] [];}for (let i 0; i loop; i) {for (let j 0; j length; j) {let str array[j] ;if (str.length i 1) {let k parseInt(str[str.length - 1 - i]); // 获取当前位的值作为插入的索引bucket[k].push(array[j]);} else {// 处理位数不够的情况高位默认为 0bucket[0].push(array[j]);}}array.splice(0, length); // 清空旧的数组// 使用桶重新初始化数组for (let i 0; i 10; i) {let t bucket[i].length;for (let j 0; j t; j) {array.push(bucket[i][j]);}bucket[i] [];}}return array;
} 桶排序Bucket Sort 计数排序的升级版。在额外空间充足的情况下尽量增大桶的数量。使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。 设置一个bucketSize该数值的选择对性能至关重要性能最好时每个桶都均匀放置所有数值反之最差表示每个桶最多能放置多少个数值 遍历输入数据并且把数据依次放到到对应的桶里去 对每个非空的桶进行排序可以使用其它排序方法这里递归使用桶排序 从非空桶里把排好序的数据拼接起来即可。 Java
private static ListInteger bucketSort(ListInteger arr, int bucketSize) {int len arr.size();if (len 2 || bucketSize 0) {return arr;}int minVal arr.get(0), maxVal arr.get(0);for (int i 1; i len; i) {if (arr.get(i) minVal) {minVal arr.get(i);} else if (arr.get(i) maxVal) {maxVal arr.get(i);}}int bucketNum (maxVal - minVal) / bucketSize 1;ListListInteger bucket new ArrayList();for (int i 0; i bucketNum; i) {bucket.add(new ArrayList());}for (int val : arr) {int idx (val - minVal) / bucketSize;bucket.get(idx).add(val);}for (int i 0; i bucketNum; i) {if (bucket.get(i).size() 1) {bucket.set(i, bucketSort(bucket.get(i), bucketSize / 2));}}ListInteger result new ArrayList();for (ListInteger val : bucket) {result.addAll(val);}return result;}
Python
def bucket_sort(input_list):l input_listif not l:return []l_max, l_min max(l), min(l)bucket_len int(l_max - l_min) 1buckets: list[list] [[] for _ in range(bucket_len)]for i in l:buckets[int(i - l_min)].append(i)return [i for bucket in buckets for i in sorted(bucket)]if __name__ __main__:test [4,3,2,1]print(bucket_sort(test))
Js
function bucketSort(arr, bucketSize) {if (arr.length 0) {return arr;}var i;var minValue arr[0];var maxValue arr[0];//求出最大值和最小值这里有两种方式两种方式只用其一这里采用方式二。方式一//for (i 1; i arr.length; i) {// if (arr[i] minValue) {// minValue arr[i]; // 输入数据的最小值// } else if (arr[i] maxValue) {// maxValue arr[i]; // 输入数据的最大值// }// }//方式二maxValue Math.max(...arr);minValue Math.min(...arr);//桶的初始化var DEFAULT_BUCKET_SIZE 5; // 设置桶的默认数量为5bucketSize bucketSize || DEFAULT_BUCKET_SIZE;var bucketCount Math.floor((maxValue - minValue) / bucketSize) 1; var buckets new Array(bucketCount);for (i 0; i buckets.length; i) {buckets[i] [];}//利用映射函数将数据分配到各个桶中for (i 0; i arr.length; i) {buckets[Math.floor((arr[i] - minValue) / bucketSize)].push(arr[i]);}arr.length 0;for (i 0; i buckets.length; i) {insertionSort(buckets[i]); // 对每个桶进行排序这里使用了插入排序这里也可以直接用js的数组sort方法很直接for (var j 0; j buckets[i].length; j) {arr.push(buckets[i][j]); }}return arr;
}计数排序 计数排序是一种非基于比较的排序算法其空间复杂度和时间复杂度均为O(nk)其中k是整数的范围。基于比较的排序算法时间复杂度最小是O(nlogn)的。 找出数组中的最大值maxVal和最小值minVal创建一个计数数组countArr其长度是maxVal-minVal1元素默认值都为0遍历原数组arr中的元素arr[i]以arr[i]-minVal作为countArr数组的索引以arr[i]的值在arr中元素出现次数作为countArr[a[i]-min]的值遍历countArr数组只要该数组的某一下标的值不为0则循环将下标值minVal输出返回到原数组即可。 Java
public static void countingSort(int[] arr) {int len arr.length;if (len 2) return;int minVal arr[0], maxVal arr[0];for (int i 1; i len; i) {if (arr[i] minVal) {minVal arr[i];} else if (arr[i] maxVal) {maxVal arr[i];}}int[] countArr new int[maxVal - minVal 1];for (int val : arr) {countArr[val - minVal];}for (int arrIdx 0, countIdx 0; countIdx countArr.length; countIdx) {while (countArr[countIdx]-- 0) {arr[arrIdx] minVal countIdx;}}}
Python
def count_sort2(arr):maxi max(arr)mini min(arr)count_arr_length maxi - mini 1 # 计算待排序列表的数值区域长度如4-9共91-46个数count_arr [0 for _ in range(count_arr_length)] # 创建一个全为0的列表for value in arr:count_arr[value - mini] 1 # 统计列表中每个值出现的次数# 使count_arr[i]存放i的元素个数就是待排序列表中比某个值小的元素有多少个for i in range(1, count_arr_length):count_arr[i] count_arr[i] count_arr[i - 1]new_arr [0 for _ in range(len(arr))] # 存放排序结果for i in range(len(arr)-1, -1, -1): # 从后往前循环是为了使排序稳定new_arr[count_arr[arr[i] - mini] - 1] arr[i] # -1是因为下标是从0开始的count_arr[arr[i] - mini] - 1 # 每归位一个元素就少一个元素return new_arrif __name__ __main__:user_input input(输入待排序的数用\,\分隔:\n).strip()#strip() 方法用于移除字符串头尾指定的字符默认为空格unsorted [int(item) for item in user_input.split(,)]print(count_sort2(unsorted))
Js
function countingSort(arr, maxValue) {var bucket new Array(maxValue1),sortedIndex 0;arrLen arr.length,bucketLen maxValue 1;for (var i 0; i arrLen; i) {if (!bucket[arr[i]]) {bucket[arr[i]] 0;}bucket[arr[i]];}for (var j 0; j bucketLen; j) {while(bucket[j] 0) {arr[sortedIndex] j;bucket[j]--;}}return arr;
}
var arr [2, 3, 8, 7, 1, 2, 7, 3];
console.log(countingSort(arr,8));//1,2,2,3,3,7,7,8 以上分享 10大常见排序算法如有问题请指教写。 如你对技术也感兴趣欢迎交流。 如有需要请点赞收藏分享
