|
知识星球
0.排序算法预备知识 （1）如何评判算法的稳定性？
? 如果相等的2个元素，在排序前后的相对位置保持不变，那么这是稳定的排序算法
对自定义对象进行排序时，稳定性会影响最终的排序效果
（2）什么是原地算法
何为原地算法？
(1)不依赖额外的资源或者依赖少数的额外资源，仅依靠输出来覆盖输入
(2)空间复杂度为 (1) 的.
冒泡排序就属于原地算法，在本数组内进行复杂度为O(1)的交换
1.冒泡排序 （1）冒泡排序原理
? 冒泡排序也叫做起泡排序
? 执行流程（升序为例）
(1)从头开始比较每一对相邻元素，如果第1个比第2个大，就交换它们的位置
? 执行完一轮后，最末尾那个元素就是最大的元素
(2) 忽略 ① 中曾经找到的最大元素，重复执行步骤 ①，直到全部元素有序
注意:每次循环结束后，下一趟 的终止条件就会提前，因为上一趟已经确定了一个最大值的位置
冒泡排序初级实现
public static void main1(Integer[] date) {
for(int end=date.length-1;end>0;end--) {
for (int i = 1; i <= end; i++) {
if (date[i - 1] > date[i]) {
int temp = date[i - 1];
date[i - 1] = date[i];
date[i] = temp;
}
}
}
System.out.println(Arrays.toString(date));
}
（3）改进的冒泡算法1
上面我们提到了冒泡算法的初级实现，但是这种写法存在一种很明显的缺点，就是如果数组一开始就是完全有序的，冒泡算法还是会按照逻辑，执行完所有比较趟数进行排序操作。显然这是没有必要的如果数组一开始就是完全有序，那么我们再第一躺遍历中就可以得知大数据排序，此时没有必要在进行后序操作了。
所以我们很容易想到用一个标记遍历记录是否完全有序，如果有序则直接终止排序
public static void main2(Integer[] arr) {
for(int end=arr.length-1;end>0;end--)
{
boolean flag=true;
for (int begin = 1; begin <=end ; begin++) {
if (arr[begin - 1] > arr[begin]) {
int tmp = arr[begin - 1];
arr[begin - 1] = arr[begin];
arr[begin] = tmp;
flag = false;
}
}
if(flag){
break;
}
}
System.out.println(Arrays.toString(arr));
}
我们随机生成一个元素数量10000的随机数组，利用时间测试工具，对他们的时间效率进行比较。
结果发现对比效果并不是像我们想像中的那么明显，好像时间也差不了多少（再比较次数很多的情况下）？
那是因为这种改进技巧对于完全有序 的数组最为明显，而我们这里是生成随机数组进行测试，所以效果不是很明显，而且数组一开始就是完全有序的数组的概率是很小的。这就引入了另一种改进方式。
（4）改进的冒泡算法2
对于局部有序的数组，我们没有必要每次都比较到最后一个元素。
我们可以标记最后一次进行交换的位置，然后在下一次交换时提前截至到这个位置。比如说下面这种情况：
后面是数据元素已经有序了没有必要再进行的最后了。
那么有人问了：局部有序的情况出现的概率就大吗？
事实上局部有序的情况一定会出现，因为冒泡排序每一趟都会将最大的移动的最后，经过一定趟数后尾部一定会出现局部有序。
public static void main3(Integer[] arr) {
for(int end=arr.length-1;end>0;end--)
{
int sortIndex=1;
for (int begin = 1; begin <=end ; begin++) {
if (arr[begin - 1] > arr[begin]) {
int tmp = arr[begin - 1];
arr[begin - 1] = arr[begin];
arr[begin] = tmp;
sortIndex=begin;
}
}
end=sortIndex;
}
System.out.println(Arrays.toString(arr));
}
这种写法既规避了完全有序的情况，又优化了局部有序的情况。
（3）稳定性分析
冒泡排序是一种稳定性算法。
2.选择排序 （1）选择排序原理
执行流程
(1) 从序列中找出最大的那个元素，然后与最末尾的元素交换位置
? 执行完一轮后，最末尾的那个元素就是最大的元素
(2) 忽略 ① 中曾经找到的最大元素，重复执行步骤 ①
static void selectSorting(Integer [] date){
for(int end=date.length-1;end>0;end--)
{
int maxIndex=0;
for (int begin = 1; begin <=end ; begin++) {
if(date[begin]>=date[maxIndex]){
maxIndex=begin;
}
}
int temp=date[maxIndex];
date[maxIndex]=date[end];
date[end]=temp;
}
System.out.println(Arrays.toString(date));
}
（2）选择排序的优化思路
每次将最大值和末尾元素进行进行交换，我们很容易想到之前讲到的最大堆，如果将选择排序的思路用最大堆实现，则直接将堆顶元素反复和末尾元素交换。这就引入到我们的堆排序。
3.堆排序 （1）堆排序原理
? 堆排序可以认为是对选择排序的一种优化
? 执行流程
① 对序列进行原地建堆（heapify）
(如果对批量建堆还不熟悉的话可以看我往期的文章 ??二叉堆)
② 重复执行以下操作，直到堆的元素数量为 1
? 交换堆顶元素与尾元素
? 堆的元素数量减 1
? 对 0 位置进行 1 次 siftDown 操作
（2）代码实现
（1）抽取公共成员为sort.java
package 排序;
import toString.RadixSort;
import tools.Integers;
import java.text.DecimalFormat;
import java.util.Arrays;
public abstract class Sort<E extends Comparable<E>> implements Comparable<Sort<E>>{
protected E [] array;
protected int swapCount;
protected int comCount;
private long times;
private DecimalFormat fmt = new DecimalFormat("#.00");
public void sort(E[] array){
if(array==null||array.length<2)
{
return;
}
this.array=array;
long begin =System.currentTimeMillis();
sort();
times=System.currentTimeMillis()-begin;
}
public abstract void sort();
protected int com(int v1,int v2){
comCount++;
return array[v1].compareTo(array[v2]);
}
protected int com(E v1,E v2)
{
comCount++;
return v1.compareTo(v2);
}
@Override
public int compareTo(Sort o) {
int result=(int)(times-o.times);
if(result!=0)return result;
result=comCount-o.comCount;
if(result!=0)return result;
return swapCount-o.swapCount;
}
protected void swap(int k1, int k2)
{
E temp=array[k1];
array[k1]=array[k2];
array[k2]=temp;
swapCount++;
}
@Override
public String toString() {
String timeStr = "耗时：" + (times / 1000.0) + "s(" + times + "ms)";
String compareCountStr = "比较：" + numberString(comCount);
String swapCountStr = "交换：" + numberString(swapCount);
String stableStr = "稳定性：" + isStable();
return "【" + getClass().getSimpleName() + "】\n"
+ stableStr + " \t"
+ timeStr + " \t"
+ compareCountStr + "\t "
+ swapCountStr + "\n"
+ "------------------------------------------------------------------";
}
private String numberString(int number) {
if (number < 10000) return "" + number;
if (number < 100000000) return fmt.format(number / 10000.0) + "万";
return fmt.format(number / 100000000.0) + "亿";
}
private boolean isStable() {
Student[] students = new Student[20];
for (int i = 0; i < students.length; i++) {
students[i] = new Student(i * 10, 10);
}
sort((E[]) students);
for (int i = 1; i < students.length; i++) {
int score = students[i].score;
int prevScore = students[i - 1].score;
if (score != prevScore + 10) return false;
}
return true;
}
}
（2）堆排序的实现
package 排序;
public class heapSort<E extends Comparable<E>> extends Sort<E>{
private int heapSize;
private void shiftDown(int index)
{
E element=array[index];
int half=heapSize>>1;
while(index<half){
int childIndex=(index<<1)+1;
E child=array[childIndex];
int rightIndex=childIndex+1;
if(rightIndex<heapSize&&com(rightIndex,childIndex)>0){
child=array[rightIndex];
childIndex=rightIndex;
}
if(com(element,child)>0)break;
array[index]=child;
index=childIndex;
}
array[index]=element;
}
@Override
public void sort() {
heapSize=array.length;
int lastIndex=(heapSize>>1)-1;
for(int i=lastIndex;i>=0;i--)
{
shiftDown(i);
}
while(heapSize>1)
{
swap(0,--heapSize);
shiftDown(0);
}
}
}
（编辑：上海站长网）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
