黑马程序员技术交流社区

标题: 选择排序和冒泡排序如果都优化的话岂不是区别不是很明... [打印本页]
作者: BitmapFactory    时间: 2013-2-12 18:40
标题: 选择排序和冒泡排序如果都优化的话岂不是区别不是很明...
本帖最后由 张学林 于 2013-3-11 12:18 编辑

  2. <DIV> </DIV>
复制代码
  1. //选择排序

  3. public static void selectSort(int[] arr)
  4. {
  5. for(int i=0; i<arr.length-1; i++)
  6. {
  7. for(int j=i+1; j<arr.length; j++)
  8. {
  9. if(arr[i] > arr[j])
  10. {
  11. arr[i] = arr[i] ^ arr[j];
  12. arr[j] = arr[i] ^ arr[j];
  13. arr[i] = arr[i] ^ arr[j];
  14. }
  15. }
  16. }

  18. }
复制代码
  1. public class ArraySortDemo {
  2. public static void main(String[] args) {
  3. int[] arr = new int[]{7,4,3,2,88,9,6};
  4. /* printArray(arr);
  5. selectSort_1(arr);
  6. printArray(arr);*/
  7. printArray(arr);
  8. bubbleSort(arr);
  9. printArray(arr);
  10. }
  11. //选择排序，已优化
  12. public static void selectSort_1(int[] arr){
  13. int min = 0;
  14. for(int x=0;x<arr.length-1;x++){
  15. min = x;
  16. for(int y=x+1;y<arr.length;y++){
  17. if(arr[min]>arr[y]){
  18. min = y;
  19. }
  20. }
  21. int temp = arr[x];
  22. arr[x] = arr[min];
  23. arr[min] = temp;
  24. }
  25. }

  27. //冒泡排序，已优化，减少存放在堆内存中数组元素交换次数,max在每次外层循环时初始化为0
  28. public static void bubbleSort_1(int[] arr){
  29. int max;
  30. for(int x=0;x<arr.length-1;x++){
  31. max = 0;
  32. for(int y=0;y<arr.length-x-1;y++){
  33. if(arr[max]<arr[y+1]){
  34. max = y+1;
  35. }
  36. }
  37. int temp = arr[arr.length-x-1];
  38. arr[arr.length-x-1] = arr[max];
  39. arr[max] = temp;
  40. }
  41. }
复制代码
作者: BitmapFactory    时间: 2013-2-12 18:45
本帖最后由 张学林 于 2013-2-12 18:46 编辑

晕了,还不会用这帖子

  2.         //冒泡排序
  3.         
  4.         public static void bubbleSort (int[] arr)
  5.         {
  6.                 for(int i=0; i<arr.length-1; i++)
  7.                 {
  8.                         for(int j=0; j<arr.length-i-1; j++)
  9.                         {
  10.                                 if(arr[j]>arr[j+1])
  11.                                 {
  12.                                         int temp = arr[j];
  13.                                         arr[j] = arr[j+1];
  14.                                         arr[j+1] = temp;
  15.                                 }
  16.                         }
  17.                 }
  18.         }
复制代码
还有几句话露没了,如下
如果选择排序和冒泡排序都用做标记来优化的话,那两者就是都在找最大的(从小到大排)是哪个,然后放在最后面
那它们存在的意义是啥呢
作者: 杨玲    时间: 2013-2-13 12:37
选择算法的思想是在数组中选择大的(或者小的),直接放在后面(或者前面),在数组内部只有一个指针用于指向最大(或者最小)的数的前面(或者后面),这算是对直接排序算法(也就是双层循环的一种优化,已经选择过的就不再进行排序),而冒泡算法呢,它相当于是对选择算法的优化,因为它在数组内部设置了两个指针分别指向前面和后面,而不是前面或者后面最大或者最小,当然了这样也会出现一个选择中间值的问题,直接排序->选择排序->冒泡排序,这其实就是一个选择算法的进化过程.



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