常见六种排序算法(java版本)
Java资料站
共 14340字,需浏览 29分钟
·
2021-05-14 12:26
点击上方蓝色字体,选择“标星公众号”
优质文章,第一时间送达
什么是排序算法的稳定性?
冒泡排序算法
最好 | 平均 | 最坏 | 辅助存储 | 稳定 |
---|---|---|---|---|
O(n) | O(n²) | O(n²) | O(1) | Y |
public static int [] maopao1(int array[]){
int t;
for(int i = 0;i <array.length;i ++){
for(int j = 0;j < array.length-i-1;j ++){
if(array[j] < array[j+1]){
t = array[j+1];
array[j+1] = array[j];
array[j] = t;
}
}
}
return array;
}
选择排序算法
最好 | 平均 | 最坏 | 辅助存储 | 稳定 |
---|---|---|---|---|
O(n²) | O(n²) | O(n²) | O(1) | N |
//选择
public static int [] selectSort(int[] array){
int t = 0;
int max = 0;
for(int i = 0; i < array.length;i ++){
max = i;
for(int j = i;j < array.length;j ++){
if(array[j] > array[max]){
max = j;
}
}
//如果i就是max,不用交换位置
if(i != max){
t = array[max];
array[max] = array[i];
array[i] = t;
}
}
return array;
}
快速排序算法
最好 | 平均 | 最坏 | 辅助存储 | 稳定 |
---|---|---|---|---|
O(nlog(n)) | O(nlog(n)) | O(n²) | O(log(2)(n)) | N |
//快速排序:分而治之的思想,一左一右两个指针,以left为基准
public static void quickSort(int left,int right,int [] arr){
//从小到大排序
int i = left;
int j = right;
//注意:i也不能等于j,当i==j说明排序完成,最后一次的左/右部分只有一个数字
if(i >= j)
return ;
//定义一个基准值
int k = arr[left];
while(i != j){
//i不能大于j
if(arr[i] <= k && i < j){
i++;
}
if(arr[j] > k && i < j){
j --;
}
if(i < j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
//i == j
if(k > arr[i]){
int temp = arr[left];
arr[left] = arr[i];
arr[i] = temp;
}
//递归
quickSort(left,i-1,arr);
quickSort(i,right,arr);
}
归并排序算法
最好 | 平均 | 最坏 | 辅助存储 | 稳定 |
---|---|---|---|---|
O(nlog(n)) | O(nlog(n)) | O(nlog(n)) | O(n) | Y |
//归并排序:先分割,再合并
//分割
public static int [] separate(int [] arr){
if(arr.length < 2){
return arr;
}
//找中位数,Math.floor(a)得到小于a的最大整数
//可能数组数量为奇数的情况下
int mid = (int)Math.floor(arr.length/2);
//分成两个
int [] left = Arrays.copyOfRange(arr,0,mid);//(左闭右开]
int [] right = Arrays.copyOfRange(arr,mid,arr.length);//因为下标从0开始,所以本来就取不到arr.length,不用减一
//递归
return merge(separate(left),separate(right));
}
//合并
public static int [] merge(int [] left,int [] right){
int [] arr = new int[left.length+right.length];
if(arr.length < 2){
//判断如果数组长度小于2,那么必定其中一个数组有值,一个无值,返回有值的即可
return left.length == 0?right:left;
}
int i=0,j=0,k=0;
while(i<left.length && j<right.length){
//把小的那个数组添加到新数组中
if(left[i] < right[j]){
arr[k++] = left[i++];
}else{
arr[k++] = right[j++];
}
}
//最后还有一个没有添加到arr新数组中,这时加上去
while(i < left.length){
arr[k++] = left[i++];
}while(j < left.length){
arr[k++] = right[j++];
}
return arr;
}
直接插入排序算法
最好 | 平均 | 最坏 | 辅助存储 | 稳定 |
---|---|---|---|---|
O(n) | O(n²) | O(n²) | O(1) | Y |
public static void insertSortAsc(int [] arr){
for(int i=1;i<arr.length;i++){
int temp=arr[i];//temp哨兵位置
int index=i-1;//index代表与哨兵比较的值的下标
//index不能小于0&&升序,把index指向的数值与哨兵作比较,如果哨兵小于index指向的元素
while(index >=0 && arr[index] > temp){
//把index指向的元素后移一位
arr[index+1] = arr[index];
index --;//index--确保从已经排好的元素中选择,从后往前扫描
}
//这时,在拍排的序列中,比哨兵大的元素都已在哨兵右边,此时把哨兵放到index+1位置上即可
arr[index+1] = temp;
}
}
希尔排序算法
最好 | 平均 | 最坏 | 辅助存储 | 稳定 |
---|---|---|---|---|
O(n) | O(n^(3/2)) | O(n^(3/2)) | O(1) | N |
public static void shellSortAsc(int[] arr){
int gap=arr.length/2;//增量,初始为数组长度一半
while(gap>=1){
for(int i=gap;i<arr.length;i++){//这里其实就是插入排序,不过把原来的i=1变成i=gap
int temp=arr[i];
int index=i-gap;
while(index>=0&&arr[index]>temp){
arr[index+gap]=arr[index];
index=index-gap;
}
arr[index+gap]=temp;
}
gap=gap/2;//增量递减
}
}
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:
https://blog.csdn.net/suo_jia_hao/article/details/116565973
锋哥最新SpringCloud分布式电商秒杀课程发布
👇👇👇
👆长按上方微信二维码 2 秒
感谢点赞支持下哈
评论