网站建设自助建站云建站,银川做网站多少钱,百度一下打开网页,糯米团网站怎么做一、冒泡排序算法#xff1a;
介绍#xff1a; 冒泡排序#xff08;Bubble Sort#xff09;是一种简单直观的排序算法。它重复地走访过要排序的数列#xff0c;一次比较两个元素#xff0c;如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需…一、冒泡排序算法
介绍 冒泡排序Bubble Sort是一种简单直观的排序算法。它重复地走访过要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢浮到数列的顶端。 作为最简单的排序算法之一冒泡排序给我们的感觉就像 Abandon 在单词书里出现的感觉一样每次都在第一页第一位所以最熟悉。冒泡排序还有一种优化算法就是立一个 flag当在一趟序列遍历中元素没有发生交换则证明该序列已经有序。但这种改进对于提升性能来说并没有什么太大作用。
原理 排序的趟数len-1每趟将数组的中的进行两两比较若前者值比后者值大(小)发生索引元素交换每遍历一次最后一位产生一个最大小值
代码
/*** 冒泡排序算法优化* param arr 数组* param type 升序asc 降序desc*/
public void sort(int[] arr,String type){
// 原理排序的趟数len-1每趟将数组的中的进行两两比较若前者值比后者值大(小)发生索引元素交换每遍历一次最后一位产生一个最大小值 System.out.println(原数组Arrays.toString(arr));boolean flag false; // 用来判断是否有交换无交换说明已经排好序不需要再排默认无交换for (int i 0; i arr.length - 1; i) { // 执行多少轮 数组长度-1flag false; // 每次循环之后重置默认无交换for (int j 0; j arr.length - i - 1; j) { // 每论执行多少次比较 数组长度-i-1if(type.equals(desc)){ // 降序排序if(arr[j] arr[j1]){ // 两数比较前数小交换int tmp arr[j];arr[j] arr[j1];arr[j1] tmp;flag true;}}else{ // 升序排序if(arr[j] arr[j1]){ // 两数比较前数大交换int tmp arr[j];arr[j] arr[j1];arr[j1] tmp;flag true;}}}System.out.println(第(i1)排序Arrays.toString(arr));if(!flag){ // 如果当前轮没有发生两数之间的交换说明顺序已经排好结束循环break;}}
}
二、选择排序SelectionSort
介绍 选择排序是一种简单直观的排序算法无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。
原理
int[] ints {6, 1, 4, 5, 2, 3};/** 第一轮: 下标为0的元素作为最小的, 下标0和下标1(下标为最小), 下标1和下标2, 下标1和下标3, 下标1和下标4, 下标1和下标5 5次* 1 6 4 5 2 3* 第二轮: 下标为1的元素作为最小的, 下标1和下标2(下标2位最小), 下标2和下标3, 下标2和下标4(下标4位最小), 下标4和下标5 4次* 1 2 4 5 6 3* 第三轮: 下标为2的元素作为最小的, 下标2和下标3, 下标2和下标4, 下标2和下标5(下标5最小) 3次* 1 2 3 5 6 4* 第四轮: 下标为3的元素作为最小的, 下标3和下标4, 下标3和下标5(下标5最下) 2次* 1 2 3 4 6 5* 第五轮: 下标为4的元素作为最小的, 下标4和下标5(下标5最小) 1次* 1 2 3 4 5 6* */
代码
/*** 选择排序-升序* param arr 要排序的数组*/
public static void selectionSortAscendingOrder(int[] arr){// 原理比较len-1趟假设第n(从0开始)个位置的值为最小值依次与后面的值比较若前者数大于后者数记录后者元素对应的索引一趟之后将两个索引位置元素进行交换// 需要循环的趟数,比较数组长度-1趟例如数组长度6需要遍历5趟依次找到五个最小值for (int i 1; i arr.length; i) {int minIndex i-1;// 记录最小元素索引位置// 每趟需要比较的次数for (int j i; j arr.length; j) {//第一个索引位置的值依次与后面元素比较若前者的值大于后者值那么最小值的索引为后者元素的索引if(arr[minIndex] arr[j]){minIndex j;}}// 判断最小元素是否是自己若不是自己再发生交换if(minIndex ! i-1){ // 算数运算符的优先级高于比较运算符// 获取第一个位置的元素int temp arr[i-1];// 获取最小索引位置的元素arr[i-1] arr[minIndex];// 将两处索引位置的值交换arr[minIndex] temp;}}
三、快速排序
介绍 快速排序使用分治法Divide and conquer策略来把一个串行list分为两个子串行sub-lists。 快速排序又是一种分而治之思想在排序算法上的典型应用。本质上来看快速排序应该算是在冒泡排序基础上的递归分治法。 快速排序的名字起的是简单粗暴因为一听到这个名字你就知道它存在的意义就是快而且效率高它是处理大数据最快的排序算法之一了。
原理步骤 1. 从数列中挑出一个元素称为 基准pivot; 2. 重新排序数列所有元素比基准值小的摆放在基准前面所有元素比基准值大的摆在基准的后面相同的数可以到任一边。在这个分区退出之后该基准就处于数列的中间位置。这个称为分区partition操作 3. 递归地recursive把小于基准值元素的子数列和大于基准值元素的子数列排序 代码
/*** 快速排序 原理以左边索引位0的数为基准* 先从右边开始找直到找到比基准数小的为止(左边索引小于右边索引)* 再从左边开始找直到找到比索引值大的为止(左边索引小于右边索引)* 交换两处索引位置的值* 如果左边索引与右边索引相同那么基准值与索引相同处元素替换使用递归依次处理* 左分区递归递归* 右分区递归递归* 判断递归出口* param arr* param left* param right*/
public static void quickSort(int[] arr, int left, int right) {// 使用递归时的出口if(left right){return;}int i left 1;// left1 表示从基准值下一位开始int j right;// 基准元素(pivot Element)int baseElement arr[left];// 循环交换数组中 比基准值大的 与 比基准值小的 交换while (i ! j) {// 先从右边开始找, 如果找到比基准值小的 结束查找,并且左边索引要小于右边索引while (arr[j] baseElement i j) {j--;}// 再从左边开始找如果找到比基准值大的 结束查找并且左边索引要小于右边索引while (arr[i] baseElement i j){i;}// 如果找到了左边找到了比基准值小的右边找到了比基准值大的两元素发生交换if(j ! i){ // 如果两个索引相同就不需要交换了结束循环int temp arr[i];arr[i] arr[j];arr[j] temp;}}// 左边索引与右边索引指向同一位置说明找到了该基准值的位置将基准值与索引位置值发生交换arr[left] arr[i];arr[i] baseElement;// 左分区递归调用排序quickSort(arr,left,i-1);// 右分区递归调用排序quickSort(arr,i1,right);
}
