域名怎么建网站,五莲网站设计,南京高淳开展规模性核酸检测,建设完网站如何信息更新目录 冒泡排序
选择排序
插入排序
希尔排序
归并排序
快速排序
堆排序
计数排序
桶排序
基数排序 冒泡排序
冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的序列#xff0c;依次比较两个元素#xff0c;如果它们的顺序错误就把它们交换过来。遍历…
目录 冒泡排序
选择排序
插入排序
希尔排序
归并排序
快速排序
堆排序
计数排序
桶排序
基数排序 冒泡排序
冒泡排序(Bubble Sort)是一种简单的排序算法。它重复地遍历要排序的序列依次比较两个元素如果它们的顺序错误就把它们交换过来。遍历序列的工作是重复地进行直到没有再需要交换为止此时说明该序列已经排序完成。这个算法的名字由来是因为越小的元素会经由交换慢慢 “浮” 到数列的顶端。
算法步骤 比较相邻的元素。如果第一个比第二个大就交换它们两个 对每一对相邻元素作同样的工作从开始第一对到结尾的最后一对这样在最后的元素应该会是最大的数 针对所有的元素重复以上的步骤除了最后一个 重复步骤 1~3直到排序完成。
/*** 冒泡排序* param arr* return arr*/
public static int[] bubbleSort(int[] arr) {for (int i 1; i arr.length; i) {// Set a flag, if true, that means the loop has not been swapped,// that is, the sequence has been ordered, the sorting has been completed.boolean flag true;for (int j 0; j arr.length - i; j) {if (arr[j] arr[j 1]) {int tmp arr[j];arr[j] arr[j 1];arr[j 1] tmp;// Change flagflag false;}}if (flag) {break;}}return arr;
}
算法分析 稳定性稳定 时间复杂度最佳O(n) 最差O(n2) 平均O(n2) 空间复杂度O(1) 排序方式In-place 选择排序
选择排序(Selection Sort)是一种简单直观的排序算法无论什么数据进去都是 O(n²) 的时间复杂度。所以用到它的时候数据规模越小越好。唯一的好处可能就是不占用额外的内存空间了吧。它的工作原理首先在未排序序列中找到最小大元素存放到排序序列的起始位置然后再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。以此类推直到所有元素均排序完毕。
算法步骤 首先在未排序序列中找到最小大元素存放到排序序列的起始位置 再从剩余未排序元素中继续寻找最小大元素然后放到已排序序列的末尾。 重复第 2 步直到所有元素均排序完毕。
/*** 选择排序* param arr* return arr*/
public static int[] selectionSort(int[] arr) {for (int i 0; i arr.length - 1; i) {int minIndex i;for (int j i 1; j arr.length; j) {if (arr[j] arr[minIndex]) {minIndex j;}}if (minIndex ! i) {int tmp arr[i];arr[i] arr[minIndex];arr[minIndex] tmp;}}return arr;
}
算法分析 稳定性不稳定 时间复杂度最佳O(n2) 最差O(n2) 平均O(n2) 空间复杂度O(1) 排序方式In-place 插入排序
(Insertion Sort)
算法步骤 从第一个元素开始该元素可以认为已经被排序 取出下一个元素在已经排序的元素序列中从后向前扫描 如果该元素已排序大于新元素将该元素移到下一位置 重复步骤 3直到找到已排序的元素小于或者等于新元素的位置 将新元素插入到该位置后 重复步骤 2~5。
/*** 插入排序* param arr* return arr*/
public static int[] insertionSort(int[] arr) {for (int i 1; i arr.length; i) {int preIndex i - 1;int current arr[i];while (preIndex 0 current arr[preIndex]) {arr[preIndex 1] arr[preIndex];preIndex - 1;}arr[preIndex 1] current;}return arr;
}
算法分析 稳定性稳定 时间复杂度最佳O(n) 最差O(n2) 平均O(n2) 空间复杂度O(1) 排序方式In-place 希尔排序
希尔排序(Shell Sort)的基本思想是先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序待整个序列中的记录 “基本有序” 时再对全体记录进行依次直接插入排序。
我们来看下希尔排序的基本步骤在此我们选择增量 gaplength/2缩小增量继续以 gap gap/2 的方式这种增量选择我们可以用一个序列来表示{n/2, (n/2)/2, ..., 1}称为增量序列。希尔排序的增量序列的选择与证明是个数学难题我们选择的这个增量序列是比较常用的也是希尔建议的增量称为希尔增量但其实这个增量序列不是最优的。此处我们做示例使用希尔增量。
先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序具体算法描述 选择一个增量序列 {t1, t2, …, tk}其中 (titj, ij, tk1) 按增量序列个数 k对序列进行 k 趟排序 每趟排序根据对应的增量 t将待排序列分割成若干长度为 m 的子序列分别对各子表进行直接插入排序。仅增量因子为 1 时整个序列作为一个表来处理表长度即为整个序列的长度。
/*** 希尔排序** param arr* return arr*/
public static int[] shellSort(int[] arr) {int n arr.length;int gap n / 2;while (gap 0) {for (int i gap; i n; i) {int current arr[i];int preIndex i - gap;// Insertion sortwhile (preIndex 0 arr[preIndex] current) {arr[preIndex gap] arr[preIndex];preIndex - gap;}arr[preIndex gap] current;
}gap / 2;}return arr;
}
算法分析 稳定性不稳定 时间复杂度最佳O(nlogn) 最差O(n^2) 平均O(nlogn) 空间复杂度O(1) 归并排序
归并排序(Merge Sort)是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 (Divide and Conquer) 的一个非常典型的应用。归并排序是一种稳定的排序方法。将已有序的子序列合并得到完全有序的序列即先使每个子序列有序再使子序列段间有序。若将两个有序表合并成一个有序表称为 2 - 路归并。
和选择排序一样归并排序的性能不受输入数据的影响但表现比选择排序好的多因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
算法步骤
归并排序算法是一个递归过程边界条件为当输入序列仅有一个元素时直接返回具体过程如下 如果输入内只有一个元素则直接返回否则将长度为 n 的输入序列分成两个长度为 n/2 的子序列 分别对这两个子序列进行归并排序使子序列变为有序状态 设定两个指针分别指向两个已经排序子序列的起始位置 比较两个指针所指向的元素选择相对小的元素放入到合并空间用于存放排序结果并移动指针到下一位置 重复步骤 3 ~4 直到某一指针达到序列尾 将另一序列剩下的所有元素直接复制到合并序列尾。
/*** 归并排序** param arr* return arr*/
public static int[] mergeSort(int[] arr) {if (arr.length 1) {return arr;}int middle arr.length / 2;int[] arr_1 Arrays.copyOfRange(arr, 0, middle);int[] arr_2 Arrays.copyOfRange(arr, middle, arr.length);return merge(mergeSort(arr_1), mergeSort(arr_2));
}
/*** Merge two sorted arrays** param arr_1* param arr_2* return sorted_arr*/
public static int[] merge(int[] arr_1, int[] arr_2) {int[] sorted_arr new int[arr_1.length arr_2.length];int idx 0, idx_1 0, idx_2 0;while (idx_1 arr_1.length idx_2 arr_2.length) {if (arr_1[idx_1] arr_2[idx_2]) {sorted_arr[idx] arr_1[idx_1];idx_1 1;} else {sorted_arr[idx] arr_2[idx_2];idx_2 1;}idx 1;}if (idx_1 arr_1.length) {while (idx_1 arr_1.length) {sorted_arr[idx] arr_1[idx_1];idx_1 1;idx 1;}} else {while (idx_2 arr_2.length) {sorted_arr[idx] arr_2[idx_2];idx_2 1;idx 1;}}return sorted_arr;
}
算法分析 稳定性稳定 时间复杂度最佳O(nlogn) 最差O(nlogn) 平均O(nlogn) 空间复杂度O(n) 快速排序
算法步骤
快速排序(Quick Sort)使用分治法策略来把一个序列分为较小和较大的 2 个子序列然后递回地排序两个子序列。具体算法描述如下 从序列中随机挑出一个元素做为 “基准”(pivot) 重新排列序列将所有比基准值小的元素摆放在基准前面所有比基准值大的摆在基准的后面相同的数可以到任一边。在这个操作结束之后该基准就处于数列的中间位置。这个称为分区partition操作 递归地把小于基准值元素的子序列和大于基准值元素的子序列进行快速排序。
public class Sort {public static void quickSort(int[] arr,int left,int right,int i ,int j) {
if(left right) { // left right | left rightreturn;}int base arr[left]; //基准数i left; //两个游标j right;
//当 i 和 j 不相遇的时候重复以下过程while(i ! j) {while(arr[j]base ij) {j--;}while(arr[i]base ij) {i;}//数据交换int temp arr[i];arr[i] arr[j];arr[j] temp;}//相遇位置的数和基准数交换arr[left] arr[i];arr[i] base;
quickSort(arr, left, i-1,i,j);quickSort(arr, i1, right,i,j);}
}
算法分析 稳定性不稳定 时间复杂度最佳O(nlogn) 最差O(nlogn)平均O(nlogn) 空间复杂度O(logn) 堆排序
堆排序(Heap Sort)是指利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构并同时满足堆的性质即子结点的值总是小于或者大于它的父节点。
算法步骤 将初始待排序列 (R1, R2, ……, Rn) 构建成大顶堆此堆为初始的无序区 将堆顶元素 R[1] 与最后一个元素 R[n] 交换此时得到新的无序区 (R1, R2, ……, Rn-1) 和新的有序区 (Rn), 且满足 R[1, 2, ……, n-1]R[n] 由于交换后新的堆顶 R[1] 可能违反堆的性质因此需要对当前无序区 (R1, R2, ……, Rn-1) 调整为新堆然后再次将 R [1] 与无序区最后一个元素交换得到新的无序区 (R1, R2, ……, Rn-2) 和新的有序区 (Rn-1, Rn)。不断重复此过程直到有序区的元素个数为 n-1则整个排序过程完成。
// Global variable that records the length of an array;
static int heapLen;
/*** Swap the two elements of an array* param arr* param i* param j*/
private static void swap(int[] arr, int i, int j) {int tmp arr[i];arr[i] arr[j];arr[j] tmp;
}
/*** Build Max Heap* param arr*/
private static void buildMaxHeap(int[] arr) {for (int i arr.length / 2 - 1; i 0; i--) {heapify(arr, i);}
}
/*** Adjust it to the maximum heap* param arr* param i*/
private static void heapify(int[] arr, int i) {int left 2 * i 1;int right 2 * i 2;int largest i;if (right heapLen arr[right] arr[largest]) {largest right;}if (left heapLen arr[left] arr[largest]) {largest left;}if (largest ! i) {swap(arr, largest, i);heapify(arr, largest);}
}
/*** Heap Sort* param arr* return*/
public static int[] heapSort(int[] arr) {// index at the end of the heapheapLen arr.length;// build MaxHeapbuildMaxHeap(arr);for (int i arr.length - 1; i 0; i--) {// Move the top of the heap to the tail of the heap in turnswap(arr, 0, i);heapLen - 1;heapify(arr, 0);}return arr;
}
算法分析 稳定性不稳定 时间复杂度最佳O(nlogn) 最差O(nlogn) 平均O(nlogn) 空间复杂度O(1) 计数排序
计数排序(Counting Sort)的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。 作为一种线性时间复杂度的排序计数排序要求输入的数据必须是有确定范围的整数。
计数排序 (Counting sort) 是一种稳定的排序算法。计数排序使用一个额外的数组 C其中第 i 个元素是待排序数组 A 中值等于 i 的元素的个数。然后根据数组 C 来将 A 中的元素排到正确的位置。它只能对整数进行排序。
算法步骤 找出数组中的最大值 max、最小值 min 创建一个新数组 C其长度是 max-min1其元素默认值都为 0 遍历原数组 A 中的元素 A[i]以 A[i]-min 作为 C 数组的索引以 A[i] 的值在 A 中元素出现次数作为 C[A[i]-min] 的值 对 C 数组变形新元素的值是该元素与前一个元素值的和即当 i1 时 C[i] C[i] C[i-1] 创建结果数组 R长度和原始数组一样。 从后向前遍历原始数组 A 中的元素 A[i]使用 A[i] 减去最小值 min 作为索引在计数数组 C 中找到对应的值 C[A[i]-min]C[A[i]-min]-1 就是 A[i] 在结果数组 R 中的位置做完上述这些操作将 count[A[i]-min] 减小 1。
/*** Gets the maximum and minimum values in the array** param arr* return*/
private static int[] getMinAndMax(int[] arr) {int maxValue arr[0];int minValue arr[0];for (int i 0; i arr.length; i) {if (arr[i] maxValue) {maxValue arr[i];} else if (arr[i] minValue) {minValue arr[i];}}return new int[] { minValue, maxValue };
}
/*** Counting Sort** param arr* return*/
public static int[] countingSort(int[] arr) {if (arr.length 2) {return arr;}int[] extremum getMinAndMax(arr);int minValue extremum[0];int maxValue extremum[1];int[] countArr new int[maxValue - minValue 1];int[] result new int[arr.length];
for (int i 0; i arr.length; i) {countArr[arr[i] - minValue] 1;}for (int i 1; i countArr.length; i) {countArr[i] countArr[i - 1];}for (int i arr.length - 1; i 0; i--) {int idx countArr[arr[i] - minValue] - 1;result[idx] arr[i];countArr[arr[i] - minValue] - 1;}return result;
}
算法分析
当输入的元素是 n 个 0 到 k 之间的整数时它的运行时间是 O(nk)。计数排序不是比较排序排序的速度快于任何比较排序算法。由于用来计数的数组 C 的长度取决于待排序数组中数据的范围等于待排序数组的最大值与最小值的差加上 1这使得计数排序对于数据范围很大的数组需要大量额外内存空间。 稳定性稳定 时间复杂度最佳O(nk) 最差O(nk) 平均O(nk) 空间复杂度O(k) 桶排序
桶排序(Bucket Sort)是计数排序的升级版。它利用了函数的映射关系高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效我们需要做到这两点 在额外空间充足的情况下尽量增大桶的数量 使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中
桶排序的工作的原理假设输入数据服从均匀分布将数据分到有限数量的桶里每个桶再分别排序有可能再使用别的排序算法或是以递归方式继续使用桶排序进行。
算法步骤 设置一个 BucketSize作为每个桶所能放置多少个不同数值 遍历输入数据并且把数据依次映射到对应的桶里去 对每个非空的桶进行排序可以使用其它排序方法也可以递归使用桶排序 从非空桶里把排好序的数据拼接起来。
/*** Gets the maximum and minimum values in the array* param arr* return*/
private static int[] getMinAndMax(ListInteger arr) {int maxValue arr.get(0);int minValue arr.get(0);for (int i : arr) {if (i maxValue) {maxValue i;} else if (i minValue) {minValue i;}}return new int[] { minValue, maxValue };
}
/*** Bucket Sort* param arr* return*/
public static ListInteger bucketSort(ListInteger arr, int bucket_size) {if (arr.size() 2 || bucket_size 0) {return arr;}int[] extremum getMinAndMax(arr);int minValue extremum[0];int maxValue extremum[1];int bucket_cnt (maxValue - minValue) / bucket_size 1;ListListInteger buckets new ArrayList();for (int i 0; i bucket_cnt; i) {buckets.add(new ArrayListInteger());}for (int element : arr) {int idx (element - minValue) / bucket_size;buckets.get(idx).add(element);}for (int i 0; i buckets.size(); i) {if (buckets.get(i).size() 1) {buckets.set(i, sort(buckets.get(i), bucket_size / 2));}}ArrayListInteger result new ArrayList();for (ListInteger bucket : buckets) {for (int element : bucket) {result.add(element);}}return result;
}
算法分析 稳定性稳定 时间复杂度最佳O(nk) 最差O(n²) 平均O(nk) 空间复杂度O(nk) 基数排序
基数排序 (Radix Sort)也是非比较的排序算法对元素中的每一位数字进行排序从最低位开始排序复杂度为 O(n×k)n 为数组长度k 为数组中元素的最大的位数
基数排序是按照低位先排序然后收集再按照高位排序然后再收集依次类推直到最高位。有时候有些属性是有优先级顺序的先按低优先级排序再按高优先级排序。最后的次序就是高优先级高的在前高优先级相同的低优先级高的在前。基数排序基于分别排序分别收集所以是稳定的。
算法步骤 取得数组中的最大数并取得位数即为迭代次数 N例如数组中最大数值为 1000则 N4 A 为原始数组从最低位开始取每个位组成 radix 数组 对 radix 进行计数排序利用计数排序适用于小范围数的特点 将 radix 依次赋值给原数组 重复 2~4 步骤 N 次
/*** Radix Sort** param arr* return*/
public static int[] radixSort(int[] arr) {if (arr.length 2) {return arr;}int N 1;int maxValue arr[0];for (int element : arr) {if (element maxValue) {maxValue element;}}while (maxValue / 10 ! 0) {maxValue maxValue / 10;N 1;}for (int i 0; i N; i) {ListListInteger radix new ArrayList();for (int k 0; k 10; k) {radix.add(new ArrayListInteger());}for (int element : arr) {int idx (element / (int) Math.pow(10, i)) % 10;radix.get(idx).add(element);}int idx 0;for (ListInteger l : radix) {for (int n : l) {arr[idx] n;}}}return arr;
}
算法分析 稳定性稳定 时间复杂度最佳O(n×k) 最差O(n×k) 平均O(n×k) 空间复杂度O(nk)
基数排序 vs 计数排序 vs 桶排序
这三种排序算法都利用了桶的概念但对桶的使用方法上有明显差异 基数排序根据键值的每位数字来分配桶 计数排序每个桶只存储单一键值 桶排序每个桶存储一定范围的数值
