你的位置:首页 > Java教程

[Java教程]三种简单排序算法(java实现)


一、冒泡排序

算法思想:遍历待排序的数组,每次遍历比较相邻的两个元素,如果他们的排列顺序错误就交换他们的位置,经过一趟排序后,最大的元素会浮置数组的末端。重复操                   作,直到排序完成。

示例演示:

               

算法实现:

1 for(int i=0;i<array.length-1;i++){//最多排序n-1次2       for(int j=0;j<array.length-i-1;j++){//需要交换的次数3         if(array[j]>array[j+1]){4           int temp=array[j];5           array[j]=array[j+1];6           array[j+1]=temp;7         }8       }9     }

算法时间复杂度:O(n2)      外层循环需要比较n-1次,内层循环需要比较n次。

 

二、选择排序

算法思想:重待排序的数组中选择一个最小的元素,将它与数组的第一个位置的元素交换位置。然后从剩下的元素中选择一个最小的元素,将它与第二个位置的元素交换                 位置,如果最小元素就是该位置的元素,就将它和自身交换位置,依次类推,直到排序完成。

示例演示:

               

 

算法实现:

 1 for(int i=0;i<array.length;i++){ 2       int min=i; 3       for(int j=i+1;j<array.length;j++){ 4         if(array[j]<array[min]){ 5           min=j; 6         } 7       }  8       int temp=array[min]; 9       array[min]=array[i];10       array[i]=temp;11     }

时间复杂度:O(n2)     需要n2 /2次比较和n次交换

 

 

三、插入排序

算法思想:从数组的第二个元素开始遍历,将该元素与前面的元素比较,如果该元素比前面的元素小,将该元素保存进临时变量中,依次将前面的元素后移,然后将该元                 素插入到合适的位置。每次排序完成后,索引左边的元素一定是有序的,但是还可以移动。对于倒置越少的数组,该算法的排序效率越高。

              注:倒置: 5   3   6   2   倒置的项为  5-3  5-2  3-2  6-2

示例演示:

              

 

算法实现:

for(int i=1;i<array.length;i++){      for(int j=i;j>0&&array[j]<array[j-1];j--){        int temp=array[j];        array[j]=array[j-1];        array[j-1]=temp;      }    }

时间复杂度:O(n2)       最坏情况下n/2次比较,n/2交换    最好情况N-1次比较,0次交换

 

注:菜鸟一个,有不正确的地方欢迎指正。