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