精华内容
下载资源
问答
  • 2018-08-18 03:34:37

    1. 选择排序:

    选择排序是一种很简单直观的排序方法,就是在未排序的数据中挑选出最大或者最小的元素,存放到已排序数据的末尾。

    简单的讲,就是每次都把最大或者最小的数据挑选出来,然后依次组成新的序列。

    假设有数据{1,4,6,8,3,4,0,2,14},要按照从大到小进行排序

    那么我们在第一次循环中,从第一个数据‘1’开始比较,最后挑选出最大‘14’,放到数组的第一个索引处,在第二次循环中,从第二个数据开始比较,挑选出最大的‘8’,以此类推。

    显而易见,我们每进行一次排序,对比的数据就会少一个。

     

    C语言代码实现:

    void selectSort(int anData[], int nSize)
    {
    	int i = 0;
    	int j = 0;
    	int nMax = 0;
    	int nTemp = 0;
    
    	for(i=0; i<nSize; i++)
    	{
    		nMax = i;
    		for(j=i+1; j<nSize; j++)
    		{
    			if(anData[j] > anData[nMax])
    			{
    				nMax = j;
    			}
    		}
    		//相同则省去替换的过程
    		if(nMax != i)
    		{
    			nTemp = anData[i];
    			anData[i] = anData[nMax];
    			anData[nMax] = nTemp;
    		}
    	}
    }

    优化:选择排序的优化空间不大,像代码中减少交换次数就是一种优化方法。

    时间复杂度分析:选择排序的比较次数是可计算的:n+(n-1)+(n-2)+……+1 = n(n-1)/2;

    选择排序的交换次数是0到(n-1)次,最好的情况就是已经排好序,交换0次,最差的情况是逆序,交换n-1次。

    所以选择排序的时间复杂度是O(n^2)

     

     

    2.冒泡排序

    冒泡排序就是字面上的意思,依次比较相邻的元素,如果顺序错了就进行交换,直到将最大或者最小的数据冒泡到未排序数据的最前端或者最后端,这个过程类似于一个泡泡不停晚上冒,所以叫冒泡排序

    假设有数据{1,4,6,8,3,4,0,2,14},要按照从大到小进行排序

    题目要求从大到小排序,那么我们可以选择将最小的冒泡到最后面,也可以选择将最大的冒泡到最前面,我们采用第一种方法。

    第一次循环:1,4比较,1比4小,交换;

    1,6比较,1比6小,交换;

    。。。。。。

    以此类推

    第一次循环结束后,数据应为{4,6,8,3,4,0,2,14,1}

    第二次循环就是把第二小的数据冒泡到倒数第二的位置。

     

    C语言代码实现:

    void bubbleSort(int anData[], int nLen)
    {
    	int i = 0;
    	int j = 0;
    	int nTemp = 0;
    	bool bFlag = false;
    
    	for(i=0; i<nLen-1; i++)
    	{
    		bFlag = false;
    		for(j=0; j<nLen-i-1; j++)
    		{
    			if(anData[j] < anData[j+1])
    			{
    				nTemp = anData[j];
    				anData[j] = anData[j+1];
    				anData[j+1] = nTemp;
    				bFlag = true;
    			}
    		}
    		//优化,如果Flag为false,证明这一轮没有发生数据交换,排序完成
    		if(!bFlag)
    		{
    			break;
    		}
    	}
    }

    优化:冒泡排序有一定程度的优化空间,如果冒泡排序过程中后半部分的数据本身是有序的,那么就可以及时停止以节约时间。如果不进行优化,冒牌排序花费的时间比选择排序要多,因为选择排序交换的次数比较少

    时间复杂度分析:

    最优时间复杂度,如果数列本身有序,那么只需循环比较n-1次,时间复杂度为O(n),此时交换次数为最小0

    最差时间复杂度,如果数列逆序,那么所有循环都要一次走完,时间复杂度为O(n^2),此时交换次数也达到最大,与比较次数相同,都是n(n-1)/2;

     

     

     

    更多相关内容
  • 冒泡排序 选择排序 插入排序 冒泡排序 冒泡排序(最好是O(n), 最坏O(n2)) 原理: 拿自己与上面一个比较,如果上面一个比自己小就将自己和上面一个调换位置,依次再与上面一个比较,第一轮结束后最上面那个一定是...
  • 1.冒泡排序 原理:冒泡排序广泛用于数组排序,大致原理就是从第一个数开始,通过和后面一个数相比较,将较大的往后挪,一一比较之后,将最大的放到最下面。 2.选择排序 原理:先找到整个数组里面的最小值,将其...
    1.冒泡排序
        原理:冒泡排序广泛用于数组排序,大致原理就是从第一个数开始,通过和后面一个数相比较,将较大的往后挪,一一比较之后,将最大的放到最下面。
        
    2.选择排序
       原理:先找到整个数组里面的最小值,将其和数组的第一个数值进行交换。然后在除了第一个数值之外的剩下的数组里面进行搜索,找到最小的数值,将其和整个数组的第二个数值交换。依次进行,直到最后一个数值。
       
    3.插入排序

      原理:假设第0个元素已经在正确的位置上,从第1个元素开始,依次和左边已经排好的序列进行比较,将值插入到左边合适的位置上

    package array;
    import java.util.Arrays;
    /**
     * 有1,3,2,5,0共5个数字
    请使用冒泡法从小到大排序
    请使用选择法从大到小排序
    请使用插入法从小到大排序
     * @author DELL
     *
     */
    public class ArrayThreeSort {

    public static void main(String[] args) {
    // TODO Auto-generated method stub
    int[] num={1,3,2,5,0};
    //请使用冒泡法从小到大排序
    System.out.println("排序前的数组:"+Arrays.toString(num));       //用于输出数组中的数
    int temp=0; //用于交换的临时变量
    for(int i=0;i<num.length;i++){      //用于比较的数
    for(int j=i+1;j<num.length;j++){    //与后面的数一一进行比较
    if(num[i]>num[j]){
    temp=num[i];
    num[i]=num[j];
    num[j]=temp;
    }
    }
    }
    System.out.println("冒泡排序后的数组:"+Arrays.toString(num));
    //重置数组为排序前的数
    num[0]=1;
    num[1]=3;
    num[2]=2;
    num[3]=5;
    num[4]=0;

    System.out.println("排序前的数组:"+Arrays.toString(num));


    //请使用选择法从大到小排序
    for(int i=0;i<num.length;i++){//第几个位置
    int min=i;   //定义每层循环的最小值初值下标
    for(int j=i;j<num.length;j++){  //判断最小值
    if(num[min]>num[j]){
    min=j;
    }
    //交换
    temp=num[i];
    num[i]=num[min];
    num[min]=temp;
    }

    }

    System.out.println("选择排序后的数组:"+Arrays.toString(num));


    //重置数组为排序前的数
    num[0]=1;
    num[1]=3;
    num[2]=2;
    num[3]=5;
    num[4]=0;

    System.out.println("排序前的数组:"+Arrays.toString(num));


    //请使用插入法从小到大排序
    for(int i=1;i<num.length;i++){   //循环次数
    for(int j=i;j>0;j--){    //比较元素
    if(num[j]<num[j-1]){
    temp=num[j];
    num[j]=num[j-1];
    num[j-1]=temp;
    }else{               //如果现在的数比前一个数大,由于前面的数都是有序的,所以无需再与前面的数进行比较,退出 循环
    break;
    }
    }
    }
    System.out.println("插入排序后的数组:"+Arrays.toString(num));
    }


    }


    运行结果:


    展开全文
  • 1、冒泡排序 基本原理:定义一个有n个元素的数组序列,从第一个元素开始依次比较相邻两个元素的大小;当下一个元素的值大于前一个元素的值时,将两个元素的位置进行调换;然后再和下一个元素进行比较,并且交换位置...

    1、冒泡排序

    基本原理:定义一个有n个元素的数组序列,从第一个元素开始依次比较相邻两个元素的大小;当下一个元素的值大于前一个元素的值时,将两个元素的位置进行调换;然后再和下一个元素进行比较,并且交换位置;一直重复该过程直到比较的结果是剩下一个元素位置;其中n个元素中最大的元素值最后交换到最后一位,也就是第n位。

    代码示例:

    package paixu;
     
    public class BubbleSort {
     
    public static void main(String[] args) {
    int[] array = {12,32,25,46,56,32,11,78,40,98,64};
    int temp;	//定义一个中间遍历
    for(int i=0;i<array.length;++i){	//首先遍历数组
    for(int j=array.length-1;j>i;--j){	//对数组进行内层循环
    if(array[j]<array[j-1]){	//判断当前数组元素和上一个数组元素的大小,如果当前数小于抢一个数,则进行调换换位置
    temp=array[j];	//采用第三变量进行数组元素的位置调换
    array[j]=array[j-1];
    array[j-1]=temp;
    }
    }
    }
    //输出遍历已经排序好之后的数组
    for(int i=0;i<array.length;i++){
    System.out.print(array[i]+"  ");
    }
    }
    }
    输出结果:11  12  25  32  32  40  46  56  64  78  98

     

    2、插入排序,

    基本原理:定义一个有n个元素的数组序列,初始时假设第一个元素自成一个有序的序列,其余记录为无序序列;接着从第二个元素开始,按照元素大小依次将当前处理的元素插入到其之前的有序序列中,直至最后一个记录插入到有序序列中为止。

    代码示例:

    package paixu;
     
    public class InsertsSort {
    public static void main(String[] args){
    int[] array = {7,3,19,6,30,7,20};
    if(array!=null){	//判断数组是否为空
    for(int i=1;i<array.length;i++){	//遍历数组
    int temp=array[i];	//定义第三变量temp
    int j=i;
    if(array[j-1]>array[j]){	//判断当前数组元素和上一个数组元素的大小,如果当前数小于前一个数,则进行调换换位置
    while(j>=1&&array[j-1]>array[j]){
    temp=array[j];	//采用第三变量进行数组元素的位置调换
    array[j]=array[j-1];
    array[j-1]=temp;
    j--;
    }
    }else{
    array[j]=temp;	//如果当前数大于前一个数,则位置不变
    }
    }
    for(int i=0;i<array.length;i++){	//遍历已经排序完成的数组序列,并上输出该数组序列
    System.out.print(array[i]+"  ");
    }
    }
       }
    }

    输出结果:3  6  7  7  19  20  30  

     

    3、选择排序

    基本思想:定义一个有n个元素的数组序列,首先对数组序列中的元素进行比较,得出最小的数组元素,并将该元素和数组第一个元素的位置进行交换;然后将不包括数组第一个元素以外 的元素进行第二轮的比较,得出第二轮比较出的最小值,将第二轮的最小值和数组元素的第二个元素位置进行交换;不断的重复该过程,直到进行比较的记录只有一个时为止。

    代码示例:

    package paixu;
     
    public class SelectSort1 {
     public static void main(String[] args) {
     int[] array = {1,6,2,8,0,4,9,6,3,7};	//定义数组
     int min = 0;
     int temp = 0;
     for(int i=0;i<array.length;i++){	//遍历数组
     min = i;
     for(int j=i+1;j<array.length;j++){
     if(array[min]>array[j]) //判断所取的最小数和当前数的大小
     min = j;	//记下较大数位置,再次比较,直到最大
     }
     /***如果第 i数的位置不在 i,则交换****/
     if(i!=min){
     temp = array[i];
     array[i] = array[min];
     array[min] = temp;
     }
     }
     for(int i=0;i<array.length;i++){	//遍历已经排序的数组,并输出
     System.out.print(array[i]+" ");
     }
     }
    }

    输出结果:0 1 2 3 4 6 6 7 8 9 

    展开全文
  • 选择排序与冒泡排序的联系和区别

    千次阅读 2013-10-08 11:43:56
    选择排序 每一趟从待排序的数据...冒泡排序(Bubble Sort),是一种计算机科学领域的较简单的排序算法。 它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是

    选择排序

    每一趟从待排序的 数据元素中选出最小(或最大)的一个元素,顺序放在已排好序的数列的最后,直到全部待排序的数据元素排完。   选择排序是不稳定的排序方法。

    冒泡排序

    冒泡排序(Bubble Sort),是一种 计算机科学领域的较简单的 排序算法
    它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地进行直到没有再需要交换,也就是说该数列已经排序完成。
    这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端,故名。
    由于冒泡排序简洁的特点,它通常被用来对于计算机程序设计入门的学生介绍算法的概念。
     
    
             
    void select_sort(int *a, int n)
    {
        register int i, j, min, t;
        for( i =0; i < n -1; i ++)
        {
            min = i; 
            //查找最小值
            for( j = i +1; j < n; j ++)
                if( a[min] > a[j])min = j; 
            //交换
            if( min != i)
            {
                t = a[min];
                a[min] = a[i];
                a[i] = t;
            }
        }
    }

    void bubbleSort(int arr[],int n)
    {
        int i,j,t;
         for(i=0;i<n-1;i++)
            for(j=0;j<n-i-1;j++)
                if(arr[j+1]<arr[j])
                {
                  t=arr[j+1];
                  arr[j+1]=arr[j];
                  arr[j]=t;
                 }
    }

    冒泡排序总的平均时间复杂度为O\left(n^2\right)
    n值较小时, 选择排序 比冒泡排序快。

    展开全文
  • ## 冒泡排序选择排序详解--举例-

    千次阅读 2018-11-14 19:58:17
    冒泡排序选择排序详解 我们先看一下图解,再举个按身高排队的例子,最后看一下程序,立马明了!!! 一、图解:寻找两者的区别 1、冒泡排序: 2、选择排序: 二、举例理解 比如:有四个人身高分别为:A:176cm、...
  • 选择、冒泡、插入排序法一、选择排序算法的原理二、冒泡排序算法的原理三、插入排序算法的原理四、简单总结选择、冒泡、插入排序算法 算法原理及代码实现 一、选择排序算法的原理 选择排序简单的来说就是拿第一个数...
  • 冒泡排序: 我们在初学Java数组的时候,排序就是数组必不可少的一项,排序分为很多种,这里我就先介绍我们经常遇到的冒泡排序: 何为冒泡排序: 顾名思义,将一组无规则的数,打乱顺序存放到一个数组当中,(现在...
  • ====================================================|| 欢迎讨论技术的可以相互加微信:windgs (请备注csdn+xx职业) =========================================...冒泡排序  代码实现 直接插入排序 总结 ...
  • 冒泡排序实现原理:只会操作相邻的两个数据,每次冒泡操作都会对相邻的两个元素进行比较,谁大就往后移动,直到将最大的元素排到最后面,接着再循环一趟,从头开始进行两两比较,而上一趟已经排好的那个元素就不用...
  • 1、简单排序  排序是数据处理中十分常见且核心的操作,虽说...本文简单温习下最基础的三类算法:选择冒泡,插入。  先定义个交换数组元素的函数,供排序时调用 /** * 交换数组元素 * @param arr * @...
  • 内部排序与外部排序 内部排序:只用到了电脑内存而不使用外存的排序方式 外部排序:同时动用了电脑... 稳定排序:插入排序, 冒泡排序, 归并排序 不稳定排序:选择排序, 快速排序 插入排序(内部排序) 在...
  • 9.结构体+冒泡排序

    2021-05-22 05:29:54
    Student age = 20 Student score = 50.000000 Student name = lisi ------------------------------------------------------- 【冒泡排序】 #include void sort(int *a, int len) { int i,j; for (i=0;i { for(j=0...
  • 本资源主要列举了几种常见的排序算法,包含:冒泡排序,插入排序,选择排序,快速排序,希尔排序和堆排序
  • 本文简单温习下最基础的三类算法:选择冒泡,插入。 先定义个交换数组元素的函数,供排序时调用 简单选择排序  简单选择排序是最简单直观的一种算法,基本思想为将序列分为有序序列和待排的无序序列,每一趟从...
  • **冒泡排序**,其实现方式,是在每一轮操作中从头部开始把相对较大的数组后部移动,这途中如果遇到更大的元素,那就选择更大的元素向后移动。这样能保证每一轮移动都能让最大的元素“冒泡”到数组尾部。也正是因为这...
  • 一、什么是冒泡排序冒泡排序(Bubble sort),是一种较简单的排序算法。这个算法的名字由来是因为越小的元素会经由交换慢慢“浮”到数列的顶端(升序或降序排列),就如同碳酸饮料中二氧化碳的气泡最终会上浮到...
  • 排序是数据处理中十分常见且核心的操作,虽说实际项目...本文简单温习下最基础的三类算法:选择冒泡,插入。  先定义个交换数组元素的函数,供排序时调用 /** * 交换数组元素 * @param arr * @param a ...
  • 冒泡排序是一种简单的排序算法,它重复地走访过要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复的进行直到没有在需要交换的两个元素,也就是说该数列已经排序完成。这个...
  • 排序方法:冒泡排序

    2022-05-02 18:27:12
    @[TOC]冒泡排序 一、排序:将一组数据按照固定的规则进行排列 二、冒泡排序:一种排序方式,对要进行排序的数据进行两两比较,将较大的数据放在后面,依次对所用的数据进行操作,直到所有数据按要求完成排序 三、...
  • 所谓冒泡排序,其实是一种在计算机领域里较简单的排序算法。思想就是从数组的第一个元素一个个跟在后面,再挪到相应的位置上去。本文教大家的是利用Python程序语言编写冒泡排序,下面我们一起来看看吧。为了用python...
  • 1.冒泡排序: /** * 冒泡排序: * 原理:比较两个相邻的元素,将值大的元素放在后面 * &lt;p&gt; * 第一层的循环是需要遍历的次数 * 第二层的循环是 每次都是重 新两两比较(除去之前得到的最大值),...
  • 来自:dreamcatcher-cx链接:cnblogs.com/chengxiao/p/6103002.html00 前言排序是数据处理中十分常见且核心的操作,虽说实际项目开发...
  • 利用冒泡法对一个已知数组进行排序 思路:假如需要对6个数进行排序,则需要进行5次外层循环来排序,而外层循环之内的内层循环又决定着每次循环时相邻两数的交换次数(每次循环交换次数=总数-此刻进行的外层循环数)...
  • 1.冒泡排序法 基本思想:在要排序的一组数中,对当前还未排好序的范围内的全部数,自上而下对相邻的两个数依次进行比较和调整,让较大的数往下沉,较小的往上冒。即:每当两相邻的数比较后发现它们的排序与排序...
  • 冒泡排序 时间复杂度为:O(n^2) public class BubbleSort { /** * N个数字要排序完成,总共进行N-1趟排序,每i趟的排序次数为(N-i)次,所以可以用双重循环语句,外层控制循环多少趟,内层控制每一趟的循环次数。 * ...
  • 冒泡排序: package com.allqj.examination.examination.util; /** * @Author WF * @DesCription 冒泡排序 * @Date 2019/7/14 11:33 **/ public class BubbleSort { public static void main(String[] args) {...
  • 摘要:编程语言千千万,都离不开各种排序,比如比较典型的冒泡排序、快速排序、插入排序等,当然还有为之所动容的猴子排序、睡眠排序!!!本文只讲如何使用PHP实现冒泡排序的算法!原理分析本文使用的排序数组数据...
  • 排序是算法研究中比较重要的一个部分,这里列举比较简单的三种排序算法的c++实现 1.交换函数 交换函数可以让代码看上去更加简洁 tip:在面试的时候,要求手写代码时,将一些重复的代码写成函数,还...2.冒泡排序 ...

空空如也

空空如也

1 2 3 4 5 ... 20
收藏数 10,464
精华内容 4,185
关键字:

列举选择排序,冒泡排序