黑马程序员技术交流社区

标题: 冒泡排序和选择排序小谈 [打印本页]

作者: 后知后觉4778 时间: 2015-12-23 21:52
标题: 冒泡排序和选择排序小谈
首先排序的对用对象是数组，可以是整型数组，也可以是字符数组，甚至可以是字符串数组，这里以int数组为例，假设定义数组int  a[6] = {23,78,34,89,12,45}，排序无外乎就是遍历数组元素，比较元素，交换元素。很多人感觉冒泡排序和选择排序是一样的，其实不然，我在这先写一下思想，然后比照代码可以更好的理解
冒泡排序的思想是：
               在第1趟遍历中，依次比较相邻的两个数组元素（如a[0]和a[1]，a[1]和a[2]，a[2]和a[3]，a[3]和a[4]………）让相邻两个元素中较大的值放在下标较大的位置，如：若a[0]>a[1],则交换两个元素，让较大的值放在a[1],否则不交换，若a[1]>a[2],则交换两个元素，让较大的值放在a[2]，交换后a[2]和a[3]重复上述操作，让a[2]和a[3]中较大的值放到a[3]，到此a[3]中存放的是a[0],a[1]，a[2]和a[3]中的最大值，然后继续a[3]和a[4]，a[4]和a[5]，第一趟结束后，数组中的最大值已经移动到a[5];即较大的数沉底，较小的数上浮，所以叫冒泡排序
               然后进行第2趟遍历，从a[1到a[4],因为在第1趟中已经确定了最大值，并且放到了a[5],所以不用在比较a[5]了，第2趟结束后，把次大值放到了a[4]中。
               第3趟：遍历a[0]，a[1]，a[2]，a[3]，然后确定其中的最大值放到a[3]中，同理
         第4趟：确定a[0]，a[1]，a[2]中的最大值放到a[2]中。
         第5趟：确定a[0]，a[1]中的最大值放到a[1]中，这样剩下的a[0]自然是6个数中的最大值，至此排序
         结束，共遍历数组5趟，第i趟遍历前6-i个元素，确定6-i个元素的最大值，交换到a[6-i-1].
         代码如下：

/*
   冒泡排序：
         冒泡排序的实现方式大体上有两种:大数下沉和小数上浮，本例实现方法时小数上浮
         1，和选择排序一样比较n-1趟，每一趟遍历前n-i个元素，找出最小的元素放到下标为n-i-1的位置
         2，比较是相邻两个元素比价，让比较小得元素移动到两个元素下标大的地方，这样每一趟结束，都是当前无序数的最小值
   */

/*
   选择排序和冒泡排序的区别：
      1，选择排序是某个数依次和其他没有序的人依次比较，冒泡的每一趟都是相邻的两个数比较
   */

# include <stdio.h>
int main()
{
      void sort(int array[],int length);
      void sort2(int array[],int length);
      int a[10]={12,23,34,45,56,67,78,89,90,100};
      //sort(a,10);
      sort2(a,10);
      for(int i=0;i<10;i++)
         printf("%d ",a[i]);
      printf("\n");
      return 0;
}
void sort(int array[],int length)
{
      int i,j,temp;
      for(i=0;i<length-1;i++)
         //
         for(j=0;j<length-i-1;j++)
            if(array[j]<array[j+1]) // 小数上浮
            {
                  temp = array[j];
                  array[j] = array[j+1];
                  array[j+1] = temp;
            }

}
void sort2(int array[],int length)
{
      int i,j,temp;
      for(i=0;i<length-1;i++)
         //
         for(j=length-i-1;j>0;j--)
            if(array[j] > array[j-1]) // 大数下沉
            {
                  temp = array[j];
                  array[j] = array[j-1];
                  array[j-1] = temp;
            }

}

选择排序的思想是：
在第1趟遍历中，让第一个元素即a[0],依次与数组的其他元素（a[1]，a[2]，a[3]，a[4]，a[5]）比较，若发现有元素比a[0]小，则立即交换，让较小的元素和a[0],这样第1趟结束后，a[0]存放的就是数组的最小值。

第2趟：因为已经确定了a[0]是数组6个元素的最小值，所以从a[1]开始往后遍历，确定a[1]，a[2]，a[3]，a[4]，a[5]中的最小值，然后放到a[1]中
第3趟：同理，遍历a[2]，a[3]，a[4]，a[5]，确定其中的最小值放到a[2]中。
第4趟：同理，遍历a[3]，a[4]，a[5]，确定其中的最小值放到a[3]中。
第5趟：同理，遍历a[4]，a[5]，确定其中的最小值放到a[4]中，自然剩下的肯定是数组元素的最大值了，不用在参与比较
同样，进过5趟比较后，数组元素已经有序，并且是由大到小，实现代码如下：
void sort2(int array[],int length)
{
      int i,j,k,temp;
      for(i=0;i<length-1;i++)
      {
         for(j=i+1;j<length;j++)
            if(array[j]>array[i])
            {
                  temp = array[i];
                  array[i] = array[j];
                  array[j] = temp;
            }
      }
}

改进的选择排序算法：若上述两个排序方法已经掌握，我再给大家说一个改进的选择排序算法：

void selectSort2(int array[],int length)
{
      int i,j,k,temp; //定义用于交换的变量temp
      for(i=0;i<length-1;i++)
      {
         k = i;//记录当前乱序的最大值的下标
         for(j=i+1;j<length;j++)
            if(array[j]>array[i])
                  k = j;//发现数据比最大值大，更新下标
         if(i!=k) // 若i!=k，说明假定的最大值很真实的最大值下标不一样，交换，若一样就不用交换了
         {
            temp = array[i];
            array[i] = array[k];
            array[k] = temp;
         }
      }
}
这种方式不像上述选择排序一样，一发现比较小的值就交换，而是额外定义一个变量，存储当前趟遍历元素的最小值的下标，在一趟中每次若发现较小的值，则更新下标变量为较小值的下标，然后在一趟遍历结束的时候，把下标变量记录的元素与第i个元素交换。这样的话可以减少交换的次数，在一定程度上降低了算法的复杂度。

作者: song0619 时间: 2015-12-24 09:21
很好，很透彻

作者: holmesconan 时间: 2015-12-24 09:42
楼主我正好在学这里

作者: 15931110616 时间: 2015-12-24 13:21
很好我正学到这里

作者: tangtang. 时间: 2015-12-24 15:40
看看看看

作者: 木叶 时间: 2015-12-24 20:21
很好，顶一个

作者: 后知后觉4778 时间: 2015-12-24 22:34

木叶发表于 2015-12-24 20:21
很好，顶一个

谢谢相互交流{:2_36:}

作者: 后知后觉4778 时间: 2015-12-24 22:38

holmesconan 发表于 2015-12-24 09:42
楼主我正好在学这里

安卓还是IOS 可以交流一下

作者: holmesconan 时间: 2015-12-24 22:53

后知后觉4778 发表于 2015-12-24 22:38
安卓还是IOS 可以交流一下

iOS 呀~~~

作者: HHE_johnson 时间: 2015-12-25 21:24
你的这个改正算法思想是好的，但是你的代码实现不了呢

作者: 后知后觉4778 时间: 2015-12-25 22:30

HHE_johnson 发表于 2015-12-25 21:24
你的这个改正算法思想是好的，但是你的代码实现不了呢

是的代码复制错了看看这个

void sort(int array[],int length)
{
int i,j,k,temp;
for(i=0;i<length-1;i++)
{
k = i;
for(j=i+1;j<length;j++)
if(array[j]>array[k])
k = j;
if(i!=k)
{
temp = array[i];
array[i] = array[k];
array[k] = temp;
}
}
}

复制代码

作者: HHE_johnson 时间: 2015-12-26 19:59

后知后觉4778 发表于 2015-12-25 22:30
是的代码复制错了看看这个

赞，这位兄弟对排序法理解得很透彻了！

作者: yolande 时间: 2015-12-26 20:26
你还可以去了解一下优化，用哨兵

作者: 精诚 时间: 2015-12-27 11:05
正需要那，谢谢

作者: zll464928406 时间: 2015-12-28 11:29
表示必须得练习才行啊

作者: 不土不木008 时间: 2015-12-29 00:11
楼主6666,分析透彻

作者: zf147 时间: 2015-12-29 23:24
很好我正学到这里

作者: 一步步往上爬 时间: 2016-1-21 19:01
不赖很详细有解释有代码不赖

作者: chensc 时间: 2016-1-22 22:28
学习学习！

作者: youngrivers 时间: 2016-1-22 22:39
感觉老师讲这个也老讲不清楚

作者: 水丹青 时间: 2016-1-25 21:59
还可以的 .

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

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