网站模板 jsp,做网站的销售团队,郑州最新发布,it培训班学出来有用吗目录
一丶时间复杂度
二丶空间复杂度
三丶Java常见排序 1. 冒泡排序#xff08;Bubble Sort#xff09; 2.插入排序#xff08;Insertion Sort#xff09; 3.希尔排序#xff08;Shell Sort#xff09; 4.选择排序#xff08;Selection Sort#xff09; 5.堆排序Bubble Sort 2.插入排序Insertion Sort 3.希尔排序Shell Sort 4.选择排序Selection Sort 5.堆排序Heap Sort 6.归并排序Merge Sort 7.快速排序Quick Sort 8.计数排序Counting Sort、桶排序Bucket Sort 和 基数排序Radix Sort 简介时间复杂度和空间复杂度是评估算法性能的两个重要指标他们分别用于衡量算法执行时间长短和算法所存储空间大小
一丶时间复杂度 时间复杂度他描述了算法执行所需时间和数据规模之间的关系。具体来说时间复杂度是算法中基本操作语句执行的次数这次次数随着数据规模的增大而增大。时间复杂度通常用大O表示法Big O notation来表示他忽略了常数因子和低阶项只保留最高阶项从而简洁明了的表示出算法的时间增长趋势例如
O(1)表示算法的执行时间是固定与输入规模无关O(log n)表示算法的执行时间与输入规模的对数成正比O(n)表示线性时间复杂度算法的执行时间与输入规模成线性比例增长O(n log n)表示算法的执行时间与输入规模的线性对数比例增长O(n^2)表示平方时间复杂度算法的执行时间与输入规模的平方成比例增长。
通过分析算法的时间复杂度可以评估算法的性能优化算法的效率从而提高程度的执行速度。
二丶空间复杂度 空间复杂度它描述了算法在运行过程中临时占用存储空间的大小与数据规模之间的关系。空间复杂度也是用大O表示法来表示他衡量的是算法运行过程中额外消耗的存储空间。例如
O(1)表示算法的空间复杂度是固定的与输入规模无关O(log n)表示线性空间复杂度算法所需内存与输入规模成线性比例增长O(n^2)表示平方空间复杂度算法所需内存与输入规模的平方成比例增长。
通过分析算法的空间复杂度可以避免内存的浪费提高空间利用率从而降低算法执行成本提高程序性能
三丶Java常见排序 1. 冒泡排序Bubble Sort 原理通过重复地遍历要排序的数列一次比较两个元素如果他们的顺序错误就把他们交换过来。遍历数列的工作是重复的进行直到没有再需要交换也就是说该数列已经排序完成。 特点简单稳定单效率低。时间复杂度O(n^2),空间复杂度O(1); //冒泡排序public static void bubbleSort(int[] arr) {int n arr.length;for (int i 0; i n-1; i) {for (int j 0; j n-i-1; j) {if (arr[j] arr[j1]) {int temp arr[j];arr[j] arr[j1];arr[j1] temp;}}}} 2.插入排序Insertion Sort 原理通过构建有序序列对于未排序数据在已排序序序列中从后向前扫描找到相应位置插入 特点稳定排序适用于少量数据的排序但是数据接近有序时效率较高。时间复杂度最好的情况下O(n),最坏的情况下O(n^2);空间复杂度O(1) //直接插入排序public static void insertionSort(int[] arr) {int n arr.length;for (int i 1; i n; i) {//取出第二个数据默认已经排序int key arr[i];//获取前以为数据的索引int j i-1;/* 将 arr[0..i-1] 中大于 key 的元素移动到其当前位置的前 1 个位置*/while (j 0 arr[j] key) {arr[j1] arr[j];j j-1;}arr[j1] key;}} 3.希尔排序Shell Sort 原理是插入排序的一种更高效的改进版本。希尔排序又称为缩小量排序它将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录基本有序在对全体记录进行直接插入排序 特点不稳定的排序时间复杂度依赖于增量序列的选择但平均性能优于直接插入排序
时间复杂度O(n^1.3)空间复杂度O(1); //直接排序public static void shellSort(int[] arr) {int n arr.length;for (int gap n/2; gap 0; gap / 2) {for (int i gap; i n; i 1) {int temp arr[i];int j;for (j i; j gap arr[j - gap] temp; j - gap) {arr[j] arr[j - gap];}arr[j] temp;}}} 4.选择排序Selection Sort 原理首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾 特点不稳定排序时间复杂度O(n^2)空间复杂度O(1) //选择排序public void selectionSort(int[] arr) {int n arr.length;for (int i 0; i n-1; i) {int min_idx i;for (int j i1; j n; j) {if (arr[j] arr[min_idx]) {min_idx j;}}// 将找到的 Minimum 元素与第一个元素交换int temp arr[min_idx];arr[min_idx] arr[i];arr[i] temp;}} 5.堆排序Heap Sort 原理是指利用堆这种数据结构所设计的一种排序算法。堆积是一个近似完全二叉树的结构并同时满足堆积的性质即子节点的键值或索引总是小于或大于他的父节点 特点不稳定排序时间复杂度O(n log n)空间复杂度O(1) // 构建最大堆辅助函数
void buildMaxHeap(int arr[]) { int n arr.length; for (int i n / 2 - 1; i 0; i--) heapify(arr, n, i);
} // 调整给定的堆
void heapify(int arr[], int n, int i) { int largest i; // 初始化最大为根 int l 2 * i 1; // 左 2*i 1 int r 2 * i 2; // 右 2*i 2 // 如果左子节点大于根 if (l n arr[l] arr[largest]) largest l; // 如果右子节点是最大值 if (r n arr[r] arr[largest]) largest r; // 如果最大值不是根 if (largest ! i) { int swap arr[i]; arr[i] arr[largest]; arr[largest] swap; // 递归地堆化受影响的子树 heapify(arr, n, largest); }
} // 堆排序函数
void heapSort(int arr[]) { int n arr.length; buildMaxHeap(arr); // 一个个从堆顶取出元素 for (int i n - 1; i 0; i--) { // 移动当前根到末尾 int temp arr[0]; arr[0] arr[i]; arr[i] temp; // 调用max heapify on the reduced heap heapify(arr, i, 0); }
} 6.归并排序Merge Sort 原理是建立在归并操作上的一种有效的排序算法。该算法是采用分治法Divide and Conquer的一个非常典型的应用。将已有序的子序合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序 特点稳定排序时间复杂度O(n log n)空间复杂度O(n) public void mergeSort(int[] arr, int l, int r) { if (l r) { // Same as (lr)/2, but avoids overflow for // large l and h int m l(r-l)/2; // Sort first and second halves mergeSort(arr, l, m); mergeSort(arr, m1, r); merge(arr, l, m, r); }
} // 合并两个已排序的数组部分
void merge(int arr[], int l, int m, int r) { // Find sizes of two subarrays to be merged int n1 m - l 1; int n2 r - m; /* Create temp arrays */ int L[] new int[n1]; int R[] new int[n2]; /*Copy data to temp arrays*/ for (int i0; in1; i) L[i] arr[l i]; for (int j0; jn2; j) R[j] arr[m 1 j]; /* Merge the temp arrays */ // Initial indexes of first and second subarrays int i 0, j 0; // Initial index of merged subarray array int k l; while (i n1 j n2) { if (L[i] R[j]) { arr[k] L[i]; i; } else { arr[k] R[j]; j; } k; } /* Copy remaining elements of L[] if any */ while (i n1) { arr[k] L[i]; i; k; } /* Copy remaining elements of R[] if any */ while (j n2) { arr[k] R[j]; j; k; }
} 7.快速排序Quick Sort 原理通过一趟排序将要排序的数据分割成独立的两部分其中一部分的所有数据都比另外一部分的所有数据都要小然后再按此方法对这两部分数据分别进行快速排序整个排序过程可以递归进行以此达到整个数据变成有序序列 特点平均时间复杂度O(n log n)但是最坏的情况下时间复杂度会变成O(n^2)。空间复杂度取决于递归深度平均为O(n log n)但最坏情况下需要O(n)的额外空间
public void quickSort(int[] arr, int low, int high) { if (low high) { // pi is partitioning index, arr[p] is now // at right place int pi partition(arr, low, high); // Separately sort elements before // partition and after partition quickSort(arr, low, pi - 1); quickSort(arr, pi 1, high); }
} // 该方法用于分区数组返回分区索引
int partition(int arr[], int low, int high) { int pivot arr[high]; int i (low - 1); // index of smaller element for (int j low; j high; j) { // If current element is smaller than or // equal to pivot if (arr[j] pivot) { i; // swap arr[i] and arr[j] int temp arr[i]; arr[i] arr[j]; arr[j] temp; } } // swap arr[i1] and arr[high] (or pivot) int temp arr[i 1]; arr[i 1] arr[high]; arr[high] temp; return i 1;
} 8.计数排序Counting Sort、桶排序Bucket Sort 和 基数排序Radix Sort
这些排序算法是非比较型排序算法其排序效率在某些情况下会高于比较型排序算法。它们各自适用于一定范围的数据如计数排序适用于一定范围内的整数排序桶排序和基数排序则适用于外部排序和大数据排序。 结尾喜欢的朋友点个赞吧
