视频网站的链接怎么做,怎样制定一个网站建设方案,云虚拟主机怎么建网站,wordpress 京东导购1. 冒泡排序 冒泡排序属于交换排序。效率较低#xff0c;适用小规模数据集。 原理#xff1a;循环遍历要排序的元素#xff0c;依次比较两个相邻的元素#xff0c;每次循环都找到一个最大(或最小)的数放到最后(或最前)。没有相邻元素需要交换时#xff0c;说明已经排序完成…1. 冒泡排序 冒泡排序属于交换排序。效率较低适用小规模数据集。 原理循环遍历要排序的元素依次比较两个相邻的元素每次循环都找到一个最大(或最小)的数放到最后(或最前)。没有相邻元素需要交换时说明已经排序完成。 它是稳定排序 (即相等的两个元素在排序后相对位置不会发生变化)。
public static void bubbleSort(int[] arrData) {int temp;int count 0;//控制循环次数for (int i 0; i arrData.length - 1; i) {for (int j 0; j arrData.length - 1 - i; j) {count;if (arrData[j] arrData[j 1]) {temp arrData[j];arrData[j] arrData[j 1];arrData[j 1] temp;}}}System.out.println(比较次数 count);}
改进算法1记录本此循环有无数据交换若无则表示数据已经有序跳出循环。
public static void bubbleSort1(int[] arrData) {int temp;int count 0;boolean noChange;//控制循环次数for (int i 0; i arrData.length - 1; i) {noChange true;for (int j 0; j arrData.length - 1 - i; j) {count;if (arrData[j] arrData[j 1]) {temp arrData[j];arrData[j] arrData[j 1];arrData[j 1] temp;noChange false;}}if (noChange) {break;}}System.out.println(比较次数 count);}
改进算法2改进算法1加上记录本次循环比较交换的最后位置后面的元素是有序的下次循环无需再比较最后位置元素之后的数据。
public static void bubbleSort2(int[] arrData) {int temp;int count 0;boolean noChange;int lastPos arrData.length - 1;int comparePos 0;//控制循环次数for (int i 0; i arrData.length - 1; i) {noChange true;for (int j 0; j lastPos; j) {count;if (arrData[j] arrData[j 1]) {temp arrData[j];arrData[j] arrData[j 1];arrData[j 1] temp;noChange false;comparePos j;}}lastPos comparePos;if (noChange) {break;}}System.out.println(比较次数 count);}
对数据{19,25,1,30,12,8,26,24,40,72}bubbleSort的比较次数为45次bubbleSort1的比较次数为35次bubbleSort2的比较次数为25次。
2. 快速排序 快速排序属于交换排序。基于分而治之策略效率稍高。 原理每一趟排序将数据分割成左右两部分其中左边的数据都比右边的数据小然后再按此方法对这两部分数据分别进行快速排序整个排序过程递归进行最终整个数据变成有序。 它是不稳定排序 (即相等的两个元素在排序后相对位置可能发生变化)。
public static void quickSort(int[] arrData, int left, int right) {if (left right) {return;}//基准数int base arrData[left];int i left;int j right;while (true) {//要先从右向左找while (i j base arrData[j]) {--j;}while (i j base arrData[i]) {i;}if (i j) break;int temp arrData[i];arrData[i] arrData[j];arrData[j] temp;}//将基准数和小的数交换arrData[left] arrData[i];arrData[i] base;//左边排序quickSort(arrData, left, i - 1);//右边排序quickSort(arrData, j 1, right);}
3. 直接插入排序 直接插入排序属于插入排序。适合数据个数小于20个的数据集。 原理将一个记录插入到已经排好序的有序表中从而得到一个新的、记录数增1的有序表。一开始有序表就只有第一个数。 public static void insertSort(int[] arrData) {//一开始有序表只有第一个数for (int i 1; i arrData.length; i) {//当前数比前一个小if (arrData[i] arrData[i - 1]) {int temp arrData[i];//保存当前数int j;//查找有序表里的插入位置for (j i - 1; j 0 temp arrData[j]; --j) {arrData[j 1] arrData[j];//将前面的大数后移一格}arrData[j 1] temp;//System.out.println(Arrays.toString(arrData));}}}
4. 希尔排序 希尔排序属于插入排序又称“缩小增量排序”是直接插入排序更高效的改进版本。 原理把记录按下标的一定增量分组对每组使用直接插入排序算法排序随着增量逐渐减少每组包含的关键词越来越多当增量减至 1 时整个文件恰被分成一组算法便终止。
public static void shellSort(int[] arrData) {//遍历所有的步长for(int d arrData.length/2; d 0; d / 2 ){//遍历所有元素for(int i d; i arrData.length; i){//遍历本组中所有元素for(int j i-d; j 0; j - d){//如果当前元素大于加上步长后的那个元素if(arrData[j] arrData[jd]){int temp arrData[j];arrData[j] arrData[jd];arrData[jd] temp;}}}}}
5. 选择排序 原理第一次从待排序的数据元素中选出最小或最大的一个元素存放在序列的起始位置然后再从剩余的未排序元素中寻找到最小大元素然后放到已排序的序列的末尾。以此类推直到全部待排序的数据元素的个数为零。
public static void selectSort(int[] arrData){for(int i0;iarrData.length;i){int minIndex i;//把当前遍历的数和后面所有数依次进行比较并记录最小数下标for(int ji1;jarrData.length;j){if(arrData[minIndex]arrData[j]){minIndex j;}}//如果最小的数和当前遍历的数下标不一致,说明下标为minIndex的数比当前遍历的数更小if(i ! minIndex){int temp arrData[i];arrData[i] arrData[minIndex];arrData[minIndex] temp;}}}
6. 归并排序 归并排序是建立在归并操作上的一种有效稳定的排序算法。 原理将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为二路归并。也是基于分而治之策略。
public static int[] mergeSort(int[] arrData, int low, int high) {if (low high) {return new int[]{arrData[low]};}int mid low (high - low) / 2;int[] leftArrData mergeSort(arrData, low, mid); //左有序数组int[] rightArrData mergeSort(arrData, mid 1, high); //右有序数组int[] newOut new int[leftArrData.length rightArrData.length]; //新有序数组int m 0, i 0, j 0;while (i leftArrData.length j rightArrData.length) {newOut[m] leftArrData[i] rightArrData[j] ? leftArrData[i] : rightArrData[j];}while (i leftArrData.length)newOut[m] leftArrData[i];while (j rightArrData.length)newOut[m] rightArrData[j];return newOut;}
7. 桶排序 桶排序(箱排序)是一种分布式排序。 原理将数据转换为另一种形式排序。通常用数组来表示每个桶用原数据的值表示桶的索引。是一种空间换时间的算法。
public static void bucketSort(int[] arrdata) {//注意数据需都0int max getMaxOne(arrdata);int[] bucket new int[max 1];for (int i 0; i arrdata.length; i) {bucket[arrdata[i]];//计数}int pos 0;for (int i 0; i bucket.length; i) {for (int j 0; j bucket[i]; j) {//同一个位置可能有几个相同数据值arrdata[pos] i;//i是原数据值}}}static int getMaxOne(int[] arrData) {int max arrData[0];for (int i 1; i arrData.length; i) {if (arrData[i] max) {max arrData[i];}}return max;}
8. 基数排序 基数排序radix sort属于“分布式排序”distribution sort。也是用空间换时间的算法。 原理透过键值的部份信息将要排序的元素分配至某些“桶”中以达到排序的作用。如对整数数列排序中先以个位为key分组然后合并再以十位为key分组合并以此类推直到最大数的最高位。
public static void radixSort(int[] arrData) {//d表示最大数字的位数有多少位int d getLen(getMaxOne(arrData));int k 0;int n 1; //作除数int m 1; //控制键值排序依据在哪一位从第一位即个位开始int[][] temp new int[10][arrData.length]; //数组的第一维表示可能的余数0-9int[] order new int[10]; //数组order[i]用来表示该位是i的数的个数while (m d) {//根据余数来分组for (int i 0; i arrData.length; i) {int lsd ((arrData[i] / n) % 10);temp[lsd][order[lsd]] arrData[i];order[lsd];}//合并分组for (int i 0; i 10; i) {if (order[i] ! 0) {for (int j 0; j order[i]; j) {arrData[k] temp[i][j];k;}}order[i] 0;}n * 10;//作除数k 0;m;//位数1}}static int getMaxOne(int[] arrData) {int max arrData[0];for (int i 1; i arrData.length; i) {if (arrData[i] max) {max arrData[i];}}return max;}static int getLen(int v) {return (v ).length();}
9. 堆排序 原理堆排序首先要构造堆结构。堆结构是一个完全二叉树。完全二叉树指的是若设二叉树的深度为n除第 n 层外其它各层 (1~n-1) 的结点数都达到最大个数第 n 层所有的结点都连续集中在最左边。完整的堆排序经过反复的两个步骤构造堆结构和堆排序输出(根节点)。 public static void heapSort(int[] arrData) {int size arrData.length;int i;//将n个元素建堆for (i size / 2 - 1; i 0; i--) {//只需循环非叶节点heapCompare(arrData, i, size);}int k, t;for (i size - 1; i 0; i--) {//根节点为最大值放到数组后面t arrData[0];arrData[0] arrData[i];arrData[i] t;k 0;heapCompare(arrData, k, i);}}static void heapCompare(int[] arrData, int i, int total) {//i为非叶节点int j;while (2 * i 1 total) {//第i个节点有子树j 2 * i 1; //左子节点if ((j 1) total) {//存在右子节点if (arrData[j] arrData[j 1])//若左边小于右边j;//指向右子节点}if (arrData[i] arrData[j]) {//j为 i节点的子节点int t arrData[i]; //交换数据arrData[i] arrData[j];arrData[j] t;i j;//堆被破坏需重新调整子树} else {//堆未破坏无需调整break;}}}
10. 数据比较
稳定原地最好最坏平均空间说明冒泡排序是是O(n)O(n²)O(n²)O(1)插入排序是是O(n)O(n²)O(n²)O(1)归并排序是否O(nLogn)O(nLogn)O(nLogn)O(n)需额外空间桶排序是否O(nk)O(n²)O(n²)O(n*k)k为桶总数基数排序是否O(d(nr))O(d(nr))O(d(nr))O(nr)d是关键码个数r为关键码的最大值快速排序否是O(nLogn)O(n²)O(nLogn)O(Logn)希尔排序否是O(n)O(n²)O(nLogn)O(1)选择排序否是O(n²)O(n²)O(n²)O(1)最低效堆排序否是O(nLogn)O(nLogn)O(nLogn)O(1)
