购物网站促销方案,免费建站的,在哪里做网站效果好,国外效果图网站查找
顺序查找
顺序查找#xff08;Linear Search#xff09;是一种在有序数组中查找目标元素的基本算法。它的时间复杂度为 O(n)#xff0c;适用于查找少量数据。顺序查找的基本思想是从数组的第一个元素开始#xff0c;逐个与待查找的元素进行比较#xff0c;直到找到…查找
顺序查找
顺序查找Linear Search是一种在有序数组中查找目标元素的基本算法。它的时间复杂度为 O(n)适用于查找少量数据。顺序查找的基本思想是从数组的第一个元素开始逐个与待查找的元素进行比较直到找到目标元素或遍历完整个数组。
package com.zhx;public class Test {//顺序查找public static int seqSearch(int[] array, int target) {for (int i 0; i array.length; i) {int p array[i];if (p target) {System.out.println(sucess to find out target from array, indexi);return i;}}System.out.println(fail to find out the target);return -1;}public static void main(String[] args) {int[] data { 3, 6, 7, 2, 12, 9, 0, 11 };System.out.println(seqSearch(data, 12));}
}折半查找 折半查找Binary Search是一种在有序数组中查找目标元素的高效算法。它的时间复杂度为 O(logn)常用于查找大量数据。折半查找的基本思想是将待查找的范围逐步缩小每次将范围缩小一半。前提是数组有序。
package com.zhx;public class Test1 {//折半查找public static int seqSearch(int[] array, int target) {int lo 0;int hi array.length - 1;while (lo hi) {int mid lo (hi - lo) / 2;if (target array[mid]) {hi mid - 1;} else if (target array[mid]) {lo mid 1;} else {return mid;}}return -1;}public static void main(String[] args) {int[] data { 10, 11, 12, 16, 18, 23, 29, 33, 48, 54, 57, 68, 77, 84, 98 };System.out.println(seqSearch(data, 23));}
}排序
冒泡排序 冒泡排序Bubble Sort是一种简单的排序算法它重复地遍历待排序的数列一次比较两个元素如果顺序错误就把它们交换过来。遍历数列的工作是重复地进行直到没有再需要交换也就是说该数列已经排序完成。
import java.util.Arrays;public class Test {public static void bubbleSort(int[] arr) {for (int i 1; i arr.length; i) {// i1, j4// i2, j3// i3, j2// jarr.length-1-ifor (int j 0; j arr.length - 1 - i; j) {if (arr[j] arr[j 1]) {int temp arr[j];arr[j] arr[j 1];arr[j 1] temp;}}}}public static void main(String[] args) {int[] arr { 9, 8, 5, 4, 2, 0 };bubbleSort(arr);System.out.println(Arrays.toString(arr));}
}快速排序
快速排序Quick Sort是一种分治策略Divide and Conquer的排序算法。它通过选取一个基准元素pivot将数组分为两个子数组其中一个子数组的元素都小于基准元素另一个子数组的元素都大于基准元素。然后对这两个子数组分别进行递归排序。当整个数组所有元素有序时排序完成。
package com.zhx;import java.util.Arrays;public class QuickSort {public static void quickSort(int[] arr, int low, int high) {if (low high) {// 1. 定义基准pivot,int pivot arr[low];// ...... pivot移动到中间左边都比pivot小后边都比pivot大, indexint i low;int j high;while (i j) {while (i j arr[j] pivot) {j--;}// 交换swap(arr, i, j);while (i j arr[i] pivot) {i;}// 交换swap(arr, i, j);}// 2. 递归对左右2部分快排quickSort(arr, low, j - 1);quickSort(arr, j 1, high);}}public static void swap(int arr[], int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}public static void main(String[] args) {int[] arr { 5, 3, 7, 6, 4, 1, 0, 2, 9, 10, 8 };quickSort(arr, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}
}插入排序 插入排序Insertion Sort是一种简单直观的排序算法。它的工作原理是将待排序的元素一个一个地插入到已经排序好的序列中的适当位置。插入排序在实现上通常采用 in-place 排序即只需用到 O(1) 的额外空间的排序因而在从后向前排序的过程中需要反复把已排序元素逐步向后挪位为最新元素提供插入空间。
package com.zhx;import java.util.Arrays;public class SortTest {public static void InsertSort(int[] arr) {for (int i 1; i arr.length; i) {for (int j i; j 0; j--) {if (arr[j] arr[j - 1]) {int temp arr[j];arr[j] arr[j - 1];arr[j - 1] temp;} else {break;}}}}public static void main(String[] args) {int[] arr { 7, 6, 9, 3, 1, 5, 2, 4 };InsertSort(arr);System.out.println(Arrays.toString(arr));}
}希尔排序
希尔排序Shell Sort是一种插入排序的算法它的主要思想是使数组中任意间隔为 h 的元素都是有序的。这样的数组被称为 h 有序数组。希尔排序会不断减小 h 的值直到最后 h1 时所有元素就都是有序的了。
package com.zhx;import java.util.Arrays;
public class SortTest {public static void shellSort(int[] arr) {// 增量gap, 并逐步的缩小增量for (int gap arr.length / 2; gap 0; gap / 2) {// 从第gap个元素逐个对其所在的组进行直接插入排序for (int i gap; i arr.length; i) {for (int j i; j gap; j - gap) {if (arr[j] arr[j - gap]) {int temp arr[j];arr[j] arr[j - gap];arr[j - gap] temp;} else {break;}}}}}public static void main(String[] args) {int[] arr { 8, 9, 1, 7, 2, 3, 5, 4, 6, 0 };shellSort(arr);System.out.println(Arrays.toString(arr));}
}选择排序 选择排序Selection Sort是一种简单直观的排序算法。它的工作原理是每次从待排序的数据元素中选出最小或最大的一个元素将其与待排序的数据序列的最前面或最后面的元素进行交换然后缩小待排序数据序列的范围直到全部待排序的数据元素都排好序为止。
package com.zhx;import java.util.Arrays;
public class SortTest {//选择排序public static void selectionSort(int[] arr) {int len arr.length;int minIndex, temp;for (int i 0; i len - 1; i) { //最后一个数不用排序minIndex i;for (int j i 1; j len; j) {if (arr[j] arr[minIndex]) { // 寻找最小的数minIndex j; // 将最小数的索引保存}}temp arr[i];arr[i] arr[minIndex];arr[minIndex] temp;}}public static void main(String[] args) {int[] arr { 29, 38, 65, 87, 78, 23, 27, 29 };selectionSort(arr);System.out.println(Arrays.toString(arr));}
}堆排序
堆排序Heap Sort是一种基于二叉堆Binary Heap的选择排序算法。它的基本思想是将待排序的序列构造成一个大顶堆或小顶堆此时整个序列的最大值或最小值就是堆顶的根节点。然后将其与末尾元素进行交换得到当前最大或最小值。接着调整剩余元素使其满足堆的性质然后继续重复这个过程直到所有元素排好序。
大顶堆Big Heap和小顶堆Little Heap是两种不同的堆结构它们在计算机科学中有着广泛的应用。 大顶堆在大顶堆中每个节点都大于或等于其子节点。换句话说大顶堆满足以下条件 对于任意的节点 i有 arr[i] arr[2 * i] 和 arr[i] arr[2 * i 1]。 小顶堆在小顶堆中每个节点都小于或等于其子节点。换句话说小顶堆满足以下条件 对于任意的节点 i有 arr[i] arr[2 * i] 和 arr[i] arr[2 * i 1]。 大顶堆和小顶堆的主要区别在于节点之间的顺序关系。大顶堆的特点是父节点大于子节点而小顶堆的特点是父节点小于子节点。 在 Java 编程中我们可以使用数组来表示堆结构。对于大顶堆我们可以使用以下方法维护堆性质
构造大顶堆从数组的最后一个元素开始逐个将元素向上调整使其满足大顶堆的性质。调整大顶堆对于任意的节点 i将节点 i 与其子节点进行比较如果节点 i 的值小于其子节点的值则交换它们的位置。然后继续调整子节点使其满足大顶堆的性质。 类似地对于小顶堆我们可以使用以下方法维护堆性质构造小顶堆从数组的最后一个元素开始逐个将元素向上调整使其满足小顶堆的性质。调整小顶堆对于任意的节点 i将节点 i 与其子节点进行比较如果节点 i 的值大于其子节点的值则交换它们的位置。然后继续调整子节点使其满足小顶堆的性质。 大顶堆和小顶堆在排序算法、数据结构以及实际应用中都有广泛的应用。例如在 Java 中的优先队列PriorityQueue就是基于大顶堆实现的。
package com.zhx;import java.util.Arrays;public class HeapSort {public static void main(String[] args) {int[] arr { 27, 46, 12, 33, 49, 27, 36, 40, 42, 50, 51 };heapSort(arr);System.out.println(Arrays.toString(arr));}public static void heapSort(int[] arr) {// 建最大堆arr数组本身就可以看做是一个二叉堆下面需要将arr变成一个最大堆/** 1、第一个非叶子节点的下标为arr.length/2-1* 2、从第一个非叶子节点开始遍历每一个非叶子节点使它们都成为最大堆*/for (int i arr.length / 2 - 1; i 0; i--) {heapify(arr, i, arr.length - 1);}for (int i arr.length - 1; i 0; i--) {//将arr数组的第一个元素因为此元素是最大堆顶点与数组最后一个元素交换因为是升序swap(arr, 0, i);//交换之后arr不是最大堆了i已经排好序了不用考虑heapify(arr, 0, i - 1);}}//将i节点变成一个最大堆public static void heapify(int[] arr, int i, int last_index) {int max i;if (2 * i 1 last_index arr[2 * i 1] arr[max]) {max 2 * i 1;// max记为左节点}if (2 * i 2 last_index arr[2 * i 2] arr[max]) {max 2 * i 2;// max记为右节点}if (max ! i) {// 将i节点与它的最大子节点进行交换swap(arr, max, i);// 递归对调用的子节点进行heapifyheapify(arr, max, last_index);}}public static void swap(int[] arr, int i, int j) {int temp arr[i];arr[i] arr[j];arr[j] temp;}
}归并排序 归并排序Merge Sort是一种分治算法它的基本思想是将一个数组或列表分成两半将两半分别排序然后将排序后的两半合并起来。
package com.zhx;import java.util.Arrays;public class MergeSort {public static void mergeSort(int arr[], int[] temp, int low, int high) {if (low high) {// 分2部分int mid (low high) / 2;// 1. 对左边进行归并排序mergeSort(arr, temp, low, mid);// 2. 对右边进行归并排序mergeSort(arr, temp, mid 1, high);// 3. 合并左右两个有序集合merge(arr, temp, low, mid, high);}}public static void merge(int[] arr, int[] temp, int low, int mid, int high) {int i low; //设置左指针初始位置int j mid 1; //设置右指针初始位置int k 0; //临时数组指针while (i mid j high) {if (arr[i] arr[j]) {temp[k] arr[i];} else {temp[k] arr[j];}}// 左边有剩余将左边剩余的填入tempwhile (i mid) {temp[k] arr[i];}// 右边有剩余将右边剩余的填入tempwhile (j high) {temp[k] arr[j];}// 将临时数组从头开始拷贝到arr中k 0;while (low high) {arr[low] temp[k];}}public static void main(String[] args) {int[] arr { 8, 4, 5, 7, 1, 3, 6, 2 };// 辅助数组int[] temp new int[arr.length];mergeSort(arr, temp, 0, arr.length - 1);System.out.println(Arrays.toString(arr));}
}计数排序 计数排序Counting Sort是一种线性时间复杂度的排序算法适用于处理整数类型的数据。它的工作原理是根据输入数据的值建立一个计数器数组然后根据计数器数组的值将原始数据重新排列。
package com.zhx;import java.util.Arrays;
public class CountSort {public static void countSort(int[] arr) {// 找到最大值int max arr[0];for (int i 0; i arr.length; i) {if (arr[i] max) {max arr[i];}}// 找到最小值int min arr[0];for (int i 0; i arr.length; i) {if (arr[i] min) {min arr[i];}}// 创建计数数组int[] count new int[max - min 1];for (int i 0; i arr.length; i) {count[arr[i] - min];}int k 0;// 往数组中输出for (int i 0; i count.length; i) {while (count[i] 0) {arr[k] i min;count[i]--;}}}public static void main(String[] args) {int[] arr { 108, 109, 106, 101, 107, 102, 103, 102, 104, 106, 101, 110 };countSort(arr);System.out.println(Arrays.toString(arr));}
}桶排序 桶排序Bucket Sort是一种线性时间复杂度的排序算法适用于处理整数类型的数据。它的工作原理是将原始数据分成若干个桶然后对每个桶内的数据进行排序最后将所有桶内的数据依次取出得到排序后的序列。
package com.zhx;
import java.util.Arrays;
import java.util.ArrayList;
import java.util.Collections;public class BucketSort {public static void bucketSort(int[] arr) {// 找到数组的最大值int max arr[0];for (int i 0; i arr.length; i) {if (arr[i] max) {max arr[i];}}// 找到数组的最小值int min arr[0];for (int i 0; i arr.length; i) {if (arr[i] min) {min arr[i];}}// 创建桶的容器ArrayListArrayListInteger list new ArrayList();// 确定桶的数量int count (max - min) / arr.length 1;for (int i 0; i count; i) {list.add(new ArrayListInteger());}// 往桶里放for (int i 0; i arr.length; i) {list.get((arr[i] - min) / arr.length).add(arr[i]);}// 给每个桶排序for (int i 0; i list.size(); i) {Collections.sort(list.get(i));}// 把桶里的内容输出int k 0;for (int i 0; i list.size(); i) {ArrayListInteger bucket list.get(i);for (int j 0; j bucket.size(); j) {arr[k] bucket.get(j);}}}public static void main(String[] args) {int[] arr { 3, 44, 38, 5, 47, 15, 36, 26, 27, 2, 46, 4, 19, 50, 48 };bucketSort(arr);System.out.println(Arrays.toString(arr));}
}基数排序 基数排序Radix Sort是一种非对比排序算法适用于处理整数和小数。它的工作原理是根据数字的位数进行分组然后对每组数据进行递归排序。 方法一
package com.zhx;import java.util.Arrays;public class RadixSort {public static void main(String[] args) {int[] arr {26,3,49,556,81,9,863,0};radixSort(arr);System.out.println(Arrays.toString(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]记录当前位置i的元素累计记数方便对应到数组temp中的位置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赋给arrSystem.arraycopy(temp, 0, arr, 0, arr.length);}}
}方法二
package com.zhx;/** 另一种实现方式:* 数组[26, 3, 49, 556, 81, 9, 863, 0]* 1、创建桶下标0~9并以个位数为下标从第一个元素开始依次放入桶中。* 0[0]* 1[81]* 2[]* 3[3863]* 4[]* 5[]* 6[26556]* 7[]* 8[]* 9[499]* 遍历桶将元素依次取出完成第一次排序[0, 81, 3, 863, 26, 556, 49, 9]* 2、以十位数为下标将完成第一次排序的数组从第一个元素开始依次放入桶中。* 0[039]* 1[]* 2[26]* 3[]* 4[49]* 5[556]* 6[863]* 7[]* 8[81]* 9[]* 遍历桶将元素依次取出完成第二次排序[0, 3, 9, 26, 49, 556, 863, 81]* 3、以百位数为下标将完成第二次排序的数组从第一个元素开始依次放入桶中。* 0[039264981]* 1[]* 2[]* 3[]* 4[]* 5[556]* 6[]* 7[]* 8[863]* 9[]* 遍历桶将元素依次取出完成第三次排序[0, 3, 9, 26, 49, 81, 556, 863]*/
import java.util.ArrayList;
import java.util.Arrays;
public class Test {private static void radixSort(int[] arr) {//查找最大值确定排序的次数int max arr[0];for (int anArr : arr) {if (anArr max) {max anArr;}}//从个位开始对数组进行排序for (int exp1; max/exp0; exp*10) {// 创建桶并初始化桶的下标 0~9ArrayListArrayListInteger buckets new ArrayListArrayListInteger();for(int i0;i10;i) {buckets.add(i,new ArrayList());}// 将数据存储在buckets中for (int value : arr) {buckets.get((value/exp)%10).add(value);}//将每一次排序的结果复制到arr数组中int k0;for(ArrayListInteger list : buckets) {for(Integer num : list) {arr[k]num;}}//System.out.println(Arrays.toString(arr));}}public static void main(String[] args) {int[] arr { 26, 3, 49, 556, 81, 9, 863, 0 };radixSort(arr);System.out.println(Arrays.toString(arr));}
}
