java常用的7大排序算法汇总-阿里云开发者社区

开发者社区> 朱培> 正文

java常用的7大排序算法汇总

简介: 刚才看到一篇不错的文章,对于提高自己的算法还是很有帮助的,我记得我大二学数据结构的时候学过,貌似有点忘记了,嘿嘿,现在转过来复习一下。 插入排序的基本思想是在遍历数组的过程中,假设在序号 i 之前的元素即 [0..i-1] 都已经排好序,本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位,为元素 x “腾位置”
+关注继续查看

刚才看到一篇不错的文章,对于提高自己的算法还是很有帮助的,我记得我大二学数据结构的时候学过,貌似有点忘记了,嘿嘿,现在转过来复习一下。



插入排序的基本思想是在遍历数组的过程中,假设在序号 i 之前的元素即 [0..i-1] 都已经排好序,本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位,为元素 x “腾位置”,最后将 k 对应的元素值赋为 x ,一般情况下,插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)。


1.插入排序算法


插入排序的基本思想是在遍历数组的过程中,假设在序号 i 之前的元素即 [0..i-1] 都已经排好序,本趟需要找到 i 对应的元素 x 的正确位置 k ,并且在寻找这个位置 k 的过程中逐个将比较过的元素往后移一位,为元素 x “腾位置”,最后将 k 对应的元素值赋为 x ,一般情况下,插入排序的时间复杂度和空间复杂度分别为 O(n2 ) 和 O(1)。

/** 
* @param int[] 未排序数组 
* @return int[] 排完序数组 
*/ 
 
public int[] sortInsert(int[] array){ 
for(int i=1;i<array.length;i++){ 
int temp = array[i]; 
int j; 
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) 。

/** 
* @param int[] 未排序数组 
* @return int[] 排完序数组 
*/ 
 
public int[] sortSelect(int[] arr){ 
for (int i = 0; i < arr.length; i++) { 
int miniPost = i; 
for (int m = i + 1; m < arr.length; m++) { 
if (arr[m] < arr[miniPost]) { 
miniPost = m; 
} 
} 
 
if (arr[i] > arr[miniPost]) { 
int temp; 
temp = arr[i]; 
arr[i] = arr[miniPost]; 
arr[miniPost] = temp; 
} 
} 
return arr; 
} 



3.冒泡排序算法


冒泡排序是將比較大的數字沉在最下面,较小的浮在上面

/** 
* @param int[] 未排序数组 
* @return int[] 排完序数组 
*/ 
 
public int[] sortBubble(int[] array){ 
int temp; 
// 第一层循环:表明比较的次数, 比如 length 个元素,比较次数为 length-1 次(肯定不需和自己比) 
for(int i=0;i<array.length-1;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, 这使才真正的找到了枢轴,分水岭. 返回这个位置,分水岭左边和右边的序列,分别再来递归。
/** 
* @param int[] 未排序数组 
* @return int[] 排完序数组 
*/ 
 
public int[] sortQuick(int[] array){ 
return quickSort(array, 0, array.length-1); 
} 
 
private int[] quickSort(int[] arr, int low, int heigh) { 
if (low < heigh) { 
int division = partition(arr, low, heigh); 
quickSort(arr, low, division - 1); 
quickSort(arr, division + 1, heigh); 
} 
return arr; 
} 
 
// 分水岭,基位,左边的都比这个位置小,右边的都大 
private int partition(int[] arr, int low, int heigh) { 
int base = arr[low]; //用子表的第一个记录做枢轴(分水岭)记录 
while (low < heigh) { //从表的两端交替向中间扫描 
while (low < heigh && arr[heigh] >= base) { 
heigh--; 
} 
// base 赋值给 当前 heigh 位,base 挪到(互换)到了这里,heigh位右边的都比base大 
swap(arr, heigh, low); 
while (low < heigh && arr[low] <= base) { 
low++; 
} 
// 遇到左边比base值大的了,换位置 
swap(arr, heigh, 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.合并排序算法


归并排序采用的是递归来实现,属于“分而治之”,将目标数组从中间一分为二,之后分别对这两个数组进行排序,排序完毕之后再将排好序的两个数组“归并”到一起,归并排序最重要的也就是这个“归并”的过程,归并的过程中需要额外的跟需要归并的两个数组长度一致的空间

/** 
* @param int[] 未排序数组 
* @return int[] 排完序数组 
*/ 
private int[] 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); 
} 
return nums; 
} 
 
private void merge(int[] nums, int low, int mid, int high) { 
int[] temp = new int[high - low + 1]; 
int i = low;// 左指针 
int j = mid + 1;// 右指针 
int k = 0; 
// 把较小的数先移到新数组中 
while (i <= mid && j <= high) { 
if (nums[i] < nums[j]) { 
temp[k++] = nums[i++]; 
} else { 
temp[k++] = nums[j++]; 
} 
} 
// 把左边剩余的数移入数组 
while (i <= mid) { 
temp[k++] = nums[i++]; 
} 
// 把右边边剩余的数移入数组 
while (j <= high) { 
temp[k++] = nums[j++]; 
} 
// 把新数组中的数覆盖nums数组 
for (int k2 = 0; k2 < temp.length; k2++) { 
nums[k2 + low] = temp[k2]; 
} 
} 
 
public int[] sortMerge(int[] array) { 
return sort(array, 0, array.length - 1); 
} 


6.希尔排序算法


希尔排序的诞生是由于插入排序在处理大规模数组的时候会遇到需要移动太多元素的问题。希尔排序的思想是将一个大的数组“分而治之”,划分为若干个小的数组,以 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 ,即对整个数组进行插入排序,此时的数组已经基本上快排好序了,所以需要移动的元素会很小很小,解决了插入排序在处理大规模数组时较多移动次数的问题,


希尔排序是插入排序的改进版,在数据量大的时候对效率的提升帮助很大,数据量小的时候建议直接使用插入排序就好了。


/** 
* @param int[] 未排序数组 
* @return int[] 排完序数组 
*/ 
 
public int[] sortShell(int[] array) { 
// 取增量 
int step = array.length / 2; 
while (step >= 1) { 
for (int i = step; i < array.length; i++) { 
int temp = array[i]; 
int j = 0; 
// 跟插入排序的区别就在这里 
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)与尾节点(最后一个节点,比较小)位置互换,剩下最后的尾节点,现在最大,其余的,从第一个元素开始到尾节点前一位,构造大顶堆递归。
/** 
* @param int[] 未排序数组 
* @return int[] 排完序数组 
*/ 
public int[] sortHeap(int[] array) { 
buildHeap(array);// 构建堆 
int n = array.length; 
int i = 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 (int i = n / 2 - 1; i >= 0; i--) 
heapify(array, i, n); 
} 
 
private void heapify(int[] A, int idx, 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,m】成为大顶堆===================================================== 
public static void heapAdjust(int[] array, int s, int m) { 
// 用0下标元素作为暂存单元 
array[0] = array[s]; 
// 沿孩子较大的结点向下筛选 
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];



版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
常用算法和复杂度总结
一、常用算法和复杂度 算法 名称 复杂度 备注 快速排序 QuickSort(A,p,r) 最坏:O(n2) 平均:O(nlog n) 均衡划分:O(nlog n) ...
3159 0
Java面试通关要点汇总集
基础篇 基本功 面向对象的特征 final, finally, finalize 的区别 int 和 Integer 有什么区别 重载和重写的区别 抽象类和接口有什么区别 说说反射的用途及实现 说说自定义注解的场景及实现 HTTP 请求的 GET 与 ...
1306 0
Java面试通关要点汇总集
框架篇SpringBeanFactory 和 ApplicationContext 有什么区别Spring Bean 的生命周期Spring IOC 如何实现说说 Spring AOPSpring AOP 实现原理动态代理...
1291 0
javascript 一个关于时间排序的算法(一个页面多个倒计时排序)
上周要做一个活动页面 秒杀列表页 需要一个时间的算法排序 自己琢磨了半天想了各种算法也没搞出来,后来问了下一个后台的php同学 他写了个算法给我看了下 ,刚开始看的时候觉得这就是个纯算法,不能转化成页面的dom效果,可是再看了两遍发现可以 于是我就改了改 实现了 不禁感叹 确实蛮赞的 于是就博一客;...
850 0
学生党如何拿到阿里技术offer: 《阿里巴巴常考面试题及汇总答案(Java方向)上篇》
今天为大家分享不是前辈们的面试经历而是面试题目,这篇题目可谓良心之作,只不过原文链接已经失效,在这里还是谢谢原作者。
50913 0
Java数组排序基础算法,二维数组,排序时间计算,随机数产生
import java.util.Arrays; //包含Arrays import java.util.Random; public class HelloWorld { public static void main(String[] args){ // Scanner s = new Scanner(System.
853 0
+关注
朱培
CSDN博客专家,大数据与云计算领域,常年活跃于Github、CSDN、开源中国等开源社区。
122
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
《2021云上架构与运维峰会演讲合集》
立即下载
《零基础CSS入门教程》
立即下载
《零基础HTML入门教程》
立即下载