黑马程序员技术交流社区
标题:
数组的选择排序和冒泡排序性能优化,望指点
[打印本页]
作者:
刘渝灵
时间:
2013-1-13 16:05
标题:
数组的选择排序和冒泡排序性能优化,望指点
本帖最后由 刘渝灵 于 2013-1-14 13:01 编辑
看了毕老师的视频,提到数组排序时,不必每次比较时都进行位置交换,可以在每次外层循环结束时再交换,可以提升效率。
本不想深究这个问题,不知道怎么回事,钻起了牛角尖,试着写了一下。既然写了,便贴出来,有什么问题,望大家指教。
public class ArraySortDemo {
public static void main(String[] args) {
int[] arr = new int[]{7,4,3,2,88,9,6};
/* printArray(arr);
selectSort_1(arr);
printArray(arr);*/
printArray(arr);
bubbleSort(arr);
printArray(arr);
}
public static void printArray(int[] arr){
System.out.print("[");
for(int i=0;i<arr.length;i++){
if(i!=(arr.length-1))
System.out.print(arr[i]+",");
else
System.out.println(arr[i]+"]");
}
}
//选择排序,未优化
public static void selectSort(int[] arr){
for(int x=0;x<arr.length-1;x++){
for(int y=x+1;y<arr.length;y++){
if(arr[x]>arr[y]){
int temp = arr[x];
arr[x] = arr[y];
arr[y] = temp;
}
}
}
}
//冒泡排序,未优化
public static void bubbleSort(int[] arr){
for(int x=0;x<arr.length-1;x++){
for(int y=0;y<arr.length-x-1;y++){
if(arr[y]<arr[y+1]){
int temp = arr[y];
arr[y] = arr[y+1];
arr[y+1] = temp;
}
}
}
}
//选择排序,已优化
public static void selectSort_1(int[] arr){
int min = 0;
for(int x=0;x<arr.length-1;x++){
min = x;
for(int y=x+1;y<arr.length;y++){
if(arr[min]>arr[y]){
min = y;
}
}
int temp = arr[x];
arr[x] = arr[min];
arr[min] = temp;
}
}
//冒泡排序,已优化,减少存放在堆内存中数组元素交换次数,max在每次外层循环时初始化为0
public static void bubbleSort_1(int[] arr){
int max;
for(int x=0;x<arr.length-1;x++){
max = 0;
for(int y=0;y<arr.length-x-1;y++){
if(arr[max]<arr[y+1]){
max = y+1;
}
}
int temp = arr[arr.length-x-1];
arr[arr.length-x-1] = arr[max];
arr[max] = temp;
}
}
}
复制代码
作者:
陈丽莉
时间:
2013-1-13 19:47
很欣赏这样老师说了一句就付诸实践的性格呢~ 赞一个~ :handshake
作者:
jonn
时间:
2013-1-13 20:00
涉及到算法与数据结构,LZ 应该知道 算法 有两个因素 空间复杂度 与 时间复杂度 ,而且之间是成正比
冒泡,还是选择或其他,总之 操作数据交换不要操作堆区的数据,堆区方的数据太多,执行时间长,效率很差,操作栈区的数据,改变栈区的指向,执行的效率更高,常见的商业化的垂直搜索引擎就是典型的例子
欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/)
黑马程序员IT技术论坛 X3.2