黑马程序员技术交流社区

标题: 冒泡排序、插入排序、选择排序有什么区别 [打印本页]
作者: 陈栋    时间: 2012-5-19 15:20
标题: 冒泡排序、插入排序、选择排序有什么区别
冒泡排序、插入排序、选择排序有什么区别
作者: 8161776    时间: 2012-5-19 15:28
本帖最后由 杨尧 于 2012-5-19 15:32 编辑

冒泡排序的基本概念是：依次比较相邻的两个数，将小数放在前面，大数放在后面。即在第一趟：首先比较第1个和第2个数，将小数放前，大数放后。然后比较第2个数和第3个数，将小数放前，大数放后，如此继续，直至比较最后两个数，将小数放前，大数放后。至此第一趟结束，将最大的数放到了最后。在第二趟：仍从第一对数开始比较（因为可能由于第2个数和第3个数的交换，使得第1个数不再小于第2个数），将小数放前，大数放后，一直比较到倒数第二个数（倒数第一的位置上已经是最大的），第二趟结束，在倒数第二的位置上得到一个新的最大数（其实在整个数列中是第二大的数）。如此下去，重复以上过程，直至最终完成排序。

插入排序简单说就是数组里第二个和第一个比谁小，把小的放到第一个里，大的放到第二个里，然后第二个再和第三个比，小的还是放在前，一直比到这个数组结束，这样就实现了从小到大，希望我说的够详细

选择法：这种方法提高了一点性能，这种方法类似我们人为的排序习惯：从数据中选择最小的同第一个值交换，在从剩下的部分中选择最小的与第二个交换，这样往复下去。
作者: 8161776    时间: 2012-5-19 15:29
插入排序简单说就是数组里第二个和第一个比谁小，把小的放到第一个里，大的放到第二个里，然后第二个再和第三个比，小的还是放在前，一直比到这个数组结束，这样就实现了从小到大，希望我说的够详细
作者: 任睦强    时间: 2012-5-19 15:34
冒泡排序、插入排序、选择排序的原理
插入排序的原理：始终定义第一个元素为有序的，将元素逐个插入到有序排列之中，其特点是要不断的移动数据，空出一个适当的位置，把待插入的元素放到里面去。插入排序的函数如下：
insertion_sort(int *arr,int len)
{
　　　　int i,j,tmp;
　　　　 for(i=1;i<len;i++)
　　　　 {
　　　　　　　　 j=i-1;
　　　　　　　　tmp=arr[i];
　　　　　　　　 while(j>=0&&arr[j]>tmp)
  　　　　　　　　{
　　　　　　　　　　　　arr[j+1]=arr[j];
　　　　　　　　　　　　 j--;
　　　　　　　　}
　　　　　　　　arr[j+1]=tmp;
　　　　}
}
  其中，arr为要排序的数组，len为数组的长度，j为数组下标，tmp为定义的要插入的数。可以看到，在while循环中，不断的去比较待插入的值与有序队列的值，不断的去移动数据，最后找到合适的位置，插入数据。
  
  选择排序的原理：每次在无序队列中&ldquo;选择&rdquo;出最小值，放到有序队列的最后，并从无序队列中去除该值（具体实现略有区别）。代码如下：
selection_sort(int *arr, int n)
{
　　　　int i,j,min,temp;
　　　　for(i=0;i<n-1;i++)
　　　　{
　　　　　　　　min=i;
　　　　　　　　for(j=i+1;j<n;j++)
　　　　{
　　　　　　　　if(arr[j]<arr[min])
　　　　　　　　{
　　　　　　　　　　　　min=j;
　　　　　　　　}
　　　　 }
}
  可以看出，选择排序的特点就是每次选出最小的放到有序队列最后。当然，也可以选出最大值放到有序队列的最前。
  
  冒泡排序的原理：每次在无序队列里将相邻两个数依次进行比较，将小数调换到前面，逐次比较，直至将最大的数移到最后。最将剩下的N-1个数继续比较，将次大数移至倒数第二位。依此规律，直至比较结束。冒泡代码如下：
sort(int *arr,int n)
{
　　　　int i,j,t;
　　　　for(i=0;i<n-1;i++)
　　　　{
　　　　　　　　for(j=0;j<n-1-i;j++)
　　　　　　　　{
　　　　　　　　　　　　if(arr[j]>arr[j+1])
　　　　　　　　　　　　{
　　　　　　　　　　　　　　　　t=arr[j];
　　　　　　　　　　　　　　　　arr[j]=arr[j+1];
　　　　　　　　　　　　　　　　arr[j+1]=t;
　　　　　　　　　　　　}
　　　　　　　　}
　　　　}
}
作者: 余宏    时间: 2012-5-19 15:34
1.冒泡排序的原理：
每次在无序队列里将相邻两个数依次进行比较，将小数调换到前面，逐次比较，直至将最大的数移到最后。最将剩下的N-1个数继续比较，将次大数移至倒数第二位。依此规律，直至比较结束
2.插入排序的原理：
始终定义第一个元素为有序的，将元素逐个插入到有序排列之中，其特点是要不断的移动数据，空出一个适当的位置，把待插入的元素放到里面去
3.选择排序的原理：
每次在无序队列中&ldquo;选择&rdquo;出最小值，放到有序队列的最后，并从无序队列中去除该值,只是具体实现略有区别。
作者: 包晗    时间: 2012-5-19 15:44
排学是以时间的复杂性比较的
插入.冒泡.选择的时间复杂性为O(n2)
排序各有各的特点，对空间的要求及其时间效率也不尽相同
插入排序和冒泡排序 对空间要求不高，但是时间效率却不稳定。
这3种应该属于同一类（简单排序，宏观上来讲）
作者: 付信榕    时间: 2012-5-19 17:15
冒泡排序、插入排序、选择排序的实现原理有区别，对应的效率（时间复杂度、空间复杂度）不同。插入排序、冒泡排序平均时间复杂度都是O(n^2)，最好时是O（n），而选择排序最好的时间复杂度都是O(n^2)。所以要根据数据的特点选择不同的排序方法，达到最优的效果。
作者: 于陈    时间: 2012-5-19 19:30
  1. /**
  2. * 作者：于陈
  3. * 功能：演示各种排序
  4. * 时间：2012年5月5日 19:49:34
  5. */
  6. package com.paixu;

  8. import java.util.*;

  10. public class Demo1 {

  12.         public static void main(String[] args) {
  13.                 int len = 55555;
  14.                 int arr[] = new int[len];

  16.                 for (int i = 0; i < len; i++) {
  17.                         int t = (int) (Math.random() * 10000);
  18.                         arr[i] = t;
  19.                 }
  20.                 Boo boo = new Boo();
  21.                 Calendar car = Calendar.getInstance();
  22.                 System.out.println("排序前时间：" + car.getTime());
  23.                 boo.maopaoPaixu(arr);
  24.                 car = Calendar.getInstance();
  25.                 System.out.println("排序后时间：" + car.getTime());
  26.                 System.out.println();
  27.                 car = Calendar.getInstance();
  28.                 System.out.println("排序前时间：" + car.getTime());
  29.                 Selent selent = new Selent();
  30.                 selent.selentPaixu(arr);
  31.                 car = Calendar.getInstance();
  32.                 System.out.println("排序后时间：" + car.getTime());
  33.         }

  35. }

  37. // 选择排序
  38. class Selent {
  39.         public void selentPaixu(int arr[]) {
  40.                 int temp = 0;
  41.                 for (int i = 0; i < arr.length - 1; i++) {
  42.                         int min = arr[i];
  43.                         int minIndex = i;
  44.                         for (int j = i + 1; j < arr.length; j++) {
  45.                                 if (min > arr[j]) {
  46.                                         min = arr[j];
  47.                                         minIndex = j;
  48.                                 }
  49.                         }
  50.                         temp = arr[i];
  51.                         arr[i] = arr[minIndex];
  52.                         arr[minIndex] = temp;
  53.                 }

  55.         }
  56. }

  58. // 冒泡排序
  59. class Boo {
  60.         public void maopaoPaixu(int[] arr) {
  61.                 int temp = 0;
  62.                 for (int i = 0; i < arr.length - 1; i++) {
  63.                         for (int j = 0; j < arr.length - 1 - i; j++) {
  64.                                 if (arr[j] > arr[j + 1]) {
  65.                                         temp = arr[j];
  66.                                         arr[j] = arr[j + 1];
  67.                                         arr[j + 1] = temp;
  68.                                 }
  69.                         }
  70.                 }

  72.         }
  73. }
复制代码
上个星期写的冒泡和选择排序，希望能有用
作者: 荣天    时间: 2012-5-19 20:31
冒泡排序：相邻的两个元素进行比较，如果符合条件要求
/*
* 按照排序打印数组  有小到大的排序打印
* 冒泡排序
* java定义好多排序
* 发现排序是的 交换位置是一致的  可以封装成函数
*/
package Wuyuejichu;

import java.util.Arrays;
//选择逐一排序
public class ShuzuDemo4 {
        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 tmp=arr[x];
                                        arr[x]=arr[y];
                                        arr[y]=tmp;
                                        */
                                        swap(arr,x,y);
                                }
                        }
                }
        }
        //冒泡排序
        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++){ //-x:让每一次比较元素减1    -1：避免数组越界
                                if( arr[y]<arr[y+1]){
                                         /*
                                        int tmp=arr[y];
                                        arr[y]=arr[y+1];
                                        arr[y+1]=tmp;
                                        */
                                        swap(arr,y,y+1);
                                }
                        }
                }
               
        }
        //封装函数    交换
        public  static void swap(int[] arr ,int a,int b){
                int tmp=arr[a];
                arr[a]=arr[b];
                arr[b]=tmp;
        }
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] arr={3,4,7,2,1,9,6};
        System.out.println("原数组：");
//                //比较前的打印前
                printArry(arr );
                selectSort(arr);/*
* 按照排序打印数组  有小到大的排序打印
*/
package Wuyuejichu;
public class ShuzuDemo4 {
        public static void selectSort(int[] arr){
                for(int x=0;x<arr.length-1;x++){        //arr.length-1 最后 不用进行比较
                        for(int y=x+1;y<arr.length;y++){
                                if(arr[x]>arr[y]){
                                        int tmp=arr[x];
                                        arr[x]=arr[y];   //借用第三方比较
                                        arr[y]=tmp;
                                }
                        }
                }
        }
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] arr={3,4,7,2,1,9,6};
                //比较前的打印前
                printArry(arr );
                selectSort(arr);
                //比较后的打印
                printArry(arr);
        }
        //打印数组
        public static void printArry(int[] arr){
                System.out.print("{");
                for(int x=0;x<arr.length;x++){
                        if(x!=arr.length-1)
                                System.out.print(arr[x]+",");
                        else
                                System.out.println(arr[x]+"}");
                }
        }
}
//                //比较后的打印
                System.out.println("选择注意排序后的数组");
                printArry(arr);
                System.out.println("JAVA中自定义的Arrays.sort升序排序：");
                Arrays.sort(arr);   //JAVA中定义好的升序排序，开发中用到
                printArry(arr);
                System.out.println("冒泡排序：");
                bubblesort(arr);
                printArry(arr );
        }
        //打印数组
        public static void printArry(int[] arr){
                System.out.print("{");
                for(int x=0;x<arr.length;x++){
                        if(x!=arr.length-1)
                                System.out.print(arr[x]+",");
                        else
                                System.out.println(arr[x]+"}");
                }
        }
}  
/*
* 按照排序打印数组  有小到大的排序打印
*/
package Wuyuejichu;
public class ShuzuDemo4 {
        public static void selectSort(int[] arr){
                for(int x=0;x<arr.length-1;x++){        //arr.length-1 最后 不用进行比较
                        for(int y=x+1;y<arr.length;y++){
                                if(arr[x]>arr[y]){
                                        int tmp=arr[x];
                                        arr[x]=arr[y];   //借用第三方比较
                                        arr[y]=tmp;
                                }
                        }
                }
        }
        public static void main(String[] args) {
                // TODO Auto-generated method stub
                int[] arr={3,4,7,2,1,9,6};
                //比较前的打印前
                printArry(arr );
                selectSort(arr);
                //比较后的打印
                printArry(arr);
        }
        //打印数组
        public static void printArry(int[] arr){
                System.out.print("{");
                for(int x=0;x<arr.length;x++){
                        if(x!=arr.length-1)
                                System.out.print(arr[x]+",");
                        else
                                System.out.println(arr[x]+"}");
                }
        }
}
作者: 彩虹    时间: 2012-5-19 23:00
本帖最后由 万章云 于 2012-5-19 23:02 编辑

       选择排序的思想是：将整个记录分为两个区，有序序列和无序序列，其中有序序列区中的记录按关键字非递减有序排列，每完成一趟排序，从无序序列中选出一个最小的元素插入到有序序列中，它是稳定的排序
算法为：
SelectionSort(int [] arr)
{
　　　　int i,j,k;
　　　　for(i=0;i<arr.length;i++)
　　　　{
　　　　　　k=i;
　　　　　　for(j=i+1;j<arr.length;j++)
　　　　      {
　　　　　　　　if(arr[j]<arr[k])
　　　　　　　　{
　　　　　　　　　　k=j;
　　　　　　　　}
　　　　       }
               }
}

       插入排序的思想是：将初始的无序序列区中的记录插入到有序序列区中，是有序序列区长度增1，从第二个记录开始，每一趟排序都要选定一个哨兵，第一趟因为是从第二个记录开始的，所以选第二个记录为哨兵，第二趟以第三个为哨兵，以此类推，直到记录按有序完成排序为止，插入排序也是稳定的排序
算法为：
InsertionSort(int [] arr)
{
　　　　int i,j;
　　　　 for(i=2;i<arr.length;i++)
　　　　 {　　　
                      if(arr<arr[i-1]){　　　　
                           arr[0]=arr;
　　　　　　　  for(j=i-1;arr[0]<arr[j];j--)
                          arr[j+1]=arr[j];
                          arr[j+1]=arr[0];　　　　　　　　
　　　　}
}

       冒泡排序的思想是：通过对无序序列区中的记录进行相邻记录关键字间的比较和记录位置的交换实现关键字较小的记录向“一头"漂移，而关键字较大的向”另一头“下沉，从而达到记录按关键字非递减的顺序有序排列，它是稳定的排序
算法为：
BubbleSort(int [] arr)
{
　　　　int i,j,k;
　　　　for(i=0;i<arr.length;i++)
　　　　{
　　　　　　for(j=0;j<arr.length-i-1;j++)
　　　　　　{
　　　　　　　　if(arr[j]>arr[j+1])
　　　　　　　　{
　　　　　　　　　　k=arr[j];
　　　　　　   　　　arr[j]=arr[j+1];
　　　　　　　　　　arr[j+1]=k;
　　　　　　　　}
　　　　　　}
　　　　}
}







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