常用的排序算法分为
- 交换排序 ( 冒泡排序 / 快速排序 )
- 插入排序 ( 简单插入排序 / 希尔排序 )
- 选择排序 ( 简单选择排序 / 堆排序 )
- 归并排序
- 基数排序 ( 桶排序 )
今天要说的是:选择排序
选择排序 就是 选择特定目标按照顺序放置
如下文中,您有别的见解,欢迎评论指正,深海谢过诸位灵长类
简单选择排序
工作原理:每次循环找到最小的数,放到结果数组的开头,循环到结束.或者找最大数,放到结尾 两者同理
依据深海的理解举一个简单的例子:
大家上学的时候是否还记得,站队形的时候怎么排顺序?,体育老师会把最高的同学叫出队列,另起一排,然后把次高的同学叫出队列
让他站到这个同学的边上,然后按顺序循环往复,队形就排好了,这就是选择排序
public static void select(int[] array) {
for (int i = 0; i < array.length; i++) {
//最小值将要放的下标
int min = i;
//从i下标的后一位到数组结尾 选出下一个最小值的位置
for (int j = i + 1; j < array.length; j++)
if (array[j] < array[min])
min = j;
//将最小值的下标与i位置的值交换
int temp = array[i];
array[i] = array[min];
array[min] = temp;
}
}
堆排序
堆排序是利用"堆"这种数据结构而设计的算法。
首先,说一下堆整个数据结构是什么样的。
1.堆是完全二叉树结构
2.堆排序虽然引入了堆的概念,但是没有去开销额外的内存去构建一个二叉树,他只是实现了一个"逻辑堆"
完全二叉树举例: (深海的画图水平 显而易见 ...)
然后,他实现排序的步骤是什么样的呢
第一，构建一个大顶堆;
第二，选择堆顶的元素放入数组末端(选择排序的精髓);
第三，调整大顶堆。
然后循环重复第二,第三步,最终得到有序数组
排序步骤举例:(答应我,不要吐槽我的画图水平....)
public static void Test(int[] arr) {
//构建大顶堆
for(int i = arr.length/2 - 1; i >= 0;i -- )
{
selectBig(arr,i,arr.length);
}
//将大顶堆的顶部元素和最后的元素交换后，最后重构大顶堆
for(int i = arr.length-1;i >0;i--)
{
int temp = arr[0];//选择堆顶的元素放入数组末端
arr[0] = aarr[i];
arr[i] = temp;
selectBig(arr,0,i);
}
}
//调整大顶堆
public static void selectBig(int a[],int start,int end)
{
//首先将堆顶的节点放入temp
int temp = a[start];
for(int i = start*2+1 ;i < end;i = i*2+1)//从左子树开始一直找到堆底
{
if(i+1 < end && a[i] < a[i+1] ){
i++;
}
if(a[i] > temp)//此两步选出左右子树中较大的一位，然后，替换掉自己的父节点，
//并获取替换的位置，在下一次循环中调整变换的节点
{
a[start] = a[i];
start = i;
}
else{
break;
}
}
a[start] = temp;
}
