选料法排序,排序算法

从小到大的选拔排序 是从贰个数组中相继选出 最小数值 输出,第二小的数值输出,第三小的数值输出... ...直到最终贰个数组中最终一个数遍历完结,则 整个排序输出落成。

 

选用法排序指每便采用所要排序的数组中的最大值(由小到大排序则选取最小值)的数组成分,将那个数组成分的值与最前面未有进展排序的数组元素的值交换。以数字9、6、15、4、2为例,采纳选取法贯彻数字按从小到大进展排序,每一趟调换的依次如图8.17所示。

 图片 1

图8.17  选取法排序暗示图

从图8.17能够窥见,在首先次排序进度元帅第三个数字和微小的数字进行了岗位沟通;而第3回排序进度中,将第三个数字和剩余的数字中细小的数字进行了岗位交流;就那样类推,每趟都将下一个数字和多余的数字中型Mini小的的数字举行岗位沟通,直到将一组数字按从小到大排序。

上边通过实例来看一下什么通进程序选用选择法贯彻数组成分从小到大的排序。 

01奇数求和演习

  • A: 奇数求和演练

    • a: 标题剖判

      • 为了记录累积和的值,大家供给定义四个仓库储存累计和的变量
      • 咱们要获得到1-100限制内的数
      • 看清当前数是还是不是为奇数,是奇数,完结增加和操作
      • 加上达成后,最终显示下累加和的值
    • b: 解题步骤

      • 概念贰个用来记录累积和的变量
      • 利用for循环语句,马克down Preview Enhanced: Toggle Scroll Sync达成1-100里边各个数的拿走
      • 动用if条件语句,决断当前数是或不是是奇数,是奇数,实行加多和操作
      • 利用输出语句,打字与印刷累积和变量的值
    • c: 案例代码

        public class Test01 {
            public static void main(String[] args) {
                int sum = 0;
                for (int i = 0; i < 100; i  ) {
                    if (i%2==1) {
                        sum  = i;
                    }
                }
                System.out.println("累加和的值 "   sum);
            }
        }
    

此地介绍了:插入排序、冒泡排序、采纳排序、Hill排序

 int[] sort = new int[13] { 1, 4, 89, 34, 56, 40, 59, 60, 39, 1, 40, 90, 48 };  // 输入一个数组
            for (int i = 0; i < sort.Length; i  )
            {
                int min = sort[i];  // 初始化(以第i个数为初始值)最小值
                for (int j = i 1; j < sort.Length; j  )   // 从第i 1个开始遍历数组,与第i个数对比,找到最小值
                {
                    if (sort[j] < min)
                    {
                        int temp = sort[j];
                        sort[j] = min;
                        min = temp;
                    }     // 找到最小值赋值给min
                }
                Console.Write(min   " ");  // 输出min 值
            }
实例 利用接纳排序将学员战表举行排序

在本实例中,表明了壹个整型数组和多个整型变量,此中整型数组用于存款和储蓄客户输入的数字,而整型变量用于存款和储蓄数值最小的数组成分的数值和该因素的岗位,然后通过双层循环进行抉择法排序,最后将排好序的数组举办输出。具体代码如下:

01   #include<stdio.h>/*包含头文件*/

02  int main()                   /*主函数main*/

03  {

04           int i,j;                             /*定义变量*/

05           int a[10];

06           int iTemp;

07           int iPos;

08           printf("为数组元素赋值:n");

09           /*从键盘为数组元素赋值(成绩)*/

10           for(i=0;i<10;i  )

11           {

12                  printf("a[%d]=",i);

13                  scanf("%d", &a[i]); 

14           }

15           /*从高到低排序*/

16           for(i=0;i<9;i  )                                 /*设置外层循环为下标0~8的元素*/

17           {

18                  iTemp = a[i];                       /*设置当前元素为最大值*/

19                  iPos = i;                              /*记录元素位置*/

20                  for(j=i 1;j<10;j  )                     /*内层循环i 1到9*/

21                  {

22                         if(a[j]>iTemp)                      /*如果当前元素比最高值还高*/

23                         {

24                                iTemp = a[j];          /*重新设置最高值*/

25                                iPos = j;                /*记录元素位置*/

26                         }

27                  }

28                  /*交换两个元素值*/

29                  a[iPos] = a[i];

30                  a[i] = iTemp;

31           }

32   

33           /*输出数组*/

34           for(i=0;i<10;i  )

35           {

36                  printf("%dt",a[i]);                /*输出制表位*/

37                  if(i == 4)                             /*如果是第5个元素*/

38                         printf("n");            /*输出换行*/

39           }

40   

41           return 0;                                     /*程序结束*/

42  }

 

运营程序,呈现结果如图8.18所示。

 图片 2

图8.18  选取排序运维图

从该实例代码和平运动转结果可以见到:

(1)声雅培个整型数组a,并通过键盘为数组成分赋值。

(2)设置多少个嵌套循环,第一层循环为前9个数组元素,并在历次循环时将对应当前次数的数组成分设置为最小值(假若当前是第3次巡回,那么将数组中第1个因素(也正是下标为2的要素)设置为眼下的最小值);在第二层循环中,循环比较该因素之后的逐个数组成分,并将每便比较结实中一点都不大的数设置为最小值,在其次层循环停止时,将最小值与开头时设置为最小值的数组元素进行调换。当有着循环都做到之后,就将数组成分遵照从小到大的逐个重新排列了。

(3)循环输出数组中的成分,并在出口5个因素之后举行换行,在下一行输出前面包车型大巴5个成分。

 

本文摘自前些天科技(science and technology)出版的《零基础学C语言》,转发请申明出处!!!

02金盏银台演习成效完结

  • A: 姚女子花剑演练功效达成

    • a: 标题剖判

      • 鲜明哪些的数正是金盏银台数。水仙花数是指两个3位数(100-999里面),其每位数字立方之和优异该3位数本人。
        如153 = 111 333 555,即 3位数本身 = 百位数立方 九个人数立方 个位数立方;
      • 收获天葱范围内的具有3位数(100-999以内的每一个3位数)
      • 判断该3位数是还是不是满足姚女花数,满意,打字与印刷该3位数
    • b: 解题步骤

      • 动用for循环,获得100-999之内的各样3位数
      • 取得3位数中国百货公司位数字、十二个人数字、个位数字
      • 动用if条件语句,决断该3位数是不是满足金盏银台数,满意,使用输出语句,打字与印刷该3位数
    • c: 案例代码

       public class Test02 {
           public static void main(String[] args) {
               for (int i = 100; i < 1000; i  ) {
                   int bai = i/100;
                   int shi = i/10;
                   int ge = i;
                   if (i == bai*bai*bai   shi*shi*shi   ge*ge*ge) {
                       System.out.println(i);
                   }
               }
           }
       }           
    

1.插入排序

  

03ASCII编码表

  • A: ASCII编码表
    • a: 波兰语全称
      • American Standard Code for Information Interchange,United States正式新闻置换代码
    • b: ASCII编码表由来
      • 管理器中,全数的数据在积攒和运算时都要利用二进制数表示
      • a、b、c、d那样的五十一个假名(包蕴大写)、以至0、1等数字还也许有部分常用的符号, 在Computer中存放时也要动用二进制数来表示
      • 实际用哪些二进制数字代表哪个符号,当然种种人都能够约定自个儿的一套(那就叫编码)
      • 我们只要要想互相通讯而不变成零乱,那么大家就不能够不运用一样的编码法则,于是U.S.A.有关的口径组织就出台了ASCII编码,
        集合规定了上述常用符号用哪些二进制数来代表。
    • c: 中文编码表
      • GB2312
      • UNICODE
    • d: 字符中首要的ASCII码对应关系
      • a : 97
      • A : 65
      • 0 : 48

算法理念

插入排序使用了两层嵌套循环,各种管理待排序的笔录。每一个记录与前方已经排好序的记录体系举行比较,并将其插入到十三分的岗位。假诺数主管度为n,外层循环调控变量i由1至n-1依次推进,用于选拔当前拍卖哪条记下;里层循环调节变量j,初步值为i,并由i至1递减,与上一记录举行对照,决定将该因素插入到哪八个岗位。这里的重大观念是,当管理第i条记下时,后面i-1条记下已然是不改变的了。亟待注意的是,因为是将日前记下与邻座的上一笔录绝相比,所以循环控制变量的起头值为1(数组下标),假如为0的话,上一记下为-1,则数组越界。

于今我们观望一下第i条记下的拍卖情形:假使外层循环递进到第i条记下,设其关键码的值为X,那么此时有相当大希望有三种状态:

  1. 一旦上一记录比X大,那么就沟通它们,直到上一笔录的至关重要码比X小照旧相等甘休。
  2. 假如上一记录比X小可能相等,那么在此以前的享有记录一定是日月经天的,且都比X小,此时淡出里层循环。外层循环向前推动,管理下一条记下。

    public class SortAlgorithm {

    // 插入排序
    public static void InsertSort<T, C>(T[] array, C comparer)
        where C:IComparer<T>
    {           
        for (int i = 1; i <= array.Length - 1; i  ) {
            //Console.Write("{0}: ", i);
            int j = i;
            while (j>=1 && comparer.Compare(array[j], array[j - 1]) < 0) {
                swap(ref array[j], ref array[j-1]);
                j--;
            }
            //Console.WriteLine();
            //AlgorithmHelper.PrintArray(array);
        }
    }
    
    // 交换数组array中第i个元素和第j个元素
    private static void swap<T>(ref T x,ref T y) {
        // Console.Write("{0}<-->{1} ", x, y);
        T temp = x;
        x = y;
        y = temp;
    }
    

    }

地点Console.WriteLine()方法和AlgorithmHelper.PrintArray()方法唯有是由于测验方便,PrintArray()方法依次打字与印刷了数组的内容。swap<T>()方准则用于沟通数组中的两条记下,也对调换数实行了打字与印刷(这里笔者注释掉了,但在测验时能够撤废对它们的表明)。外层for循环调整变量i表示方今管理第i条记下。

public class AlgorithmHelper {
    // 打印数组内容
    public static void PrintArray<T>(T[] array) {
        Console.Write("   Array:");
        foreach (T item in array) {
            Console.Write(" {0}", item);
        }
        Console.WriteLine();
    }
}

// 获得Comparer,进行比较
public class ComparerFactory {
    public static IComparer<int> GetIntComparer() {
        return new IntComparer();
    }

    public class IntComparer : IComparer<int> {
        public int Compare(int x, int y) {
            return x.CompareTo(y);
        }
    }
}

地方这段代码我们创立了二个ComparerFactory类,它用于获取一个IntComparer对象,这一个目的达成了IComparer<T>接口,规定了五个int类型的关键码之间不小小的平整。假使您有自定义的花色,例如叫MyType,只供给在ComparerFactory中再加多三个类,比方叫MyTypeComparer,然后让这一个类也落到实处IComparer<T>接口,最终再加多一个格局再次回到MyTypeComparer就足以了。

输出:

static void Main(string[] args) {
    int[] array = {42,20,17,13,28,14,23,15};
    //int[] array = { 9, 8, 7, 6, 5, 4, 3, 2, 1, 0 };
    AlgorithmHelper.PrintArray(array);

    SortAlgorithm.InsertSort
        (array, ComparerFactory.GetIntComparer());
}

图片 3

 

04char类型的存款和储蓄

  • A: char类型的储存

    • a: 取值范围

      • short:占五个字节,是有暗记数据,取值范围-32768-32767
      • char: 占七个字节,是无符号数据,取值范围0-65536
    • b: 类型转变

      • char类型的多寡到场运算时要线程程int数据类型
    • c: 案例代码

        /*  ASCII编码表演示
            字符Java 数据类型,char
            整数Java 数据类型,int

            int 类型和 char 数据类型转换
            char  两个字节, int 四个字节

            char转成int类型的时候,类型自动提示,char数据类型,会查询编码表,得到整数
            int转成char类型的时候,强制转换,会查询编码表

            char存储汉字,查询Unicode编码表

            char可以和int计算,提示为int类型, 内存中两个字节
            char取值范围是0-65535, 无符号的数据类型
        */
        public class ASCIIDemo{
            public static void main(String[] args){
                char c = 'a';
                int i = c   1;
                System.out.println(i);

                int j = 90;
                char h = (char)j;
                System.out.println(h);

                System.out.println( (char)6 );

                char k = '你';
                System.out.println(k);


                char m = -1;
            }
        }   

2.冒泡排序

05输出全部希伯来语字母

  • A: 输出全部波兰语字母

    • a: 标题解析

      • 一共28个大大小小写字母,那么,能够设想循环贰十七次。在每一遍循环中,实现内定字母的大大小小写打字与印刷
      • 搜索ABCDEFG…XYZ那么些字母之间的变化规律
        经过ASCII表开采,前面包车型大巴假名比它前边的字母,ASCII值大1
        下叁个字母 = 上一个假名 1
        如: A B C D
        65 66 67 68
      • 在历次循环中打字与印刷上四个字母大小写,并点名下叁个假名
    • b: 解题步骤

      • 概念领头化大写变量,值为’A’; 开首化小写变量,值为’a’
      • 使用for循环,进行26次循环
      • 在历次循环中,打印大写字母、小写字母。
        老是打字与印刷实现后,更新大写字母值、小写字母值
    • c: 案例代码

        public class Test04 {
            public static void main(String[] args) {
                char da = 'A';
                char xiao = 'a';
                for (int i = 0; i < 26; i  ) {
                    System.out.println("大写字母 " da " ,小写字母 " xiao);
                    da  ; //更新大写字母值
                    xiao  ; //更新小写字母值
                }
            }
        }
        ```
    

算法理念

如若你从未有读书过关于算法方面包车型地铁学问,而急需统一希图七个数组排序的算法,那么很有望设计出的正是泡沫排序算法了。因为它很好精通,达成起来也很轻便。它也蕴藏两层循环,若是数主任度为n,外层循环调控变量i由0到n-2递增,那个外层循环实际不是管理有些记录,只是调节相比的趟数,由0到n-2,一共比较n-1趟。为啥n个记录只须要相比n-1趟?大家得以先看下最简便易行的八个数排序:例如4和3,大家只要比较一趟,就足以得出3、4。对于更加多的记录可以类推。

数组记录的置换由里层循环来产生,调节变量j开头值为n-1(数组下标),平素递减到1。数组记录从数组的尾声起首与周围的上多少个记下相比较,假如上一记下比当下记下的关键码大,则实行置换,直到近些日子记录的下标为1截止(此时上一记下的下标为0)。整个经过就象是二个卵泡从尾部向上升,于是这么些排序算法也就被取名称叫了冒泡排序。

我们来对它进行三个观测,按照这种排序方式,在进展完第一趟循环之后,最小的料定位于数组最最上端(下标为0);第二趟循环之后,次小的笔录位于数组第二(下标为1)的岗位;依次类推,第n-1趟循环之后,第n-1小的笔录位于数组第n-1(下标为n-2)的职位。此时没有必要再实行第n趟循环,因为最终三个一度身处数组末尾(下标为n-1)地方了。

// 泡沫排序
public static void BubbleSort<T, C>(T[] array, C comparer)
    where C : IComparer<T> 
{
    int length = array.Length;

    for (int i = 0; i <= length - 2; i  ) {
        //Console.Write("{0}: ", i   1);
        for (int j = length - 1; j >= 1; j--) {
            if (comparer.Compare(array[j], array[j - 1]) < 0) {
                swap(ref array[j], ref array[j - 1]);
            }
        }
        //Console.WriteLine();
        //AlgorithmHelper.PrintArray(array);
    }
}

0699乘法表的分析

  • A: 99乘法表的深入分析

    • a: 打字与印刷格式
      11=1
      1
      2=2 22=4
      1
      3=3 23=6 33=9

    • b: 标题深入分析
      通过观看发现,假使把11=1如此的从头到尾的经过看做一颗的话,那么打印结果就成了之类效果:

      **




      这么,便是打字与印刷9行星,每行打字与印刷星的个数与当前行数相等。
      再观察“13=3 23=6 33=9”得出它们如下的变化规律:
      每行第n次 "
      " 行号 "=" 每行第n次 * 行号
      如: 1 "" 2 "=" 12; // 相当于12=2
      2 "
      " 2 "=" 22; // 相当于22=4

    • c: 解题步骤

      • 概念叁个外层for循环,起先值从1从头,循环9次。用来决定打字与印刷的行数
      • 在外层for循环内部,定义多个for循环,初阶值从1伊始,循环次数与当下行数相等。用来成功每行打印钦命次数的乘法公式 如1*1=1
      • 在内层for循环中,完毕每行内定次数的乘法公式打字与印刷 如11=1
        System.out.print(k "
        " j "=" j*k "t");
        // 变量k代表:每行中的第n次
        // 变量j代表:行号
      • 在外循环中,当每行内定次数的乘法公式打字与印刷完结后,通过System.out.println()切换来下一行。
        那样,再一次打字与印刷乘法公式时,就在下一行输出打字与印刷了

出口演示(C#)

static void Main(string[] args) {
    int[] array = {42,20,17,13,28,14,23,15};
    AlgorithmHelper.PrintArray(array);

    SortAlgorithm.BubbleSort
        (array, ComparerFactory.GetIntComparer());
}

图片 4

 

0799乘法表的功力完毕

  • A: 99乘法表的功能完毕

    • a: 案例代码
        /*
            利用嵌套for循环,实现99乘法表示
            实现步骤:
              1. 定义外循环控制行数
              2. 内循环控制个数,个数,每次都在递增
              3. 循环中输出,乘法表的格式   1*3=3
        */
    
        public class Test05 {
            public static void main(String[] args) {
                for (int j = 1; j < 10; j  ) {
                    for (int k = 1; k <= j; k  ) {
                        System.out.print(k  "*"  j  "="  j*k  "t");
                    }
                    System.out.println();
                }
            }
        }
    
        ```
    

3.取舍排序

08落实数组的遍历

  • A: 完毕数组的遍历

    • a: 标题深入分析

      • 经过巡回,我们得以成功数组凉月素的获得,数组名[索引]
      • 观测开掘,每个数组成分之间投入了贰个逗号”,”举办分隔;何况,整个数组的左右有一部分中括号”[]”包裹数组全体因素。
    • b: 解题步骤

      • 应用输出语句完结打字与印刷 左侧的中括号”[”
      • 行使循环,输出数组成分值。输出元素值分为三种状态,如下:
        • 末段八个数组成分,加上二个右臂的中括号”]”
        • 非末了贰个数组成分,加上二个逗号”,”
    • c: 案例代码

            /*
                定义方法,实现数组的遍历
                遍历中,输出结果  [11,33,565,66,78,89]
                int[] arr = {3,4,45,7};
                结果包含字符串, [  ]  ,
                实现步骤:
                  1. 定义方法实现数组的遍历
                  2. 先打印[ 中括号
                  3. 遍历数组
                    输出数组的元素和逗号
                    判断是否遍历到了数组的最后一个元素,如果是最后一个元素,输出]中括号
            */
            public class ArrayMethodTest{
                public static void main(String[] args){
                    int[] arr = {11,44,55,33,66};
                    printArray(arr);
    
                    int[] arr2 = {22,88,99,33,66};
                    printArray(arr2);
    
                }
                /*
                   定义方法,实现功能
                   返回值: void
                   方法参数: 数组
                */
                public static void printArray(int[] arr){
                    //输出一半中括号,不要换行打印
                    System.out.print("[");
                    //数组进行遍历
                    for(int i = 0 ; i < arr.length ; i  ){
                        //判断遍历到的元素,是不是数组的最后一个元素
                        //如何判断 循环变量 到达 length-1
                        if( i == arr.length-1 ){
                            //输出数组的元素和]
                            System.out.print(arr[i] "]");
                        }else{
                        //不是数组的最后一个元素,输出数组元素和逗号
                            System.out.print(arr[i] ",");
                        }
                    }
                    System.out.println();
                }
            }
        ```
    

算法观念

选拔排序是对冒泡排序的二个创新,从下边冒泡排序的输出能够看看,在首先趟时,为了将小小的值13由数组末尾冒泡的数组下标为0的第一个职分,进行了多次换到。对于继续的每次,都会举办类似的置换。

分选排序的思路是:对于第一趟,搜索整个数组,搜索出最小的,然后放置在数组的0号地方;对于第二趟,寻觅数组的n-1个记录,找出出最小的(对于全数数组来讲则是次小的),然后放置到数组的第1号地点。在第i趟时,寻找数组的n-i 1个记录,搜索最小的记录(对于一切数组来讲则是第i小的),然后放在数组i-1的地点(注意数组以0开首)。能够看看,选择排序显然的缩减了置换的次数。

急需小心的地点是:在第i趟时,内层循环并没有需求递减到1的职位,只要循环到与i同样就能够了,因为从前的地点一定都比它小(也便是第i小)。别的里层循环是j>i,却非j>=i,那是因为i在步入循环之后就被马上保存到了lowestIndex中。

public static void SelectionSort<T, C>(T[] array, C comparer)
    where C : IComparer<T> 
{
    int length = array.Length;
    for (int i = 0; i <= length - 2; i  ) {
        Console.Write("{0}: ", i 1);
        int lowestIndex = i;        // 最小记录的数组索引
        for (int j = length - 1; j > i; j--) {
            if (comparer.Compare(array[j], array[lowestIndex]) < 0)
                lowestIndex = j;
        }
        swap(ref array[i], ref array[lowestIndex]);
        AlgorithmHelper.PrintArray(array);
    }
}

输出:

static void Main(string[] args) {
    int[] array = {42,20,17,13,28,14,23,15};
    AlgorithmHelper.PrintArray(array);

    SortAlgorithm.SelectionSort
        (array, ComparerFactory.GetIntComparer());
}

图片 5

 

 

09数组逆序原理

  • A: 数组逆序原理

  • a: 标题剖判(图解见day07_source/数组的逆序原理.JPG)

    • 通过观望开采,本标题要兑现原数组成分倒序存放操作。即原数组存储成分为{11,22,33,44},
      逆序后为原数组存款和储蓄成分变为{44,33,22,11}。
    • 经过图解开采,想做到数组成分逆序,其实就是把数组中索引为start与end的要素举办调换。
    • 历次交换后,start索引地点后移,end索引地方前移,再扩充调换
    • 直到start地点当先了end地方,沟通甘休,此时,数组成分逆序达成。
  • b: 解题步骤

    • 概念多少个目录变量start值为0,变量end值为数首席营业官度减去1(即数组最终一个因素索引)
    • 选择循环,完毕数组索引start地方成分与end地方成分值调换。
    • 在循环换过程中,每趟交换截止后,start位置后移1,end地方前移1
    • 在循环换进程中,最早判定start地点是否超越了end地方,若已超越,则跳出循环

4.Hill排序

Hill排序利用了插入排序的贰性格格来优化排序算法,插入排序的那些特性正是:当数组基本板上钉钉的时候,插入排序的频率相比高。譬如对于上边那样三个数组:

int[] array = { 1, 0, 2, 3, 5, 4, 8, 6, 7, 9 };

插入排序的出口如下:

图片 6

能够见到,即便相比较的趟数未有缩小,然则交流的次数却分明很少。Hill排序的全部主张正是先让数组基本有序,最终再接纳插入排序。具体进程如下:倘若有数组int a[] = {42,20,17,13,28,14,23,15},不失日常性,大家设其尺寸为length。

先是趟时,步长step = length/2 = 4,将数组分为4组,每组2个记录,则下标分别为(0,4)(1,5)(2,6)(3,7);转变为数值,则为{42,28}, {20,14}, {17,23}, {13,15}。然后对每一个分组举办插入排序,之后分组数值为{28,42}, {14,20}, {17,23}, {13,15},而实际的原数组的值就成为了{28,14,17,13,42,20,23,15}。这里要介怀的是分组中记录在原数组中的地点,以第3个分组{14,20}来说,它的下标是(1,5),所以这八个记录在原数组的下标分别为a[1]=14;a[5]=20。

第二趟时,步长 step = step/2 = 2,将数组分为2组,每组4个记录,则下标分别为(0,2,4,6)(1,3,5,7);调换为数值,则为{28,17,42,23}, {14,13,20,15},然后对种种分组举行插入排序,获得{17,23,28,42}{13,14,15,20}。此时数组就成了{17,13,23,14,28,15,42,20},已经基本平稳。

其三趟时,步长 step=step/2 = 1,此时一定举行二次完整的插入排序,拿到最后结果{13,14,15,17,20,23,28,42}。

10数组逆序效能完成

  • A:案例代码
        /*
           数组的逆序:
             数组中的元素,进行位置上的交换
             逆序 不等于 反向遍历
             就是数组中最远的两个索引,进行位置交换,实现数组的逆序
             使用的是数组的指针思想,就是变量,思想,可以随时变换索引
             反转 reverse
             实现步骤:
               1. 定义方法,实现数组的逆序
               2. 遍历数组
                 实现数组的最远索引换位置
                 使用临时的第三方变量
        */
        public class ArrayMethodTest_1{
            public static void main(String[] args){
                int[] arr = {3,5,7,1,0,9,-2};
                //调用数组的逆序方法
                reverse(arr);
                //看到数组的元素,遍历
                printArray(arr);
            }

            /*
               定义方法,实现数组的逆序
               返回值: 没有返回值
               参数:   数组就是参数
            */
            public static void reverse(int[] arr){
                //利用循环,实现数组遍历,遍历过程中,最远端换位
                //for的第一项,定义2个变量, 最后,两个变量   --
                for( int min = 0 , max = arr.length-1 ; min < max  ; min  ,max--){
                    //对数组中的元素,进行位置交换
                    //min索引和max索引的元素交换
                    //定义变量,保存min索引
                    int temp = arr[min];
                    //max索引上的元素,赋值给min索引
                    arr[min] =  arr[max];
                    //临时变量,保存的数据,赋值到max索引上
                    arr[max] = temp;
                }
            }
        }

算法实现(C#)

// 希尔排序
public static void ShellSort<T, C>(T[] array, C comparer)
    where C : IComparer<T> 
{
    for (int i = array.Length / 2; i >= 1; i = i / 2) {
        Console.Write("{0}: ", i);
        for (int j = 0; j < i; j  ) {
            InsertSort(array, j, i, comparer);
        }
        Console.WriteLine();
        AlgorithmHelper.PrintArray(array);
    }
}

// 用于希尔排序的插入排序
private static void InsertSort<T, C>
    (T[] array, int startIndex, int step, C comparer)
    where C : IComparer<T> 
{
    for (int i = startIndex   step; i <= array.Length - 1; i  = step) {
        int j = i;
        while(j>= step && comparer.Compare(array[j], array[j - step]) <0 ){
            swap(ref array[j], ref array[j - step]);
            j -= step;
        }
    }
}

 

注意这里插入排序InsertSort()方法的参数,startIndex是分组的起初索引,step是大幅度,能够看见,前边的插入排序只是此处step=1,startindex=0的二个特例

11选项排序原理

  • A: 选用排序原理
    • a: 标题深入分析(图解见day07_source/采用排序原理.JPG)
      • 通过旁观发掘,本标题要落成把数组成分{13,46,22,65,3}实行排序
      • 涉嫌数组排序,就要进行成分值大小的可比,通过上海体育场合开采,大家想成功排序要透过若干次的可比才能够不负任务。
      • 上图中用每圈要比较的率先个成分与该因素前边的数组成分依次比较到数组的终极贰个因素,把小的值放在第一个数组元素中,数组循环一圈后,则把最小成分值交换成了第贰个因素中。
      • 数组再循环一圈后,把第二小的成分值沟通来了第2个因素中。根据这种艺术,数组循环多圈现在,就实现了数组成分的排序。这种排序情势大家誉为选取排序。
* b: 解题步骤
    * 使用for循环(外层循环),指定数组要循环的圈数(通过图解可知,数组循环的圈数为数组长度 - 1)
    * 在每一圈中,通过for循环(内层循环)完成数组要比较的第一个元素与该元素后面的数组元素依次比较到数组的最后一个元素,把小的值放在第一个数组元素中
    * 在每一圈中,要参与比较的第一个元素由第几圈循环来决定。如上图所示
        * 进行第一圈元素比较时,要比较的第一个元素为数组第一个元素,即索引为0的元素
        * 进行第二圈元素比较时,要比较的第一个元素为数组第二个元素,即索引为1的元素
        * 依次类推,得出结论:进行第n圈元素比较时,要比较的第一个元素为数组第n个元素,即数组索引为n-1的元素

输出演示(C#)

static void Main(string[] args) {
    int[] array = {42,20,17,13,28,14,23,15};
    AlgorithmHelper.PrintArray(array);

    SortAlgorithm.ShellSort
        (array, ComparerFactory.GetIntComparer());
}

 

图片 7

 

12增选排序作用达成

A: 案例代码

        /*
          数组的排序: 一般都是升序排列,元素,小到大的排列

          两种排序的方式
             选择排序: 数组的每个元素都进行比较
             冒泡排序: 数组中相邻元素进行比较
             规则: 比较大小,位置交换
        */
        public class ArrayMethodTest_2{
            public static void main(String[] args){
                int[] arr  = {3,1,4,2,56,7,0};
                //调用选择排序方法
                //selectSort(arr);
                printArray(arr);
            }
            /*
                定义方法,实现数组的选择排序
                返回值: 没有
                参数:  数组
                实现步骤:
                  1.嵌套循环实现排序
                    外循环,控制的是一共比较了多少次
                    内循环,控制的是每次比较了多少个元素
                  2. 判断元素的大小值
                    小值,存储到小的索引
            */
            public static void selectSort(int[] arr){
                for(int i = 0 ; i < arr.length - 1; i  ){
                    //内循环,是每次都在减少,修改变量的定义
                    for(int j = i 1 ; j < arr.length ; j  ){
                        //数组的元素进行判断
                        if(arr[i] > arr[j]){
                            //数组的换位
                            int temp = arr[i];
                            arr[i] = arr[j];
                            arr[j] = temp; 
                        }
                    }
                }
            }

            /*
               定义方法,实现功能
               返回值: void
               方法参数: 数组
            */
            public static void printArray(int[] arr){
                //输出一半中括号,不要换行打印
                System.out.print("[");
                //数组进行遍历
                for(int i = 0 ; i < arr.length ; i  ){
                    //判断遍历到的元素,是不是数组的最后一个元素
                    //如何判断 循环变量 到达 length-1
                    if( i == arr.length-1 ){
                        //输出数组的元素和]
                        System.out.print(arr[i] "]");
                    }else{
                    //不是数组的最后一个元素,输出数组元素和逗号
                        System.out.print(arr[i] ",");
                    }
                }
                System.out.println();
            }
        }

13冒泡排序功效达成

  • A: 冒泡排序功效落成
    * a: 标题分析
    * 通过观望开掘,本标题要达成把数组成分{13,46,22,65,3}举办排序
    * 提到数组排序,就要开展成分值大小的可比,通过上海教室发掘,咱们想成功排序要因此多少次的可比才可以形成。
    * 上图中相邻的成分值依次比较,把大的值放后边的因素中,数组循环一圈后,则把最大成分值沟通来了最终一个要素中。
    数组再循环一圈后,把第二大的因素值调换来了尾数第一个要素中。遵照这种方法,数组循环多圈以往,
    就做到了数组成分的排序。这种排序形式大家称为冒泡排序。

  • b: 解题步骤
    * 使用for循环(外层循环),内定数组要循环的圈数(通过图解可以看到,数组循环的圈数为数首席营业官度 - 1)
    * 在每一圈中,通过for循环(内层循环)完结相邻的成分值依次相比,把大的值放前面包车型大巴成分中
    * 每圈内层循环的次数,由第几圈循环来决定。如上海体育场合所示
    * 实行第一圈成分相比较时,内层循环次数为数老董度 - 1
    * 进行第二圈成分相比时,内层循环次数为数CEO度 - 2
    * 依次类推,得出结论:举行第n圈成分相比时,内层循环次数为数主任度 - n

  • c: 案例代码

                /*
                  数组的排序: 一般都是升序排列,元素,小到大的排列
                                  两种排序的方式
                     选择排序: 数组的每个元素都进行比较
                     冒泡排序: 数组中相邻元素进行比较
                     规则: 比较大小,位置交换
                */
                public class ArrayMethodTest_2{
                    public static void main(String[] args){
                        int[] arr  = {3,1,4,2,56,7,0};
                        //调用选择排序方法
                        //selectSort(arr);
                                            //调用冒泡排序方法
                        bubbleSort(arr);
                        printArray(arr);
                    }
                    /*
                       定义方法,实现数组的冒泡排序
                       返回值: 没有
                        参数:  数组
                    */
                    public static void bubbleSort(int[] arr){
                        for(int i = 0 ; i < arr.length - 1; i  ){
                            //每次内循环的比较,从0索引开始, 每次都在递减
                            for(int j = 0 ; j < arr.length-i-1; j  ){
                                //比较的索引,是j和j 1
                                if(arr[j] > arr[j 1]){
                                    int temp = arr[j];
                                    arr[j] = arr[j 1];
                                    arr[j 1] = temp;
                                }
                            }
                        }
                    }
    
                    /*
                       定义方法,实现功能
                       返回值: void
                       方法参数: 数组
                    */
                    public static void printArray(int[] arr){
                        //输出一半中括号,不要换行打印
                        System.out.print("[");
                        //数组进行遍历
                        for(int i = 0 ; i < arr.length ; i  ){
                            //判断遍历到的元素,是不是数组的最后一个元素
                            //如何判断 循环变量 到达 length-1
                            if( i == arr.length-1 ){
                                //输出数组的元素和]
                                System.out.print(arr[i] "]");
                            }else{
                            //不是数组的最后一个元素,输出数组元素和逗号
                                System.out.print(arr[i] ",");
                            }
                        }
                        System.out.println();
                    }
                }
    

14数组的扣除查找原理

  • A: 数组的扣除查找原理(图解见day07_source/折半招来原理.JPG)

  • a: 标题深入分析

    • 通过观看开掘,本标题要促成查找钦赐数值在要素有序的数组中贮存的地方(索引),重返该岗位(索引)。
    • 大家采用数组最中间地方的成分值与要寻找的钦赐数值实行相比较,若相等,重回中间成分值的目录
    • 最中间地点的成分值与要寻觅的钦命数值进行相比较,若不等于,则基于比较的结果,收缩查询范围为上次数组查询范围的四分之二;
      再依照新的询问范围,更新最中间成分地方,然后选取当七月素值与要物色的钦定数值举办比较
       相比较结实非凡,重临中间成分值的目录
       相比结实不对等,继续裁减查询范围为上次数组查询范围的八分之四,更新最中间成分地方,继续比较,依次类推。
    • 当查问范围减少到小于0个要素时,则钦点数值未有询问到,再次回到索引值-1。
  • b: 解题步骤

  • 概念3个用来记录索引值的变量,变量min记录当前范围最小索引值,先导值为0;变量max记录当前界定最大索引值,开首值为数首席实施官度-1;变量mid记录当前当前限制最中间成分的索引值,起头值为(min max) / 2

  • 应用循环,判别当前限定下,最中间成分值与钦点查找的数值是或不是等于
     若相等,甘休循环,再次回到当前范围最中间成分的索引值mid
     若不等于,依照比较结实,裁减查询范围为上贰遍询问范围的日常
     中间成分值 比 要询问的数值大,表达要查询的数值在如今限制的最小索引位置与中间索引地点之间,此时,更新查询范围为:
    限制最大索引值 = 上三次中间索引地点 -1;
     中间成分值 比 要询问的数值小,表明要查询的数值在当前范围的最大索引地方与中间索引地点之间,此时,更新查询范围为:
    界定最小索引值 = 上三遍中间索引地点 1;
     在新的询问范围中,更新当霜月素值的职位,再一次使用最中间成分值与钦赐查找的数值是或不是等于。
    中间索引值 = (范围最小索引值 范围最大索引值) / 2;

  • 老是查询范围减弱八分之四后,使用if语句决断,查询范围是不是小于0个因素,若小于0个要素,则印证钦赐数值未有询问到,重临索引值-1。

15数组的扣除查找代码达成

  • A: 案例代码
        /*
           数组的查找功能
             在一个数组中,找一个元素,是否存在于数组中,如果存在,就返回索引

             普通查询:
               找到元素在数组中出现的索引,如果没有这个 元素,结果就是负数

        */
        public class ArrayMethodTest_3{
             public static void main(String[] args){
                 int[] arr = {1,3,5,7,9,11,15};
                 int index = binarySearch(arr,10);
                 System.out.println(index);

             }

             /*
                 定义方法,实现,折半查找
                 返回值: 索引
                 参数: 数组,被找的元素 
                 实现步骤:
                   1. 需要的变量定义
                      三个,三个指针

                   2. 进行循环折半
                      可以折半的条件  min <= max

                   3. 让被找元素,和中间索引元素进行比较
                       元素 > 中间索引  小指针= 中间 1
                       元素 < 中间索引  大指针= 中间-1
                       元素 == 中间索引  找到了,结束了,返回中间索引

                    4. 循环结束,无法折半
                      元素没有找到 ,返回-1
             */
             public static int binarySearch(int[] arr, int key){
                 //定义三个指针变量
                 int min = 0 ;
                 int max = arr.length -1 ;
                 int mid = 0;
                 //循环折半,条件 min<=max
                 while( min <= max){
                     //公式,计算中间索引
                     mid = (min max)/2;
                     //让被找元素,和中间索引元素进行比较
                     if(key > arr[mid]){
                         min = mid   1;
                     }else if (key < arr[mid]){
                         max = mid - 1;
                     }else{
                         //找到元素,返回元素索引
                         return mid;
                     }
                 }
                 return -1;
             }

            /*
               定义方法,实现数组的普通查询
               返回值: 索引
               参数:   数组, 被找的元素

               实现步骤:
                 1. 遍历数组
                 2. 遍历过程中,使用元素和数组中的元素进行比较
                    如果相同,返回元素在数组中的索引
                    如果不同,返回负数
            */
            public static int search(int[] arr, int key){
                //遍历数组
                for(int i = 0 ; i < arr.length ; i  ){
                    //数组元素,被查找的元素比较
                    if(arr[i] == key){
                        //返回索引
                        return i;
                    }
                }
                return -1;
            }
        }

本文由星彩网app下载发布于计算机编程,转载请注明出处:选料法排序,排序算法

TAG标签: 星彩网app下载
Ctrl+D 将本页面保存为书签,全面了解最新资讯,方便快捷。