排序算法:所有常见排序方法 Myth丶恋晨 2022-10-29 09:15 131阅读 0赞 ## 排序算法 ## ### O ( n 2 ) O(n^2) O(n2) ### #### 冒泡排序 #### void bubbleSort(int[] arr){ for(int i = 0 ; i < arr.length ; i ++){ for(int j = 0 ; j < arr.length - i - 1 ; j ++ ){ if(arr[j] > arr[j + 1]){ int mid = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = mid; } } } } #### 选择排序 #### void selectSort(int[] arr){ for(int i = 0 ; i < arr.length ; i ++){ for(int j = i + 1; j < arr.length ; j ++){ if(arr[j] < arr[i]){ int mid = arr[i]; arr[i] = arr[j]; arr[j] = mid; } } } } #### 插入排序 #### * 近乎有序的话可达到 O(n) 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 mid = arr[j]; arr[j] = arr[j - 1]; arr[j - 1] = mid; } } } } #### 希尔排序 #### * 复杂度 O ( n 2 / 3 ) O(n^\{2/3\}) O(n2/3) 关键思想 * 进行排序的元素索引位置是 0、step、2step、3step … void shellsort(int[] arr){ for(int step = arr.length - 1 ;step >= 1 ; step /= 2){ for(int i = step ; i <= arr.length - 1 ; i += step){ for(int j = i ; j >= step ; j -= step){ if(arr[j] < arr[j - step]){ int mid = arr[j]; arr[j] = arr[j - step]; arr[j - step] = mid; } } } } } ### O ( n l o g n ) O(nlogn) O(nlogn) ### #### 归并排序 #### 递归的终止 * 二分就是只有一个元素时终止 每次 return 都返回一个新数组 * 原数组只用来传值 归并过程的三个索引 * 右边数组的 * 左边数组的 * 归并后要返回的数组的 int[] mergeSort(int[] arr){ return merge(arr , 0 , arr.length - 1); } private int[] merge(int[] arr , int l , int r){ // 明确递归终止 //对于分治来说,比如分两段,那么终止条件一定是一段长度是 1;如果分三段,那么终止条件一定是该段长度 1 或者 2,否则还可再分 if(r - l == 0 ){ return new int[]{ arr[r]}; } int mid = (l + r) / 2; int[] lArr = merge(arr , l , mid); int[] rArr = merge(arr , mid + 1 , r); int[] res = new int[r - l + 1]; for(int i = 0 , lIndex = 0 , rIndex = 0; i < r - l + 1 ; i ++){ if( rIndex >= rArr.length || ( lIndex < lArr.length && lArr[lIndex] <= rArr[rIndex])){ res[i] = lArr[lIndex ++]; }else { res[i] = rArr[rIndex ++]; } } return res; } #### 快排 #### 三个索引 * 要确定位置元素的索引 * 区间右边的索引(代表比 * 区间左边的索引 终止条件 * while( lIdx <= rIdx) * 因为如果只有两个元素的话,那么 lIdx 就等于 rIdx 了 * 因此目标元素的位置就是 rIdx(因为这种终止条件下, Idx 代表的是比 target 大的,所以其左边第一个才是<= target 的) void quickSort(int[] arr){ _quickSort(arr , 0 , arr.length - 1); } private static void _quickSort(int[] arr , int l , int r){ if(l >= r){ return; } int target = arr[l]; int lIdx = l + 1 , rIdx = r; // 因为要让两个元素的也能进入,所以终止条件取 =,即: // lIdx 最终代表的 >= target 的 // rIdx 是 < target 的或者是起始位置下一个 while(lIdx <= rIdx){ if(arr[lIdx] >= target){ while (arr[rIdx] > target && lIdx <= rIdx){ rIdx --; } if (lIdx > rIdx) { break; }else { ArrUtil.swap(arr , lIdx , rIdx --); } } lIdx ++; } ArrUtil.swap(arr , l , rIdx); _quickSort(arr , l , rIdx - 1); _quickSort(arr , rIdx + 1 , r); } #### 堆排序 #### 两个步骤 * 构建大堆 * 从 i = 1 开始,i = arr.length 结束 * 自底向上调整(只比较父节点就可以,因为只要保证每个节点增加时都比父节点小,那么就不用担心交换做了父节点后但比另一个兄弟小),保证父节点必须比两个子节点都大,不然就交换 * 对大堆进行调整 * 从后向前遍(即 i = arr.length - 1 开始),直到只剩一个元素(即 i = 1)结束 * 把堆顶(即 index = 1,代表的最大元素)和最后的位置的元素交换 * 重新调整堆(自顶向下调整,直到遇见父节点都比左右子节点大结束),然后又得到新的堆顶 * 重复上面两步 void heapSort(int[] arr){ // 构建大堆 for(int i = 1; i < arr.length ; i ++ ){ int newDataIdx = i; int parent = newDataIdx / 2; while(parent >= 1 && arr[parent] < arr[newDataIdx]){ ArrUtil.swap(arr , parent , newDataIdx); newDataIdx = parent; parent /= 2; } } // 用大堆实现从小到大排序 for(int i = arr.length - 1; i > 1 ; i --){ ArrUtil.swap(arr , i , 1); int parent = 1; while (parent <= (arr.length - 1) /2 && (arr[parent * 2] > arr[parent] || arr[parent * 2 + 1] > arr[parent])){ int lchildIdx = parent * 2 < i ? parent * 2 : 0; int rchildIdx = parent * 2 + 1 < i ? parent * 2 + 1 : 0; int newParentIdx; if( lchildIdx == 0){ break; }else if(rchildIdx == 0){ newParentIdx = lchildIdx; }else { newParentIdx = arr[lchildIdx] > arr[rchildIdx] ? lchildIdx : rchildIdx; } ArrUtil.swap(arr , newParentIdx , parent); parent = newParentIdx; } } } ### O(n) ### #### 计数排序 #### * 仅适用于已知有多少种不同元素 思想 * 遍历一次,对每种的元素个数进行计数 * 按每种元素的个数进行还原(例如 3个1、2个2,那么数组前三个放 1,后两个放 2)
相关 探索排序算法:C语言实现常见排序方法 -------------------- 探索排序算法:C语言实现常见排序方法 排序算法是计算机科学中一个基本且重要的领域,它们在数据处理和搜索等任务中扮演着关键角色。 深藏阁楼爱情的钟/ 2023年10月14日 22:01/ 0 赞/ 19 阅读
相关 [排序算法] 常见的排序算法 前言 1.冒泡排序 2.选择排序 3.插入排序 4希尔排序 5.归并排序 6.快速排序 前言 在实际需求中,我们可能要 雨点打透心脏的1/2处/ 2023年09月29日 14:29/ 0 赞/ 237 阅读
相关 排序算法:所有常见排序方法 排序算法 O ( n 2 ) O(n^2) O(n2) 冒泡排序 void bubbleSort(int[] arr){ Myth丶恋晨/ 2022年10月29日 09:15/ 0 赞/ 132 阅读
相关 常见排序算法 注:点进链接查看算法具体实现!!! -------------------- 插入排序 [直接插入排序][Link 1] [希尔排序][Link 2] - 怼烎@/ 2022年06月16日 09:10/ 0 赞/ 204 阅读
相关 常见排序算法 常见排序: ![这里写图片描述][SouthEast] 1、直接插入排序 在给定数组中,拿出一个数M,与前面的数相比较,如果M大于前面的数,位置不变,如果小于前面的 迷南。/ 2022年06月05日 05:51/ 0 赞/ 275 阅读
相关 常见排序算法 常见排序算法 排序问题作为算法基础的重要组成部分,代码实现方式多种多样,但其原理是基本一致的。常见的排序算法有: ①. 冒泡排序 ②. 选择排序 ③. 插入排序 偏执的太偏执、/ 2022年05月16日 07:28/ 0 赞/ 286 阅读
相关 常见排序算法 今天实在不想刷笔试题就把常见的排序手敲了一遍 -------------------- 1.选择排序 class ChoiceSort<T extends 约定不等于承诺〃/ 2022年01月15日 13:35/ 0 赞/ 295 阅读
相关 常见排序算法 稳定排序:假设在待排序的文件中,存在两个或两个以上的记录具有相同的关键字,在用某种排序法排序后,若这些相同关键字的元素的相对次序仍然不变,则这种排序方法是稳定的。(即原本a在b 墨蓝/ 2022年01月06日 03:01/ 0 赞/ 314 阅读
还没有评论,来说两句吧...