三种基本排序的实现及其效率对比：冒泡排序、选择排序和插入排序

public class threetypesofbasesort {
　　// ========================== 三种基本排序的效率对比 ============================
　　public static void main(string[] args) {
　　　　threetypesofbasesort sort = new threetypesofbasesort();

　　　　// 测试百万级别的数组排序，看三种基本排序的的效率差别：
　　　　int number = 500000;
　　　　int[] array = new int[number];
　　　　int[] array1 = new int[number];
　　　　int[] array2 = new int[number];
　　　　for(int i = 0; i < array.length; i++) {
　　　　　　int temp = new random().nextint(number);
　　　　　　array[i] = temp;
　　　　　　array1[i] = temp;
　　　　　　array2[i] = temp;
　　　　}
　　　　system.out.println("数组准备完毕~");

　　　　long start1 = system.currenttimemillis();
　　　　sort.bubblesort(array);
　　　　long end1 = system.currenttimemillis();
　　　　system.out.println("bubblesort 用时：" + (end1 - start1));//5万：4157。50万：430255。100万：1644079

　　　　long start2 = system.currenttimemillis();
　　　　sort.selectionsort(array1);
　　　　long end2 = system.currenttimemillis();
　　　　system.out.println("selectsort 用时：" + (end2 - start2));//5万：727。50万：74253。100万：281276 ==》选择排序比冒泡快了5.7倍。

　　　　long start3 = system.currenttimemillis();
　　　　sort.insertionsort(array2);
　　　　long end3 = system.currenttimemillis();
　　　　system.out.println("insertionsort 用时：" + (end3 - start3));//5万：827。50万：84644。 ==》插入排序比选择排序稍慢一点。
　　}

　　// ========================== bubblesort ============================
　　/**
　　* 冒泡排序：相邻的两个数进行比较，如果是从小到大排序，则将较大的那个数放后，每次都要交换。
　　* 冒泡排序的优化思路：
　　* 　　 ① 判空；
　　* 　　 ② 元素的个数很特殊时：个数为0、1时；
　　* 　　 ③ 数组已经是有序的，或者是数组里所有元素都相同：
　　*/
　　public void bubblesort(int[] target){
　　　　if(target == null){
　　　　　　return;
　　　　}
　　　　boolean tag = true;//如果数组是有序的，则不需要再进行交换。
　　　　for(int i = 0; i < target.length -1 && tag; i++){//外层循环：控制比较的组数：（元素个数-1）次。
　　　　　　tag = false;
　　　　　　for(int j = 0; j < target.length - i - 1; j++){//内层循环：控制每组比较的次数：每组比较都从第一个元素开始比较，把每次比较时的max移到后面去，每组的比较次数=target.length-1-i。
　　　　　　　　if(target[j] > target[j + 1]){
　　　　　　　　　　int temp = target[j];
　　　　　　　　　　target[j] = target[j + 1];
　　　　　　　　　　target[j + 1] = temp;
　　　　　　　　　　tag = true;
　　　　　　　　}
　　　　　　}
　　　　}
　　}

　　// ======================= selectionsort ============================
　　/**
　　* 选择排序：
　　* 　　第一趟从n个元素的数据序列中选出关键字最小/大的元素并放在最前位置，
　　* 　　下一趟从n-1个元素中选出最小/大的元素并放在未排好序元素的最前位置。以此类推，经过n-1趟完成排序。
　　*/
　　public void selectionsort(int[] target){
　　　　if(target == null){
　　　　　　return;
　　　　}
　　　　for(int i = 0; i < target.length - 1; i++){
　　　　　　int tempindex = i;
　　　　　　for(int j = i + 1; j < target.length; j++){
　　　　　　　　if(target[tempindex] > target[j]){
　　　　　　　　　　tempindex = j;
　　　　　　　　}
　　　　　　}
　　　　int temp = target[tempindex];
　　　　target[tempindex] = target[i];
　　　　target[i] = temp;
　　　　}
　　}

　　// ===================== insertsort ====================================
　　/**
　　* 插入排序：将一个数据插入到已经排好序的有序数据中（一般默认第一个元素是有序的，比较从第二个元素开始），
　　* 从而得到一个新的、个数加一的有序数据，算法适用于少量数据的排序。
　　*/
　　public void insertionsort(int[] target){
　　　　if(target == null){
　　　　　　return;
　　　　}
　　　　//外层循环控制比较的组数；
　　　　for(int i = 0; i < target.length - 1; i++){
　　　　　　//两层循环：外层控制比较的组数；内层负责找出该组比较中，在已排好序数组之后的第一个无序的元素，并通过比较将这个无序元素插入到有序数组中。
　　　　　　for(int j = i + 1; j > 0; j--){
　　　　　　　　if(target[j - 1] > target[j]){
　　　　　　　　　　int temp = target[j];
　　　　　　　　　　target[j] = target[j - 1];
　　　　　　　　　　target[j - 1] = temp;
　　　　　　　　}else{
　　　　　　　　　　break;
　　　　　　　　}
　　　　　　}
　　　　}
　　}
}