第一次写博客，不对的地方欢迎指正
以下的测试时间只是在本人的电脑上直接运行的，只是简单的对比，并不是标准的时间，可能涉及到后台程序的影响
冒泡排序：时间复杂度O（n*n），可以从前向后，也可以从后向前进行排序，从后向前（自我感觉还是从后向前好，冒泡不就是向上冒），把最后一个和倒数第二个进行性比较，如果比第一个小就进行交换，这样小的数就换到了倒数第二个，倒数第二个再和倒数第三个进行比较，小再进行交换，直至最小的数被放到了第一个，之后再从后向前进行比较，直至换到第二个位置，以此类推，剩下一个数结束比较。（这个名字起的很形象）以下是自己用10000个随机数进行测试，时间只记录排序时间！
package demo_sort;
/**
* 普通的冒泡排序：就像一个个泡向上漂，小的数字与前面的数字挨个进行比较，如果小于前面的就换位置
*/
import java.util.Random;
public class MaoPao {
public static void main(String[] args) {
Random r=new Random();
int array[]=new int[10000];
for(int i=0;i<10000;i++){
array[i]=r.nextInt(10000);
}
int lenth=array.length;
long begin=System.currentTimeMillis();
for(int i=0;i<lenth;i++){
for(int j=lenth-1;j>i;j--){
if(array[j-1]>array[j]){
int temp;
temp=array[j-1];
array[j-1]=array[j];
array[j]=temp;
}
}
}
long end=System.currentTimeMillis();
System.out.println(end-begin+"ms");
// for(int as:array){
// System.out.println(as+" ");
// }
}
}
通过多次运行得到的时间基本上维持在630ms左右
优化冒泡排序：设置一个标记，如果执行到某个位置标记重新赋值，下次执行判断标记是否符合条件符合执行循环交换（对于已经有排好的可以优化很多时间）
同样是10000个随机数
对于以上排好序的数组不加优化110ms，加了优化时间大幅价绍1ms
时间维持在700ms左右
同样是10000个随机数
package demo_sort;
/**
* 优化的冒泡排序：如果给定的数组中已经有按照顺序排列的数字，不必要进行多次循环比较
* 不加优化：110多ms
* 加优化：1ms
*/
import java.util.Random;
public class MaoPaoTest {
public static void main(String[] args) {
Random r=new Random();
int array[]=new int[10000];
for(int i=0;i<10000;i++){
array[i]=i;
}
int lenth=array.length;
int flag=1;
long begin=System.currentTimeMillis();
for(int i=0;i<lenth&&flag==1;i++){
flag=0;
for(int j=lenth-1;j>i;j--){
if(array[j-1]>array[j]){
int temp=array[j-1];
array[j-1]=array[j];
array[j]=temp;
flag=1;
}
}
}
long end=System.currentTimeMillis();
System.out.println(end-begin);
}
}
对于以上排好序的数组不加优化110ms，加了优化时间大幅价绍1ms
选择排序：选择排序顾名思义，选择出来进行排序，最开始先遍历一遍数组，选择出来最小的值放在数组第一个位置，之后再对第二个元素之后的元素进行遍历，选择出来最小的值放在这个子无序序列的第一位，也就是数组的第二个元素，这样前两个数就排完了，以此类推，复杂度O（n*n）
package demo_sort;
/**
* 选择排序算法
*/
import java.util.Random;
public class SelectSort {
public static void main(String[] args) {
// int array[]=new int[]{9,6,3,2,8,7};
Random r=new Random();
int array[]=new int[10000];
for(int i=0;i<10000;i++){
array[i]=r.nextInt(10000);
}
int lenth=array.length;
long begin=System.currentTimeMillis();
for(int i=0;i<lenth;i++){
for(int j=i+1;j<lenth;j++){
if(array[i]>array[j]){
int temp=array[i];
array[i]=array[j];
array[j]=temp;
}
}
}
long end=System.currentTimeMillis();
System.out.println(end-begin+"ms");
// for(int a:array){
// System.out.println(a);
// }
}
}
时间维持在700ms左右
插入排序：插入排序复杂度也是O（n*n），涉及到了元素的移动。先把数组中的第一个元素看成有序数列，查找与这个有序数列相邻元素，与有序数列中的每个元素进行比较，插入到合适的位置，直至有序数列中的元素和原数组元素相等排序完成。
几次测试都会维持在200ms左右，相比以上的排序已经好不少，它是稳定排序，不改变相同元素原来的顺序。
优化的插入排序：
package demo_sort;
import java.util.Random;
public class InsertSort2 {
public static void main(String[] args) {
// int array[]=new int[]{9,1,4,3,6};
int array[]=new int[10000];
Random r=new Random();
for(int i=0;i<10000;i++){
array[i]=r.nextInt(10000);
}
long begin=System.currentTimeMillis();
for(int i=1;i<array.length;i++){
for(int j=i;j>0;j--){
if(array[j-1]>array[j]){
int temp=array[j];
array[j]=array[j-1];
array[j-1]=temp;
}
}
}
long end=System.currentTimeMillis();
System.out.println(end-begin+"ms");
// for(int a:array){
// System.out.println(a);
// }
}
}
几次测试都会维持在200ms左右，相比以上的排序已经好不少，它是稳定排序，不改变相同元素原来的顺序。
优化的插入排序：
package demo_sort;
import java.util.Random;
public class InsertSort1 {
public static void main(String[] args) {
// int array[]=new int[]{9,5,8,1,4};
int array[]=new int[10000];
Random r=new Random();
for(int i=0;i<10000;i++){
array[i]=r.nextInt(10000);
}
long begin=System.currentTimeMillis();
for(int i=1;i<array.length;i++){
int temp=array[i];
int j=i-1;
while(j>=0&&array[j]>temp){
array[j+1]=array[j];
j--;
}
if(j!=i-1){
array[j+1]=temp;
}
}
long end=System.currentTimeMillis();
System.out.println(end-begin+"ms");
// for(int a:array){
// System.out.println(a);
// }
}
}
优化后10000个元素，排序用时80ms左右，和基本的插入排序相差一半，主要相差在循环上，减少不必要的循环
快速排序：，快速排序要求选择的枢轴值两边子序列长度最好一致，快速排序的时间消耗上主要在对元素的划分上，元素数量为k的数组，共需要比较k-1次。快速排序主要在于选择基准，如果选择的基准刚好是最小的或者最大的元素，那么这时候时间复杂度最大为O(n*n)，如果刚好选择的基准就是这个无序序列的中值，时间复杂度最小为O(nlgn)，总的关键字比较次数：O(nlgn)
快速排序对于数组元素重复率高的不适用。
快速排序为社么快，这里要提到一个分治思想，分而治之，虽然用到的是递归，虽然也有最坏情况下和冒泡，选择排序相等的时间复杂度，但是，分治思想是关键，把一个大问题分成两个小问题，分别同时处理，这两个小问题再向下分，最后问题也就水落石出了，分治思想避免了做无用功，选择一个基准，大于他的数在他的右面，小于他的数在他的左面，在进行比较的时候，左面的数只在左面进行比较就可以，没有必要再去右面比较，这样节省了时间
package demo_sort;
import java.util.Random;
public class QuickSort {
public static void main(String[] args) {
Random r=new Random();
int a[]=new int[10000];
for(int i=0;i<10000;i++){
a[i]=r.nextInt(10000);
}
long begin=System.currentTimeMillis();
sort(a,0,a.length-1);
long end=System.currentTimeMillis();
System.out.println(end-begin);
// for (int i = 0; i < a.length; i++) {
// System.out.println(a[i]);
// }
}
public static void sort(int[] a, int low, int hight) {
int i, j, index;
if (low > hight) {
return;
}
i = low;
j = hight;
index = a[i];
while (i < j) {
while (i < j && a[j] >= index) {
j--;
}
if (i < j) {
a[i++] = a[j];
}
while (i < j && a[i] < index) {
i++;
}
if (i < j) {
a[j--] = a[i];
}
}
a[i] = index;
sort(a, low, i - 1);
sort(a, i + 1, hight);
}
}
几次运行的结果都会在80ms左右，这是在随机的条件下，其中有一次20ms，可见快速排序非常对得起他这个名字