两种选择排序法

/**
 * 功能:选择排序法
 *
思想:第一次从R[0]-R[N-1]中选取最小值,与R[0]交换,第二次从R[1]-R[N-1]中选取最小值,与R[1]交换,
 *
第三次从R[2]-R[N-1]中选取最小值,与R[2]交换…第i次从R[i]-R[N-1]中选取最小值,与R[i-1]交换,
 *
第n-1次从R[n-2]-R[N-1]中选取最小值,与R[n-2]交换,总共通过n-1次,得到一个按排序码从小到大排列的
 * 有序序列。
奥门威尼人, * 作者:徐守威
 */
package com.xushouwei;

常用排序法之一 ——冒泡排序法和选择排序法,排序法冒泡选择

语言中,常用的算法有:冒泡排序、快速排序、插入排序、选择排序、希尔排序、堆排序以及归并排序等等。那么从这篇开始,我将分别总结下这几种排序法。

先交代一下,我们将要排序的数组定义为arr[N],即数组arr[]包含N个元素。

## 冒泡排序法(Bubblesort) ##

所谓排序法,就是对一组无序的序列进行有序的排序(从大到小或者从小到大),那么什么叫冒泡排序法,冒泡排序法又是怎么实现数组的有序排列呢。

冒泡排序法的具体实现方法是这样的,从数组的第一个元素`arr[0]`开始,两两比较**(`arr[n],arr[n+1]`),如果前面的数大于后面的数(`arr[n]
>
arr[n+1]`),那么交换两个元素的位置,把大的数往后移动。这样依次经过一轮比较以后,最大的数将会被交换到最后的位置(arr[n-1])。

澳门威尼斯人平台,先一起再来看看冒泡排序法是怎么排序的。
 
 
数组排序前    7    23    12    4    33    21    2    17    13    9          
 
第一轮排序    7    12    4    23    21    2    17    13    9    33    
  第二轮排序    7    4    12    21    2    17    13    9    23    
 
第三轮排序    4    7    12    2    17    13    9    21                 
  第四轮排序    4    7    2    12    13    9    17    
  第五轮排序    4    2    7    12    9    13        
  第六轮排序    2    4    7    9    12        
  第七轮排序    2    4    7    9    
  第八轮排序    2    4    7   
  第九轮排序    2    4      

可以看到,每一轮的排序,在这一轮中参与比较的元素中最大的数将会浮到最后。而冒泡排序的名字也是从这里来的

C语言实现Bubblesort:

 1      void bubblesort(int a[], int m)
 2     {
 3         int i,j;
 4         int tmp;
 5         int flag = 0;  //设定标志,如果第一次循环比较时没有发生交换,则说明数组是升序排序,不用排序,提前结束循环。
 6         for(i = 0; i < m; i++)  //外层循环控制循环次数
 7         {
 8             for(j = 0; j < m-1-i; j++)    //内层循环控制每次循环里比较的次数。
 9             {
10                 if(a[j] > a[j+1])
11                 {
12                     tmp = a[j];
13                     a[j] = a[j+1];
14                     a[j+1] = tmp;
15                     flag = 1;
16                 }
17             }
18     
19             if(0 == flag)
20             {
21                 printf("No Sort\n");
22                 break;
23             }
24             }
25     }

 ## 选择排序法(Selectionsort) ##

所谓的选择是什么意思呢,选择就是于万千花丛中择其一,在选择排序法中说的就是,每一次循环过程中,通过比较选择出你需要的**最值**。

选择排序法的过程是,通**过比较,选择出每一轮中最值元素,然后把他和这一轮中最最前面的元素交换**,所以这个算法关键是要记录每次比较的结果,即每次比较后最值位置(下标)。

先来看看选择排序的过程:

数组排序前    7    23    12    4    33    21    2    17    13    9      
第一轮循环    2    23    12    4    33    21    7    17    13    9          
第二轮循环          4      12   
23    33    21    7    17    13    9    
第三轮循环                  7     
23    33    21    12    17    13    9    
第四轮循环                           9     
33    21    12    17    13    23         
第五轮循环                                  
12    21    33    17    13    23    
第六轮循环                                          
13    33    17    21    23   
第七轮循环                                                  
17    33    21    23    
第八轮循环                                                          
21    33    22   
第九轮循环                                                              
     22    33

通过这个过程,我们可以看到,每轮循环过程中,都会找出这个最值元素,下一轮排序时就不用再考虑这个元素了。

C语言实现(Selectionsort)

 1     void selectionsort(int a[],int m)
 2     {
 3         int i,j;
 4         int k;
 5         int tmp;
 6 
 7         for(i = 0; i < m-1; i++)//控制循环次数,n个数需要n-1次循环
 8         {
 9             k = i;
10             for(j = i+1; j < m ; j++)
11             {
12                 if(a[j] < a[k])
13                     k = j;
14             }
15             //i不等于k是就证明a[i]不是最小的,
16             //i等于k时证明a[i]就是本轮比较过程中最小的值
17             if(i != k)
18             {
19                 tmp = a[i];
20                 a[i] = a[k];
21                 a[k] = tmp;
22             }
23         }
24     }

 
## 总结 ##
冒泡排序法是两两依次比较,并做交换,交换的次数多。
选择排序法是每次循环找出最值,循环结束后将最值调整到合适位置,交换的次数少。
 

——冒泡排序法和选择排序法,排序法冒泡选择
语言中,常用的算法有:冒泡排序、快速排序、插入排序、选择排序、希…

选择排序法

选择排序法与定位比较排序法相比较,比的次数没变,交换的次数减少了。

选择排序算法

public class T5 {

前言

昨天晚上匆匆忙忙的写完了冒泡排序法,在简书里没找到markdown编辑器,所以只能手敲了,今天在scdn上借用这个强大的编辑器,文章照常在简书上发表,话不多说,今天写的是选择排序法。

 

澳门威尼斯人平台 1

 /**
  * @param args
  */
 public static void main(String[] args) {
  // TODO Auto-generated method stub
  int arr1[]={1,6,0,-1,9,-100,90,10,15,-10};
  //开始排序,创建一个Select类
  Select select=new Select();
  select.sort(arr1);
  
  //输出最后结果
  for(int i=0;i<arr1.length;i++)
  {
   System.out.print(arr1[i]+” “);
  }

选择排序法

  1. 原理

选择数组中的任意一个元素A,依次跟其他的元素X比较,若A>X,则交换,否则不交换。

  1. 事例

例子:待排序的数组为{ 5,2,9,8,1}
选择第一个元素5,跟2比较,2小于5那么2跟5交换,然后拿2跟9比,不换,依次类推第一轮比较完毕,手里拿的是1,现在的顺序是1,2,9,8,5;
第二轮比较,拿2跟后面的9,8,5比较,顺序不变,顺序还是1,2,9,8,5
第三轮比较,拿9跟后面的8,5比,找到了较小的5,排序后是1,2,5,9,8
最后一轮比较,最终得到的数组是1,2,5,8,9,排序完毕

  1. 代码

/**
* 选择排序法
* @param arr–待排序的数组
* @return 排好序的数组
*/
public static int[] choiceSort(int[] arr){
for (int i=0;i<arr.length;i++){
//临时变量
int temp;
for (int j=i+1;j<arr.length;j++){
//若发现被比较的元素小于选择的元素,交换两个的值
if (arr[i]>arr[j]){
temp=arr[i];
arr[i]=arr[j];
arr[j]=temp;
}
}
}
return arr;
}

#include<stdio.h>
#define N 20
void fun(int n,int *a)
{
 int i,j,k,t;
 for(i=0;i<n-1;i++)
 {
  k=i;
  for(j=i+1;j<n;j++)//j=i+1,别写成0,该层for循环仅包含

 }

总结

理解原理后,代码都是辅助性的表达出来了

一个if语句,不包含下一个if语句
   if(a[k]>a[j])
    k=j;
  if(k!=i)//先默认a[i]为最小,每次执行内层for循环,找

}
//定义一个Select类
class Select
{
 //选择排序
 public void sort(int arr[])
 {
  //定义一个临时变量来存放交换的值
  int temp=0;
  for(int j=0;j<arr.length-1;j++)
  {
   //假设第一个数是最小的
   int min=arr[j];
   //定义最小下标
   int minIndex=j;
   for(int k=j+1;k<arr.length;k++)
   {
    if(min>arr[k])
    {
     //修改
     min=arr[k];
     minIndex=k;
    }
   }
   //但退出内循环后就找到这次的最小值
  temp=arr[j];
  arr[j]=arr[minIndex];
  arr[minIndex]=temp;
  }
 }
}

到最小的元素和a[i]交换,减少了交换次数,k相当于监视哨
  {
   t=a[k];a[k]=a[i];a[i]=t;//注意下标是i
  }
 }
}
void putmatrix(int n,int *a)
{
 int i;
 for(i=0;i<n;i++)
 {
  printf(“%4d”,a[i]);//不能是*a
  if((i+1)%10==0)
   printf(“\n”);
 }
 printf(“\n”);
}
int main()
{
 int a[N]={1010,2,86,76,56,89,400,5,6,3},n=10;
 printf(“排序前:”);//分号弄成中文啦
 putmatrix(n,a);
 printf(“排序后:”);
 fun(n,a);
 putmatrix(n,a);
 return 0;
}

 

发表评论

电子邮件地址不会被公开。 必填项已用*标注