排序算法

1.插入排序

public void insertArray(Integer[] in ) {

int tem =0;

    int num =0;

    int upnum =0;

    for (int i =0; i < in .length; i++) {

for (int j = i -1; j >=0; j--) {

num++;

            if ( in [j +1] < in [j]) {

tem = in [j +1]; in [j +1] = in [j]; in [j] = tem;

                upnum++;

            }else {

break;

            }

}

}

for (int i =0; i < in .length; i++) {

System.out.print( in [i]);

        if (i < in .length -1) {

System.out.print(",");

        }

}

System.out.println();

    System.out.println("插入排序循环次数:" + num);

    System.out.println("移动次数:" + upnum);

    System.out.print("\n\n\n");

}

比较两个值的大小,如果后边的值比前边的值小,将后边的值与前边的值互换,如果后边的值比前边的值大,就继续比较后边的两个值

2.选择排序

//选择排序

public void chooseArray(Integer[] in ) {

int tem =0;

    int num =0;

    int upnum =0;

    for (int i =0; i < in .length; i++) {

for (int j =0; j < in .length -1; j++) {

num++;

            if ( in [j +1] < in [j]) {

tem = in [j +1]; in [j +1] = in [j]; in [j] = tem;

                upnum++;

            }

}

}

for (int i =0; i < in .length; i++) {

System.out.print( in [i]);

        if (i < in .length -1) {

System.out.print(",");

        }

}

System.out.println();

    System.out.println("选择排序循环次数:" + num);

    System.out.println("移动次数:" + upnum);

    System.out.print("\n\n\n");

}

循环将小的值放到前边

3.冒泡排序

//冒泡排序

public void efferArray(Integer[] in ) {

int tem =0;

    int num =0;

    int upnum =0;

    for (int i =0; i < in .length; i++) {

for (int j = i; j < in .length -1; j++) {

num++;

            if ( in [j +1] < in [i]) {

tem = in [j +1]; in [j +1] = in [i]; in [i] = tem;

                upnum++;

            }

}

}

for (int i =0; i < in .length; i++) {

System.out.print( in [i]);

        if (i < in .length -1) {

System.out.print(",");

        }

}

System.out.println();

    System.out.println("冒泡排序循环次数:" + num);

    System.out.println("移动次数:" + upnum);

    System.out.print("\n\n\n");

}

冒泡排序是选择排序的升级版,能够一定限度的减少循环的次数

总结

选择排序是最原始的排序算法,运行结果不稳定,作为了解就行,循环次数为n*n次

插入排序是选择排序的改良版,利用break减少了循环的次数,运行结果稳定,循环次数为n*n~n次比较,n*n~1次插入

冒泡排序是插入排序的改良版,同时也牺牲了运行开销,运行结果稳定,循环次数为n*n~n次

快速排序是冒泡排序的升级版,但是运行结果不是很稳定,循环次数为n*n~n*log n次

归并排序(合并排序)是现在应用最广的排序算法,java1.7后Collections.sort使用的默认排序就是归并排序,运用化整为零的思想,将源集合分成若干小集合最好合并结果,运行结果稳定,循环次数为n*log n次

数学知识补充log n意思是2的几次方等于n,例如log 1=0,log 2=1,log 4=2,log 8=3

当然,还有希尔排序,堆排序在这里就不多说了

参考:https://www.cs.usfca.edu/~galles/visualization/Algorithms.html

你可能感兴趣的