java中常用的七大排序算法
更新时间:2024-06-20 13:31:01 阅读量: 综合文库 文档下载
- Java常用排序算法推荐度:
- 相关推荐
java中常用的七大排序算法
这段时间闲了下来,就抽了点时间总结了下java中常用的七大排序算法,希望以后可以回顾!
1.插入排序算法
插入排序的基本思想是在遍历数组的过程中,假设在序号i之前的元素即 [0..i-1] 都已经排好序,本趟需要找到i对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位,为元素 x “腾位置”,最后将 k 对应的元素值赋为 x ,一般情况下,插入排序的时间复杂度和空间复杂度分别为O(n2) 和 O(1)。 /**
* @paramint[] 未排序数组 * @return int[] 排完序数组 */
publicint[] sortInsert(int[] array){ for(inti=1;i
for(j=i-1;j >= 0 &&temp< array[j]; j--){
array[j + 1] = array[j]; }
array[j + 1] = temp; }
return array; }
2.选择排序算法
选择排序的基本思想是遍历数组的过程中,以i代表当前需要排序的序号,则需要在剩余的 [i?n-1] 中找出其中的最小值,然后将找到的最小值与i指向的值进行交换。因为每一趟确定元素的过程中都会有一个选择最大值的子流程,所以人们形象地称之为选择排序。选择排序的时间复杂度和空间复杂度分别为O(n2)和O(1)。 /**
* @paramint[] 未排序数组 * @return int[] 排完序数组 */
publicint[] sortSelect(int[] arr){ for (inti = 0; i
for (int m = i + 1; m
if (arr[i] >arr[miniPost]) { int temp;
temp = arr[i];
arr[i] = arr[miniPost]; arr[miniPost] = temp; } }
returnarr; }
3.冒泡排序算法
冒泡排序的基本思想是將比較大的數字沉在最下面,较小的浮在上面。 冒泡排序的时间复杂度和空间复杂度分别是O(n2)和O(1)。 /**
* @paramint[] 未排序数组 * @return int[] 排完序数组 */
publicint[] sortBubble(int[] array){ int temp;
// 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次(肯定不需和自己比)
for(inti=0;i
for (int j = array.length - 1; j >i; j--) { if (array[j] < array[j - 1]) { temp = array[j];
array[j] = array[j - 1]; array[j - 1] = temp; } } }
return array; }
4.快速排序算法
通过一趟排序将待排记录分割成独立的两部分,其中一部分记录的关键字均比另一部分的关键字小,则可以分别对这两部分记录继续进行排序,已达到整个序列有序的目的,本质就是,找一个基位(枢轴,分水岭,作用是左边的都比它小,右边的都比它大。)
基位可随机选取,取名base,首先从序列最右边开始找比base小的,如果小,换位置,从而base移到刚才右边(比较时比base小)的位置(记为临时的high位),这样base右边的都比base大。然后从序列的最左边开始找比base大的,如果大,换位置,从而base移动到刚才左边(比较时比base大)的位置(记为临时的low位),这样base左边的都比base小,循环以上两步,直到 low == heigh,这使才真正的找到了枢轴---分水岭。返回这个位置,分水岭左边和右边的序列,分别再来递归。
快速排序的时间复杂度和空间复杂度都是O(nlogn)。
/**
* @paramint[] 未排序数组 * @return int[] 排完序数组 */
publicint[] sortQuick(int[] array){
returnquickSort(array, 0, array.length-1); }
privateint[] quickSort(int[] arr, int low, intheigh) { if (low int division = partition(arr, low, heigh); quickSort(arr, low, division - 1); quickSort(arr, division + 1, heigh); } returnarr; } // 分水岭,基位,左边的都比这个位置小,右边的都大 privateint partition(int[] arr, int low, intheigh) { int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录 while (low // base 赋值给当前heigh位,base 挪到(互换)到了这里,heigh位右边的都比base大 swap(arr, heigh, low); while (low // now low = heigh; return low; } private void swap(int[] arr, int a, int b) { int temp; temp = arr[a]; arr[a] = arr[b]; arr[b] = temp; } 5.合并排序算法 归并排序采用的是递归来实现,属于“分而治之”,将目标数组从中间一分为二,之后分别对这两个数组进行排序,排序完毕之后再将排好序的两个数组“归并”到一起,归并排序最重要的也就是这个“归并”的过程,归并的过程中需要额外的跟需要归并的两个数组长度一 致的空间 合并排序的时间复杂度和空间复杂度是O(nlogn)和O(n)。 /** * @paramint[] 未排序数组 * @return int[] 排完序数组 */ privateint[] sort(int[] nums, int low, int high) { int mid = (low + high) / 2; if (low < high) { // 左边 sort(nums, low, mid); // 右边 sort(nums, mid + 1, high); // 左右归并 merge(nums, low, mid, high); } returnnums; } private void merge(int[] nums, int low, int mid, int high) { int[] temp = new int[high - low + 1]; inti = low;// 左指针 int j = mid + 1;// 右指针 int k = 0; // 把较小的数先移到新数组中 while (i<= mid && j <= high) { if (nums[i] temp[k++] = nums[j++]; } } // 把左边剩余的数移入数组 while (i<= mid) { temp[k++] = nums[i++]; } // 把右边边剩余的数移入数组 while (j <= high) { temp[k++] = nums[j++]; } // 把新数组中的数覆盖nums数组 for (int k2 = 0; k2 } publicint[] sortMerge(int[] array) { return sort(array, 0, array.length - 1); } 6.希尔(shell)排序算法 希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”,划分为若干个小的数组。 以 gap 来划分,比如数组 [1, 2, 3, 4, 5, 6, 7, 8] ,如果以 gap = 2 来划分,可以分为 [1, 3, 5, 7] 和 [2, 4, 6, 8] 两个数组(对应的,如 gap = 3 ,则划分的数组为: [1, 4, 7] 、 [2, 5, 8] 、 [3, 6] )然后分别对划分出来的数组进行插入排序,待各个子数组排序完毕之后再减小 gap 值重复进行之前的步骤,直至 gap = 1 ,即对整个数组进行插入排序。 此时的数组已经基本上快排好序了,所以需要移动的元素会很小很小,解决了插入排序在处理大规模数组时较多移动次数的问题,希尔排序是插入排序的改进版,在数据量大的时候对效率的提升帮助很大,数据量小的时候建议直接使用插入排序就好了。 希尔排序的时间复杂度和空间复杂度是O(n1.3)和O(1)。 /** * @paramint[] 未排序数组 * @return int[] 排完序数组 */ publicint[] sortShell(int[] array) { // 取增量 int step = array.length / 2; while (step >= 1) { for (inti = step; i // 跟插入排序的区别就在这里 for (j = i - step; j >= 0 && temp < array[j]; j -= step) { array[j + step] = array[j]; } array[j + step] = temp; } step /= 2; } return array; } 7.堆排序算法 本质就是先构造一个大顶堆,parent比children大,root节点就是最大的节点把最大的节点(root)与尾节点(最后一个节点,比较小)位置互换,剩下最后的尾节点,现在最大,其余的,从第一个元素开始到尾节点前一位,构造大顶堆递归。 堆排序的时间复杂度和空间复杂度分别是O(nlogn)和O(1)。 /** * @paramint[] 未排序数组 * @return int[] 排完序数组 */ publicint[] sortHeap(int[] array) { buildHeap(array);// 构建堆 int n = array.length; inti = 0; for (i = n - 1; i>= 1; i--) { swap(array, 0, i); heapify(array, 0, i); } return array; } private void buildHeap(int[] array) { int n = array.length;// 数组中元素的个数 for (inti = n / 2 - 1; i>= 0; i--) heapify(array, i, n); } private void heapify(int[] A, intidx, int max) { int left = 2 * idx + 1;// 左孩子的下标(如果存在的话) int right = 2 * idx + 2;// 左孩子的下标(如果存在的话) int largest = 0;// 寻找3个节点中最大值节点的下标 if (left < max && A[left] > A[idx]) largest = left; else largest = idx; if (right < max && A[right] > A[largest]) largest = right; if (largest != idx) { swap(A, largest, idx); heapify(A, largest, max); } } // 建堆函数,认为【s,m】中只有 s // 对应的关键字未满足大顶堆定义,通过调整使【s,===================================================== public static void heapAdjust(int[] array, int s, int m) { // 用0下标元素作为暂存单元 array[0] = array[s]; // 沿孩子较大的结点向下筛选 m】成为大顶堆for (int j = 2 * s; j <= m; j *= 2) { // 保证j为较大孩子结点的下标,j < m 保证 j+1 <= m ,不越界 if (j < m && array[j] < array[j + 1]) { j++; } if (!(array[0] < array[j])) { break; } // 若S位较小,应将较大孩子上移 array[s] = array[j]; // 较大孩子的值变成S位的较小值,可能引起顶堆的不平衡,故对其所在的堆进行筛选 s = j; } // 若S位较大,则值不变;否则,S位向下移动至2*s、4*s、。。。 array[s] = array[0];
正在阅读:
java中常用的七大排序算法06-20
针灸治疗腰椎间盘突出症研究进展06-02
成语故事典故01-11
成语故事“李代桃僵”11-20
四字成语故事-言过其实成语故事04-26
邯郸成语故事知识05-19
雕虫小技成语故事精选11-20
《成语故事》教学心得11-20
画蛇添足成语故事11-20
刻舟求剑成语故事11-20
- 多层物业服务方案
- (审判实务)习惯法与少数民族地区民间纠纷解决问题(孙 潋)
- 人教版新课标六年级下册语文全册教案
- 词语打卡
- photoshop实习报告
- 钢结构设计原理综合测试2
- 2014年期末练习题
- 高中数学中的逆向思维解题方法探讨
- 名师原创 全国通用2014-2015学年高二寒假作业 政治(一)Word版
- 北航《建筑结构检测鉴定与加固》在线作业三
- XX县卫生监督所工程建设项目可行性研究报告
- 小学四年级观察作文经典评语
- 浅谈110KV变电站电气一次设计-程泉焱(1)
- 安全员考试题库
- 国家电网公司变电运维管理规定(试行)
- 义务教育课程标准稿征求意见提纲
- 教学秘书面试技巧
- 钢结构工程施工组织设计
- 水利工程概论论文
- 09届九年级数学第四次模拟试卷
- 算法
- 七大
- 排序
- 常用
- java
- 医学统计选择题
- 思科第3学期第3章答案
- 《第三方物流》复习
- 吻别英文版《Take me to your heart》歌词
- 市政道路工程初步设计文件编制深度规定
- 关于印发副省长朱虹在全省高校工作座谈会上讲话的通知
- 招商部管理制度
- 发热伴血小板减少培训试题答案
- 2012年度中国调味品著名品牌企业100强数据分析解读
- 项目失败的主要风险
- 完全平方公式的几何背景专题训练试题精选附答案
- 交通违章扣分标准一览
- 研究性学习结题报告(食品安全)
- 2017-2018海淀七年级第一学期期末数学试题及参考答案
- 2013-2014北师大版七年级数学上期期中模拟
- 混凝土结构设计(下册)钢筋混凝土房屋结构课程教学大纲
- 《阿房宫赋》练习题及_答案
- 应收租金保理业务协议
- 龚飞1606+8211社会保障学期末复习提要L
- 河南农业大学2015年VFP期末考试试题(之一)