电商网站平台建设资金预算,医院做网站的好处,seo优化必备技巧,上海网站建设制作公冒泡排序/*** 冒泡排序 比较好理解* 两两相比 较大的放后面* 时间复杂度O(n^2)*//*** 改进前的冒泡排序算法进行100,000数据排序运行时间为#xff1a;3829ms* 优化后的冒泡排序算法进行100,000数据排序运行时间为#xff1a;3551ms*/
public static void bubbleSort(int[] a…冒泡排序/*** 冒泡排序 比较好理解* 两两相比 较大的放后面* 时间复杂度O(n^2)*//*** 改进前的冒泡排序算法进行100,000数据排序运行时间为3829ms* 优化后的冒泡排序算法进行100,000数据排序运行时间为3551ms*/
public static void bubbleSort(int[] array){ //原始的冒泡排序比较的次数是固定的int lenarray.length;int temp0;for(int i0;ilen-1;i){for(int j0;jlen-1-i;j){if(array[j]array[j1]){temparray[j];array[j]array[j1];array[j1]temp;}}}
}public static void bubbleSort2(int[] array){ //改进的冒泡排序有序时无需比较int lenarray.length;int temp0;boolean flagtrue;for(int i0;ilen-1;i){for(int j0;jlen-1-i;j){if(array[j]array[j1]){flagfalse;temparray[j];array[j]array[j1];array[j1]temp;}}if(flag){ //如果有序 则跳出循环break;}else {flagtrue;}}
}插入排序/*** 插入排序,将无序元素依次插入到有序数组中* 和选择排序很类似。但是其时间取决于数组的初始顺序* 时间复杂度为O(n^2)*//*** 由于数据量大时可能存在一堆数据后移的情况所以时间并不一定比选择排序快* 插入排序算法进行50,000数据排序运行时间为1280ms*/
public static void insertSort(int[] array){int temp0;int lenarray.length;for(int i1;ilen;i){for(int ji;j0;j--){if(array[j]array[j-1]){temparray[j];array[j]array[j-1];array[j-1]temp;}}}
}选择排序/*** 选择排序* 与冒泡排序不同无需频繁进行交换的操作时间较冒泡排序短* 时间复杂度为O(n^2)*//*** 选择排序算法进行50,000数据排序运行时间为626ms*/public static void selectSort(int[] array){int lenarray.length;int temp0;for (int i0;ilen;i){int mini; //min为最小值对应的索引for(int ji;jlen;j){ //内层循环的目的是为了找到最小值if(array[j]array[min]){minj;}}temparray[min];array[min]array[i];array[i]temp;}
}希尔排序/*** 希尔排序* 插入排序的变种慢慢地调整数组的顺序使插入排序效率变高* 最坏情况下时间复杂度为O(n^(1-2))*//*** 希尔排序的效率肯定是要比插入排序要高的* 希尔排序算法进行50,000数据排序运行时间为705ms*/
public static void shellSort(int[] array){int lenarray.length;int h1;while(hlen/3)h3*h1; //希尔排序的增量相邻增量应该尽可能互斥 h1,4,13,40,121...int temp0;while (h1){for (int ih;ilen;i){for(int ji;jh;j-h){if(array[j]array[j-h]){temparray[j];array[j]array[j-h];array[j-h]temp;}}}h/3;}
}快速排序/*** 快速排序* 使用递归的方法有一些难以理解多看几遍就好* 主要思想就是设定pivot将所有比pivot大的放右边比pivot小的放左边* 平均的时间复杂度为O(nlogn) ,有序情况下的复杂度为O(n^2)*//*** 快排是真的快 ,比冒泡插入选择希尔要快上好多* 快速排序算法进行50,000数据排序运行时间为4.00ms*/
public static void quickSort(int[] array, int left, int right){if(leftright){ //递归结束的条件!!! 没有这个 递归就出不来了return;}int Lleft,Rright;int pivotarray[left]; //pivot随意设置这里我们设置pivot为最左边的元素while (leftright){while (array[right]pivot rightleft){ //一定要大于等于或者小于等于 不然数字相同可能出现死循环right--; //右指针不断后移}if(rightleft){array[left]array[right]; //左右指针不重合时将right的值赋给left}while (array[left]pivot rightleft){left; //左指针开始移动}if(leftright){array[right]array[left];}}array[left]pivot; //完成第一次排序quickSort(array,L,left-1);quickSort(array,left1,R);
}归并排序/*** 归并排序* 同样使用递归采用分而治之的想法通过递归的方式将若干个有序序列合并为一个* 时间复杂度为 O(nlogn)同样非常快*//*** 归并排序算法进行50,000数据排序运行时间为4.90ms*/public static void merge(int[] array,int left,int mid,int right){ //进行归并操作的函数int[] tempnew int[right-left1]; //建立缓存数组int ileft,jmid1;int index0; //temp的索引while (imid jright){if(array[i]array[j]){
// temp[index]array[i];
// i;
// index;temp[index]array[i]; //这段代码可以简化成这个形式}else {temp[index]array[j];}}while (imid){temp[index]array[i];}while (jright){temp[index]array[j];}for (int kleft;kright;k){ //将temp传回arrayarray[k]temp[k-left];}
}public static void mergeSort(int[] array,int left,int right){ //归并排序if(leftright){return;}int mid(leftright)/2;mergeSort(array,left,mid);mergeSort(array,mid1,right); //先分解成最小的merge(array,left,mid,right); //再合并
}基数排序/*** 基数排序* 空间换时间所以时间复杂度最低为 O(d(nr)) r是基数(基本都是10),d为长度。。。 可趋近于O(n)* PS:我反而觉得基数排序比较复杂提前需要设置很多变量和数组*//*** 基数排序算法进行50,000数据排序运行时间为2.35ms*/
public static void radixSort(int[] array){int maxarray[0];for (int i1;iarray.length;i){if(array[i]max){maxarray[i]; //首先找到数组中的最大数}}int times(max).length(); //得到桶排序的轮数也就是最大数有几位int[][] tempnew int[10][array.length]; //定义10个桶每个桶的容量为元素总个数int t1; //t表示第几轮int n1; //每过一轮n*10为了得到相应位的数字int num;int[] orderTempnew int[10]; //数组orderTemp[i]用来表示该位是i的数的个数while (ttimes){for(int i0;iarray.length;i){num(array[i]/n)%10;temp[num][orderTemp[num]]array[i];orderTemp[num];}int index0;for (int i0;i10;i){if(orderTemp[i]0){ //如果桶中元素大于0for (int j0;jorderTemp[i];j){array[index]temp[i][j];}}orderTemp[i]0; //一定要把桶子清空哦}n*10;t;}
}堆排序/*** 堆排序* 1)将待排序的序列构造成一个大顶堆* 2)将根节点与末尾元素交换末尾元素就为最大值* 3)剩余数据重新构造成一个大顶堆* 4)不断执行操作完成排序* 时间复杂度为O(nlogn)*//*** 堆排序算法进行50,000数据排序运行时间为4.07ms*/public static void adjustHeap(int[] arr,int i, int length){ //调整一个以i为顶点的子树int temparr[i];for (int ki*21;klength;kk*21){if(k1length arr[k]arr[k1]){k; //如果左叶子小于右叶子k就变成右叶子}if (temparr[k]){ //对子树进行调整. 注意这里要用temp来比较不能用a[i]我们目的是把temp进行移动arr[i]arr[k];ik;} else {break; //说明该子树已然是一个最大堆直接跳出循环即可}}arr[i]temp;
}public static void heapSort(int[] arr){for(int iarr.length/2-1;i0;i--){ //i从最后一个非叶子节点开始。位置为iarr.length/2-1adjustHeap(arr,i,arr.length); //该步骤为建立一个最大堆}for (int iarr.length-1;i0;i--){int temparr[i];arr[i]arr[0];arr[0]temp;adjustHeap(arr,0,i);}
}完结撒花~
