算法之排序

概述

记录排序算法。

1 选择排序

*** 选择排序* 思路：遍历数组，找出（选择）最小的元素，然后和最左边的元素交换。接下来，再从第二个元素开始遍历整个数组。再找到最小的元素，再和第二个元素交换。* 重复该过程，直至遍历完成。* 时间复杂度：n^2* 空间复杂度：1（原地排序，除了临时变量不需要额外空间）* @param arr 数组* @return 排好序的数组*/public static int[] selectSort(int[] arr){// 边界条件if(arr.length < 1){return arr;}// 0 - n// 1 - n// ...// i - nfor(int i = 0; i < arr.length; i++){int minIndex = i;// 在i-n范围内找最小的for(int j = i+1; j < arr.length; j++){if(arr[minIndex] > arr[j]){minIndex = j;}}swap(i, minIndex, arr);}return arr;}/*** 索引i和j位置的元素交换* @param i 索引* @param j 索引* @param arr 数组*/public static void swap(int i, int j, int[] arr){int temp = arr[i];arr[i] = arr[j];arr[j] = temp;}

2 冒泡排序

/*** 2冒泡排序* 关键词：两两比较* 思路：* 第一次遍历，从0到n-1遍历数组。两两比较，大的元素往后排，最后遍历结束时，最大的元素就排在了数组末尾。* 第二次遍历，从0到n-2遍历数组。两两比较，大的元素往后排，最后遍历结束时，0到n-2中最大的元素就排在了数组n-1的位置处。* ...* 时间复杂度：n^2* 空间复杂度：1* 注意：因为是j+1，为防止越界，添加条件1：j <= i-1；又因为是i-1，添加条件2：i > 0；* @param arr 数组* @return 排好序的数组*/public static int[] bubbleSort(int[] arr){// 边界条件if(arr.length < 2){return arr;}for(int i = arr.length - 1; i > 0; i--){// 从0到i遍历，两两比较for(int j = 0; j <= i-1; j++){if(arr[j] > arr[j+1]){swap(j, j+1, arr);}}}return arr;}

3 插入排序

/*** 插入排序* 理解：打牌，在发牌时，先整理好手上的牌。拿到新发的牌后，往手上已经整理好的牌中插入。* 思路：* 从0到0，自己和自己比，不用排序* 从0到1，小的往前排，直至排到第一个位置* 从0到2，小的往前排，直至拍到第一个位置或者前面的更小* @param arr 数组* @return 有序数组*/public static int[] insertSort(int[] arr){if(arr == null || arr.length < 2){return arr;}for(int i = 0; i < arr.length; i++){for(int j = i; j >= 0; j--){if(j-1 < 0){continue;}if(arr[j-1] > arr[j]){swap(j, j-1, arr);}}}return arr;}