插入排序与冒泡排序的区别

对于选择排序和冒泡排序的基本概念

（一）冒泡排序
基本思想：依次比较相邻的两个数，将小数放在前面，大数放在后面。由于在排序过程中总是小数往前放，大数往后放，相当于气泡往上升，所以称作冒泡排序。主要通过两层循环来实现。
代码实例：

   public int[] BubblingSort(int[] arr)
         {
             for (int i = 0; i < arr.Length; I++)
             {
                 for (int j = 1; j < arr.Length-i; j++)
                 {
                     if (arr[j] >arr[j - 1])
                     {
                         int temp = arr[j];
                         arr[j] = arr[j - 1];
                         arr[j - 1] = temp;
                     }
                 }
             }
             return arr;
         }

(二)插入排序

基本思想：插入排序的基本操作就是将一个数据插入到已经排好序的有序数据中,从而得到一个新的、个数加一的有序数据，是稳定的排序方法。

代码实例：

         public int[] InsertSort(int[] arr)
         {
             for (int i = 1; i < arr.Length; I++)
             {
                 int k = arr[i];
                 int j = I;
                 while (j > 0 && arr[j - 1] > k)
                 {
                     arr[j] = arr[j - 1];
                     j--;
                 }
                 arr[j] = k;
            }
             return arr;
         }

这里重点说下两种排序方法的区别

假设有这样一个数组为 int []list=new list[]{1,2,3,4}; 我们要对其进行升序排序(很显然这里已经是符合要求的升序排列).

现在假若我们用冒泡排序大概流程会是这样:

1.先将1，2进行比较无须替换然后2，3比较无须替换然后3，4比较无须替换完成第一轮冒泡比较次数为3次

2.将2，3进行比较无须替换然后3，4进行比较无须替换完成第二轮冒泡比较次数为2次

3.将3，4进行比较无须替换完成第三轮冒泡比较次数为1次

很显然我们没有移动一次数字但是却比较了6次

再来看看插入排序如何实现其详细步骤为:

1.先设定1为有序区间将2和1比较无须移动比较一次

2.此时1，2均为有序区间将3和2进行比较无须移动直接跳出while循环比较一次

3.此时1，2，3均为有序区间将4和3进行比较无须移动直接跳出while循环比较一次

很显然我们也没有移动数字但是只比较了3次

总的来说冒泡排序循环一次就确定了第0位为最小值(针对升序) 而插入排序循环一次则将有序区间增加一位

因此针对部分有序的集合来说（这里说的有序是指与我们想得到的顺序一致）插入排序效率优于冒泡排序

但是我们可以针对冒泡排序进行优化当我们循环某一次发现没有任何数字移动的时候我们就已经知道集合已经排序完成而无须再进行循环

示例代码:

   public int[] BubblingSort(int[] arr)
         {
             //集合中数字是否移动过
             bool flag = true;
             for (int i = 0; i < arr.Length; I++)
             {
                 if (flag)
                 {
                     for (int j = 1; j < arr.Length - i; j++)
                     {
                         flag = false;
                         if (arr[j] > arr[j - 1])
                         {
                             flag = true;
                             int temp = arr[j];
                             arr[j] = arr[j - 1];
                             arr[j - 1] = temp;
                         }
                     }
                 }
                 else
                 {
                     break;
                 }
             }
             return arr;
         }

此时的冒泡排序循环次数和插入排序一样均为3次

转载：http://www.cnblogs.com/yeguo/archive/2013/05/14/3078202.html

最后编辑于：2018.04.03 02:11:34