龙空技术网

「排序算法」(1)——冒泡排序、选择排序

IT编程 128

前言:

而今同学们对“数据结构起泡排序算法c语言实现”大概比较关注,大家都想要剖析一些“数据结构起泡排序算法c语言实现”的相关资讯。那么小编同时在网摘上搜集了一些有关“数据结构起泡排序算法c语言实现””的相关文章,希望大家能喜欢,咱们一起来了解一下吧!

做了这么久的练习题

相信伙伴们的基础已经可以了

那么我们开始进入下一阶段

排序算法

冒泡排序

这个冒泡排序的原理就像水里的鱼吐泡泡一样,起初是小一点的泡泡,然后越来越大,最后的泡泡是最大的~

算法描述:

1)设待排序序列中的记录的数为 n

2)一般地,第 i 趟起泡排序从1 到 n-i+1

3)依次比较相邻两个记录的关键字,如果发生逆序,则交换之。

4)其结果是这 n-i+1 个记录中,关键字最大的记录被交换到第 n-i+1 的位置上,最多作 n-1 趟。

上面的文字看起来晕晕的~

我们还是来看下图吧~~

我们有7个数需要排列,第一趟排列的时候我们需要比较7次,把最大的数 9 排在最后一位。当第二趟排列的时候,我们只需要比较6次把整个数列中第二大的数排在第六位就可以了,因为最后一位整个数列中最大的数,就不需要比较了~以此类推~n个数排列的时候,我们排六趟就可以了~

代码:

public class sortMethods { public static void main(String[] args) { int a[]={8,3,2,5,9,3,6}; bubbleSort(a);  Print(a); } //冒泡排序 private static void bubbleSort(int[] a) { for(int i=0;i<a.length-1;i++){ for(int j=0;j<a.length-i-1;j++){ if (a[j]>a[j+1]) { swap(a,j,j+1); } } }  } private static void swap(int[]a,int i,int j) { int temp; temp = a[i]; a[i] = a[j]; a[j] = temp;  } private static void Print(int[] a) { for(int num:a){ System.out.print(num+"\t"); } System.out.println();  }}

冒泡算法是可以优化的呦,我们一起看一下优化后的冒泡排序算法:

//优化后的冒泡排序 private static void bubbleSort2(int[] a) { for(int i=0;i<a.length-1;i++){ boolean flag = true; for(int j=0;j<a.length-i-1;j++){ if (a[j]>a[j+1]) { swap(a,j,j+1); flag = false; } } if (flag) { break; } }  }

算法评价

1)时间复杂度:T(n)=O(n²)

a.最好的情况(正序)

比较次数:n-1(优化后)

移动次数:0

b.最坏的情况(逆序)

比较次数:

移动次数:

2)空间复杂度:S(n)=O(1)

选择排序

算法描述

1)首先通过n-1次比较,从n个数中找出最小的, 将它与第一个数交换——第一趟选择排序,结果最小的数被安置在第一个元素位置上。

2)再通过n-2次比较,从剩余的n-1个数中找出关键字次小的记录,将它与第二个数交换——第二趟选择排序。

3)重复上述过程,共经过n-1趟排序后,排序结束。

额~

还是看下图吧~

第一趟找到整个数列中最小的那个数,把它和整个数列的第一位交换位置,然后找到第二小的数,把它和第二位书交换位置~以此类推~

代码:

//选择排序 private static void selectSort(int[] a) { for(int i=0;i<a.length-1;i++){ int k=i; for(int j=i+1;j<a.length;j++){ if (a[j]<a[k]) { k=j;  } } if (k!=i) { swap(a, i, k); } } }

算法评价

1)时间复杂度:T(n)=O(n²)

a.比较次数:

b.移动次数:

最好情况: 0

最坏情况: 3(n-1)

2)空间复杂度:S(n)=O(1)

伙伴们准备好了吗?

新一轮的学习要开始了呦~

嘿嘿~

我是萌新娜娜

立志做一个不翻车的老司机

学习Java的路上请多多指教

标签: #数据结构起泡排序算法c语言实现 #起泡排序算法代码