江苏龙网

  1. 主页 > 生活百科 > >

java代码实现 排序算法详解( 二 )

排序算法



java代码实现 排序算法详解

文章插图
 
3、直接插入排序? 插入排序 。每一次把一个待排序的记录，按照值的大小，插入到有序数组的合适位置 。
? 相当于把a[n]分割，先排序数组 a[0] ~ a[1]，再 a[0] ~ a[2]，直到 a[0] ~ a[n] 全部排序完成 。
3.1 算法步骤
  1. 第一个元素之前没有值，认为已经排序
  2. 取下一个待排序元素，下标为 i，向前进行比较
  3. 如果待排序元素比待比较元素小，则交换位置
  4. 重复步骤3直到有一个元素等于或者小于待排序元素，此次内循环结束，a[0] ~ a[i]排序完成
  5. 重复步骤2~4，直到最后一个元素
3.2 时间复杂度? 认为第一元素已经排好序，从第二个元素开始向前比较，计算需要比较的次数：
[O(n) = 1+2+3+cdots+n-1= frac{(n-1)*n}{2}\ 即O(n) = n^2 ]
 
3.3 代码实现public static int[] insertionSort(int[] arr){ // 从第二个元素开始到最后一个元素 for (int i = 1; i < arr.length; i++) {// 向前遍历for( int j = i ; j > 0 ; j -- ){if( arr[j] < arr[j-1] ){swap( arr, j , j-1 );}else{break;}} } return arr;}private static void swap(int[] arr, int i, int j) { int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp;}3.4 图示
java代码实现 排序算法详解

文章插图
 

java代码实现 排序算法详解

文章插图
 
4、希尔排序? 插入排序 。因为设计该算法的人叫Shell，所以叫希尔排序，又称缩小增量排序 。思路上是将待排序序列分割成若干个子序列进行直接插入排序，并逐渐缩减少子序列个数，直到针对整体进行一次排序 。
4.1 算法步骤
  1. 设置一个递减增量序列 $$t_1,t_2,cdots,t_k$$，(t_k)为1
  2. 按照增量个数k，整体上对序列进行k次排序
  3. 每次排序，根据增量 t，将序列分割成 (数组长度 / (t_i)) 个子序列，对子序列分别进行直接插入排序，当增量为1时，对序列整体进行一次排序
4.2 时间复杂度? 希尔排序的时间复杂度和增量的选择有关，证明的话我是不会，最坏时间复杂度是(O(n^2))，当n在某个范围内时，可以达到(O(n^{1.3}))
4.3 代码实现/** 该代码与实际算法步骤有区别： 算法步骤是说针对每个子序列进行直接插入排序，实际上对每个子序列的直插排序是交替进行的**/public static void shellSort(int[] arr) { int length = arr.length; // 记录需要进行直接插入排序的值 int temp; // 增量step从length/2递减到1进行循环 for (int step = length / 2; step >= 1; step /= 2) {// 进行直插排序，默认第一个元素已经排序完成，从step下标的元素开始向前进行直插for (int i = step; i < length; i++) {// 需要对arr[i]进行直接插入排序，记录该值temp = arr[i];// j来记录temp最后需要插入的位置int j = i;while (j -step >= 0 && arr[j-step] > temp) {arr[j] = arr[j-step];j -= step;}arr[j] = temp;} }}// 使用直接插入版本的代码：private static void shellSort2(int[] arr) { int len = arr.length; for (int step = len / 2; step > 0; step = step / 2) {// 直接插入排序的代码，只不过向前遍历时遍历的数组为i,i-step,i-step-step...for (int i = step; i < arr.length; i++) {for (int j = i; j-step >= 0; j -= step) {if (arr[j] < arr[j - step]) {swap(arr, j, j - step);}}} }}private static void swap(int[] arr, int i, int j) {int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}4.4 图示
java代码实现 排序算法详解

文章插图
 

java代码实现 排序算法详解

文章插图
 
5、简单选择排序? 选择排序 。从未排序序列中查找一个最小值，然后将该值放到已排序序列的末尾位置，循环下去，直到最后一个元素 。
5.1 算法步骤
  1. 从 a[i] 开始，i=0,1,2,...,n，在数组中找到最小值的下标，放到arr[i]，此时 a[0] ~ a[i] 有序，a[i+1] ~ a[n] 待排序
  2. 待排序序列重复步骤1
  3. 经过n-1次循环完成排序
5.2 时间复杂度? 循环次数为n-1，n-2，n-3，(cdots)，1
[O(n) = (n-1)+(n-2)+cdots+1\ O(n) = frac{1}{2}(n^2-n)\ O(n) = n^2 ]
 
5.3 代码实现public static int[] selectionSort(int[] arr){ // 外层循环经过 n-1 轮比较 for (int i = 0; i < arr.length - 1; i++) {// min用来记录每次比较过程中最小值的下标int min = i;// 0~i已经排序完成，从i向后比较查找后面序列的最小值for (int j = i + 1; j < arr.length; j++) {if (arr[j] < arr[min]) {// 记录最小值元下标min = j;}}// 将找到的最小值和i位置所在的值进行交换if (i != min) {swap(arr, i ,min);} } return arr;}


推荐阅读


上一篇：Nginx入门的基本使用和配置详解

下一篇：架构实战——Dapr 的轻量级、安全、便携和高性能运行时