经典排序算法——冒泡和选择排序法
基本思想是,对相邻的元素进行两两比较,顺序相反则进行交换,这样,每一趟会将最小或最大的元素放到顶端,最终达到完全有序,首先看个动图:
我们要清楚一点,冒泡排序是相邻元素的两两比较,再看下图是否会清晰些:
输入的数据为:10 30 40 33 5 78 11 100 23 66
第一次排序,从第一个数10依次比较,若10比后者小,则进行交换,当比较到5时,10比5大,所以10就停在第四个位置,再用5去比较,后面的数都比5大,所以5就排到最后了
同理,第二次排序,仍然从第一个数30开始比较,分别跟40,33交换了顺序,比到10的时候,30比10大,所以30就停在了第三个位置,再用10去比较,10只比5大,所以排在了倒数第二个位置
依次10次比较后,得到最终排序结果
Java实现冒泡排序代码如下,代码实现过程,用一个临时变量来做中间值,从而实现交换:
- package maopaopaixu;
- import java.util.Scanner; //使用到了scanner函数,所以需要导包
- public class maopao {
- public static void main(String[] args) {
- int i,
- j,
- k,
- temp; //声明变量
- int a[] = new int[10]; //定义一个数组,长度为10
- Scanner sc = new Scanner(System. in ); //创建一个输入对象
- System.out.println("请输入十个正整数:"); //输出
- for (i = 0; i < a.length; i++) { //使用for循环把数据存储到数组中
- a[i] = sc.nextInt();
- }
- for (j = 0; j < a.length; j++) { //外层循环控制排序趟数
- for (k = 0; k < a.length - 1; k++) { //内层循环控制每一趟排序多少次
- if (a[k] < a[k + 1]) { //取相邻两个数进行比较
- temp = a[k + 1]; //条件为真,进行交换位置,采用temp临时变量
- a[k + 1] = a[k];
- a[k] = temp;
- }
- }
- }
- for (i = 0; i < a.length; i++) { //使用for循环,把排序的结果依次显示
- System.out.print(a[i] + "\t");
- }
- }
- }
加上一些代码可以看的更清晰,如下所示:
- package maopaopaixu;
- import java.util.Scanner; //使用到了scanner函数,所以需要导包
- public class maopao {
- public static void main(String[] args) {
- int i,
- j,
- k,
- temp; //声明变量
- int a[] = new int[10]; //定义一个数组,长度为10
- Scanner sc = new Scanner(System. in ); //创建一个输入对象
- System.out.println("请输入十个正整数:"); //输出
- for (i = 0; i < a.length; i++) { //使用for循环把数据存储到数组中
- a[i] = sc.nextInt();
- }
- for (j = 0; j < a.length; j++) { //外层循环控制排序趟数
- for (k = 0; k < a.length - 1; k++) { //内层循环控制每一趟排序多少次
- if (a[k] < a[k + 1]) { //取相邻两个数进行比较
- temp = a[k + 1]; //条件为真,进行交换位置,采用temp临时变量
- a[k + 1] = a[k];
- a[k] = temp;
- }
- }
- System.out.print("第" + (j + 1) + "次排序为:"); //输出
- for (i = 0; i < a.length; i++) { //在外层循环中看每一次排序后的结果
- System.out.print(a[i] + "\t");
- }
- System.out.println(); //换行
- }
- System.out.print("最终排序为:"); //输出
- for (i = 0; i < a.length; i++) { //使用for循环,把排序的结果依次显示
- System.out.print(a[i] + "\t");
- }
- }
- }
基本思想为每一趟从待排序的数据元素中选择最小(或最大)的一个元素作为首元素,直到所有元素排完为止,简单选择排序是不稳定排序。
在算法实现时,每一趟确定最小(或最大)元素的时候会通过不断地比较交换来使得首位置为当前最小(或最大),交换是个比较耗时的操作。其实我们很容易发现,在还未完全确定当前最小(或最大)元素之前,这些交换都是无意义的。我们可以通过设置一个变量min(或max),每一次比较仅存储较小(或较大)元素的数组下标,当轮循环结束之后,那这个变量存储的就是当前最小(或最大)元素的下标,此时再执行交换操作即可。
简言之,就是找到找到一组数中的最大与最小交换顺序
先看一张结果图,一看就明白:
输入的数据为:10, 35 67 88 99 100 2 34 77 55,我们可以从上图看出,进行第一次排序时,只是最大值100与最小值10交换了位置,其他数的位置都没有变化
同理,第二次就是该组数中的第二大的数99与第二小的数35交换位置,其他数位置不变
十次下来,就实现了排序功能
Java实现选择排序代码如下:
- package xuanzepaixu;
- import java.util.Scanner; //使用到了scanner函数,所以需要导包
- /*选择比较是找出最大的与第一个交换*/
- public class xuanze {
- public static void main(String[] args) {
- int i,j,k,temp,max,count=0; //声明变量
- int a[] = new int[10]; //定义一个数组,长度为10
- Scanner sc=new Scanner(System.in); //创建一个输入对象
- System.out.println("请输入十个正整数:"); //输出
- for(i=0;i<a.length;i++){ //使用for循环把数据存储到数组中
- a[i]=sc.nextInt();
- }
- for(j=0;j<a.length;j++){ //外层循环控制排序趟数
- max=a[j]; //把数组中第j个值赋给max
- count=j; //count记录下标,若if结果为假,则保持原样交换
- for(k=j;k<a.length;k++){ //内层循环控制每一趟排序多少次
- if(max<a[k]){ //假定的max值与数组依次去比较
- max=a[k]; //为真就把a[k]的值赋给max
- count=k; //count是记录数的位置
- }
- }
- temp=a[j]; //在外循环中对数据进行交换顺序
- a[j]=a[count];
- a[count]=temp;
- }
- for(i=0;i<a.length;i++){ //使用for循环,把排序的结果依次显示
- System.out.print(a[i]+"\t");
- }
- }
- }
选择排序有个地方需要注意:就是count=j,若没有这句,当出现判断条件为假时,从而会导致整个排序出错
加上显示排序次数的代码更加清楚,如下所示:
- package xuanzepaixu;
- import java.util.Scanner; //使用到了scanner函数,所以需要导包
- /*选择比较是找出最大的与第一个交换*/
- public class xuanze {
- public static void main(String[] args) {
- int i,j,k,temp,max,count=0; //声明变量
- int a[] = new int[10]; //定义一个数组,长度为10
- Scanner sc=new Scanner(System.in); //创建一个输入对象
- System.out.println("请输入十个正整数:"); //输出
- for(i=0;i<a.length;i++){ //使用for循环把数据存储到数组中
- a[i]=sc.nextInt();
- }
- for(j=0;j<a.length;j++){ //外层循环控制排序趟数
- max=a[j]; //把数组中第j个值赋给max
- count=j; //count记录下标,若if结果为假,则保持原样交换
- for(k=j;k<a.length;k++){ //内层循环控制每一趟排序多少次
- if(max<a[k]){ //假定的max值与数组依次去比较
- max=a[k]; //为真就把a[k]的值赋给max
- count=k; //count是记录数的位置
- }
- }
- temp=a[j]; //在外循环中对数据进行交换顺序
- a[j]=a[count];
- a[count]=temp;
- System.out.print("第"+(j+1)+"次排序为:"); //输出
- for(i=0;i<a.length;i++){ //在外层循环中看每一次排序后的结果
- System.out.print(a[i]+"\t");
- }
- System.out.println(); //换行
- }
- System.out.print("最后排序为:"); //输出
- for(i=0;i<a.length;i++){ //使用for循环,把排序的结果依次显示
- System.out.print(a[i]+"\t");
- }
- }
- }
实现原理都一样,只是代码写法稍有不同罢了,所以就直接上代码了:
- #include<stdio.h>
- main()
- {
- int i,j,temp;
- int a[10];
- printf("请输入十个数:");
- for(i=0;i<10;i++)
- {
- scanf("%d",&a[i]);
- }
- for(i=0;i<10;i++)
- {
- for(j=0;j<9-i;j++)
- {
- if(a[j]>a[j+1])
- {
- temp=a[j];
- a[j]=a[j+1];
- a[j+1]=temp;
- }
- }
- }
- for(i=0;i<10;i++)
- {
- printf("a[%d]=%d\n",i,a[i]);
- }
- }
- #include < stdio.h >
- main() {
- int a[5],
- b,
- i,
- j,
- max,
- temp,
- count = 0;
- printf("请输入五个数:");
- for (i = 0; i < 5; i++) {
- scanf("%d", &a[i]);
- }
- for (i = 0; i < 4; i++) {
- count = i;
- for (j = 0; j < 4 - i; j++) {
- max = a[j];
- if (max < a[j + 1]) {
- max = a[j + 1];
- b = j + 1;
- temp = a[j];
- a[j] = a[j + 1];
- a[j + 1] = temp;
- }
- }
- }
- for (i = 0; i < 5; i++) {
- printf("%d\n", a[i]);
- }
- printf("最大值为:%d", max);
- }
来源: http://www.cnblogs.com/hong-fithing/p/7615907.html