黑马程序员技术交流社区

标题: 关于选择排序和冒泡排序的效率比较 [打印本页]

---

作者: 熊猫不烧香    时间: 2016-3-5 23:13
标题: 关于选择排序和冒泡排序的效率比较
   冒泡排序与比较排序以需要多少次比较来比较效率
  以int[] arr = {5,2,19,61,1,22,6,55,28};9个元素为例子
单纯用数学比较的话,
冒泡排序的比较次数是(1+8)*8/2=36
选择排序的比较次数也是1+8)*8/2=36
然后在两种排序里加计数器
class BubbleSort {
        public static void main(String[] args) {
                int[] arr = {5,2,19,61,1,22,6,55,28};
                bubbleSort(arr);
                ArrErg(arr);       
        }

        public static void bubbleSort(int[] arr) {
                int count = 0;
                for (int i = 0; i < arr.length-1 ; i++) {
                        for (int j = 0 ; j < arr.length -1-i;j ++ ) {
                                count ++;
                                if (arr[j] > arr[j+1]) {
                                        int temp = 0;
                                        temp = arr[j];
                                        arr[j] = arr[j+1];
                                        arr[j+1] = temp;
                                }
                        }
                }
                System.out.println(count);
        }

        public static void ArrErg(int[] arr) {
                for (int i = 0;i < arr.length ;i ++ ) {
                        System.out.print(arr[i] + " ");
                }       
        }
}


class SelectSort {
        public static void main(String[] args) {
                int[] arr = {5,2,19,61,1,22,6,55,28};
                selectSort(arr);
                ArrErg(arr);       
        }

        public static void selectSort(int[] arr) {
                int count = 0;
                for (int i = 0; i < arr.length-1 ; i++) {
                        for (int j = i ; j < arr.length -1;j ++ ) {
                                count ++;
                                if (arr[i] > arr[j]) {
                                        int temp = 0;
                                        temp = arr[i];
                                        arr[i] = arr[j];
                                        arr[j] = temp;
                                }
                        }
                }
                System.out.println(count);
        }

        public static void ArrErg(int[] arr) {
                for (int i = 0;i < arr.length ;i ++ ) {
                        System.out.print(arr[i] + " ");
                }       
        }
}
得到的count打印次数均是36

---

欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)

黑马程序员IT技术论坛 X3.2