浙江高考VB之排序系列_vbzj

在浙江高考中, 排序算法 是一个大头, 下至冒泡选择, 上至桶排索引.
这里我们大致梳理一遍高考可能考到的排序算法.

排序算法有哪些?

在算法中排序 (sort) 有很多算法:

• 冒泡排序 (Bubble Sort)
• 选择排序 (Selection Sort)
• 索引排序 (Hash Sort)
• 插入排序 (Insertion Sort)
• 桶排序 (Bucket sort)

除了上述这些高考常考的算法以外, 还有很多性能更加强大, 速度更快, 更高阶的算法, 比如: 快速排序(Quick sort), 希尔排序 (Shell Sort), 堆排序 (Heap Sort), 归并排序(Merge Sort) … 如果有兴趣可以尝试, 记忆中希尔排序和归并排序的变式在几个模拟卷中碰到过.

准备出发了昂, 上车!

• 冒泡排序

      许多新手第一个学到的排序算法就是 冒泡排序 , 但作为浙江信息高考的宠儿, 浙考院的老师最喜欢拿这个冒泡来恶心你, 各种变形, 各种改编, 各种作, 但是正应一句话: 万变不离其中.
      扯了这么多, 那我们开始了解冒泡排序的思想和特征吧!

  下面是冒泡的运行流程图
  
      交换前数据是: 9 5 6 8 2 7 3 4 1
      交换后数据是: 1 2 3 4 5 6 7 8 9

      通过上方的图可以清楚的发现一个现象,冒泡排序将排序步骤为:

           1.比较相邻的元素，前一个比后一个大 (看题目条件) 调换位置
           2.每一对相邻的元素进行重复的工作，从开始对一直到结尾对，这步完成后，结尾为做大或最小的数
           3.针对除了最后一个元素重复进行上面的步骤
           4.重复1-3步骤直到完成排序

  这里考点就出现了, 有很多小朋友弄不清楚什么是 执行次数 什么是 交换次数. 其实两者很好区分, 执行次数 其实一般指的是 If 条件从句 运行的次数. 现在假设一共有 N 个元素待排序, 那么 执行次数 一定是 N * N次 .为什么? 因为从下文的代码可以知道,冒泡排序一般采用 嵌套For循环语句 来实现, 最坏情况下的时间复杂度是 N * N, 记为 $O$($n^2$) .
     换句最通俗的话来说: 人家代码的 If 就是要一直检查, 直到循环退出.

  什么是时间复杂度

  时间复杂度是描述算法时间的函数 ( $O$ 函数 ) .一般的, 该函数描述时间效率时不包括这个函数的低阶项和首项系数, 也就是说, 当一个程序最坏运行时间是 2$n^2$ + $n$ + 100, 用 $O$ 函数表示就是 $O$($n^2$). 关于时间复杂度还有很多内容, 在这里我就只介绍到这里了.

      交换次数 通过名字就可以知道, 是两两元素交换的次数, 那么它一定是 N * N 次吗? 当然不是, 随便举个例子, 当两个元素不满足条件, 不需要交换时, 那么交换次数一定不是 N * N 次, 甚至再举个极端的例子, 当所有元素都是已经处于排序好的状态, 交换次数就为 0.

      那么又一个难点来了, 这外循环和内循环代表啥的? 走几遍?

  上代码:

  Const n As Integer = 100
  Dim i As Integer, j As Integer
  Dim Arr(1 To n) As Integer
  
  " 这里给Arr数组随机赋值,代码略.
  
  For i = 1 To n - 1                  	" 这是外循环, 控制遍历检查的趟数, 这里走 N - 1 遍
      For j = 1 To n - i	                " 这是内循环, 控制每趟检查的次数, 这里走 N - i 遍, 因为上一次的状态下已经有 i 个数排好了, 还有 N - i + 1 个数需要被检查
          If Arr(j) > Arr(j + 1)	Then	" 这是负责检查的If语句,它的运行的次数也就是上文提到的执行次数
          	Swap(Arr(j), Arr(j + 1))	" 交换,它运行的次数是上文提到的交换次数
          End If
      Next j
  Next i
  
  Sub Swap(X1 As Integer,X2 As Integer)
  	X1 = X1 - X2
  	X2 = X2 + X1
  	X1 = X2 - X1
  End Sub		" 采用加减法交换的 过程(Sub) , 暂且可以理解为没有返回值的交换函数(Function)
  " 此冒泡运行时,总是将最大的数字往后丢
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12
  13
  14
  15
  16
  17
  18
  19
  20

      当然, 上面给的代码是最最常规的冒泡, 考试当然不会赤裸裸的直接考. 在平常的试题中, 它的外循环起点可能不是从头开始, 可能从尾巴上开始, 比如:

  For i = n - 1 To 1	Step -1         " 外循环从后往前
  	For j = 1 To i 
  		If Arr(j) > Arr(j + 1)	Then
  			Swap(Arr(j),Arr(j + 1))
  		End If
  	Next j
  Next i	
  " 此冒泡运行,是把大的数字往后丢
  1
  2
  3
  4
  5
  6
  7
  8

      当然, 也还有的是内循环是从尾巴上开始的, 比如:

  For i = 1 To n - 1
  	For j = n To i + 1	Step -1		"内循环从后往前
  		If Arr(j - 1) > Arr(j)	Then
  			Swap(Arr(j - 1),Arr(j))
  		End If
  	Next j
  Next i
  " 此冒泡运行,是把大的数字往后丢
  1
  2
  3
  4
  5
  6
  7
  8

      其实关于冒泡排序的代码主要靠理解, 不能死记硬背, 分清楚外循环和内循环的作用, 这样才能灵活变通. 关于冒泡排序算法, 还有相应的优化策略. 其实非常简单, 对于程序来说, 如果当某一时刻数组已经有序化了, 那么可以就不需要再进行判断和检查了. 那么实际的 执行次数 还真不一定是 N * N 次了. 小朋友们可能要问了, 之前不是说冒泡排序的 执行次数 一定是 N * N 次吗? 其实没错, 最原始的冒泡排序的 执行次数 确实一定是 N * N 次, 因为它没有优化机制, 不懂得灵活退出. 优化后的冒泡排序则不同, 请看代码:

  i = 1 : flag = True						" 可以看到这里我们使用了一个开关 ---- flag, 
  Do While i < n And flag					" 这里为什么用 While 而不是 For 能够想懂么? 因为VB不像C系的语言,可以在 For 中设置条件, 所以使用 While.
  	flag = Fasle						" 开关关上
  	For j = n To i + 1 Step - 1		
  		If Arr(j) < Arr(j - 1)	Then
  			Swap(Arr(j), Arr(j - 1))
  			flag = True					" 如果发生交换, 证明该数组内元素还未排序完, 开关打开, 继续下一趟检查
  		End If							" 反之, 如果未发生交换, 开关一直是关上, 那么说明该数组内元素排序完, 不用下一趟检查了, 退出冒泡排序
  	Next j
  	i = i + 1
  Loop
  " 此冒泡运行,是把大的数字往后丢
  1
  2
  3
  4
  5
  6
  7
  8
  9
  10
  11
  12

    通过上述代码, 基本了解了冒泡的思想和优化, 那么考试的时候怎么判断是冒泡排序呢?

冒泡排序在考试中特征

• 具有两个循环的嵌套, 可以是 For嵌套, While嵌套, For-While嵌套.
  (注意,这只是冒泡的特征之一, 不能说有嵌套循环的就是冒泡 )
• If 条件判断句中比较的两个元素一定是同一个数组里相邻的两个元素
• If 条件里有交换元素的语句, 且交换同数组内相邻的元素

上述条件都满足则就是冒泡排序.

• 选择排序

   选择排序 又是高考的一个常考点之一, 很多小朋友会将 选择排序 的代码和 冒泡排序 的代码相混淆, 因为 选择排序 的代码有时候被写成 嵌套For. 接下来我们开始对选择排序进行剖析.

下面是选择的运行流程图

    交换前数据是: 3 44 5 27 2 50 48
    交换后数据是: 2 3 5 27 44 48 50

    通过上方的图可以清楚的发现一个现象,选择排序将排序步骤为:

         1.第1次排序：从n个元素中找出最值元素与第1个记录交换
         2.第2次排序：从n-1个元素中找出最值元素与第2个记录交换
         3.第i次排序：从n-i+1个元素中找出最值元素与第i个记录交换
         4.按照上面的方法直到排序结束

首先,循环扫描这个步骤和冒泡是一样的, 也就是说整个代码的 外循环For 是和冒泡排序是一样的, 而且两者都是具有双重嵌套循环, 即外循环和内循环. 那么同理可得, 选择排序的时间复杂度也是 $O$($n^2$). 执行次数 也是 N * N 次, 而 交换次数 也不一定是 N * N.
   与冒泡排序不同的是, 选择排序的交换, 不是同数组相邻两个元素进行交换, 而是同数组内与剩下待排序的数字中的极值交换.

上代码:

 Const n As Integer = 100
 Dim i As Integer , j As Integer, maxIndex As Integer
 Dim Arr(1 To n) As Integer
 
 " 这里给Arr数组随机赋值,代码略.

 For i = 1 To n - 1
 	maxIndex = i									" 申请了一个变量maxIndex,顾名思义, 最大下标的意思. 首先默认置为当前位, 即 i 
 	For	j = i + 1 To n
 		If Arr(j) > Arr(maxIndex)	Then
 			maxIndex = j				            " 如果发现有个数比下标为maxIndex的元素大时, maxIndex下标就该指向那个数, 也就是赋值它的下标
 		End If
 	Next j
 	If maxIndex <> i	Then
 		Swap(Arr(i),Arr(maxIndex))			        " 当maxIndex不等于原下标时, 说明最大值是另一个数, 交换
 	End If
 Next i

 Sub Swap(X1 As Integer,X2 As Integer)
 	X1 = X1 - X2
 	X2 = X2 + X1
 	X1 = X2 - X1
 End Sub								"交换 过程(Sub)
 " 该选择运行会把大的数往后丢
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

    对于选择排序来说, 它也有它的优化变形, 我们给他个名字, 叫做 双向选择排序. 那什么是 双向选择排序 呢? 其实道理很简单, 说白了, 就是双向开工, 减少时间的消耗. 这种排序方法, 很巧妙地把二分的思想结合起来.
   咋双向开工? 其实就是有两个指针一个负责找最大值,一个负责找最小值, 然后按照一定的排序顺序把找到的最值放在两边. 代码如下:

 Dim maxIndex As Integer,minIndex As Integer
 For i  = 1 To n \ 2										" 因为双向所以只用做 n \ 2 趟
 	maxIndex = i											" 将两个充当指针功能的变量赋值默认值
 	minIndex = i
 	For j = i + 1 To n - i + 1								" 有小朋友疑惑为什么内循环的范围是i + 1 To n - i + 1. 因为 i 的范围现在变成了1 To n \ 2. 那么 j 的起始范围就是2 To n \ 2 + 1.
 		If	Arr(j) < Arr(minIndex)	Then	minIndex = j
 		If	Arr(j) < Arr(maxIndex)	Then	maxIndex = j
 	Next j                                                  " 通过内循环找到剩余数字里的最小值和最大值, 将其下标用minIndex和maxIndex指向
 	
 	" 接下来我们把最小的值放在第 i 位, 为什么? 因为 i 是按顺序走的, i - 1 位存储的是之前的最小值.
 	" 还有我们把最大的值放在第 n - i + 1 位, 为什么? 因为n - i + 1 表示倒数第 i 位.
 	
 	Swap(Arr(i), Arr(minIndex))

 	If maxIndex = i	Then	maxIndex = minIndex		         " 这句非常关键, 这里是处理一种特殊情况, 下文讲解
 	Swap(Arr(n - i + 1), Arr(maxIndex))
 Next i
 " 该选择运行会把小的丢前面, 大的丢后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

   很多小朋友想不通为什么会有 If maxIndex = i Then maxIndex = minIndex 这句话. 其实我们好好分析下:

代码 If 检查语句分析

假设现在 Arr数组里有66, 55, 33, 22, 44, 11 这些数字. 当程序处理第一遍的时候, maxIndex 存的是下标1, 也就是数字 66 , minIndex 存的是下标 6, 也就是数字 11. 第一次交换, 没有任何问题, 得到的数组是 11, 55, 33, 22 , 44, 66 .

[重点来了]: 现在我们进入第二次, 发现我们的 maxIndex 存的是下标 2,也就是数字 55.而 minIndex 存的是下标 4, 也就是数字 22. 好那么该交换了. 通过代码你会发现一个问题, Arr(minIndex) 与 Arr(i) 的交换 在 Arr(maxIndex) 与 Arr(i) 的交换 的前面, 也就是说,数字 55已经和数字 22交换了, 但是 maxIndex 存的下标值还是 2, 这怎么办? ,没有错, If语句这个时候就有用了.

• 第一, 这种特殊情况只存在于 maxIndex 存的还是下标 i 的时候. 所以If 的条件是 maxIndex = i 时触发
• 第二, 既然交换了, 但是 minIndex 的值没有被覆盖, 所以此时此刻 minIndex 里存的是其实是最大值的下标, 所以有 maxIndex = minIndex.

    通过上述代码, 基本了解了选择的思想和优化, 那么考试的时候怎么判断是选择排序呢?

选择排序在考试中特征

• 具有两个循环的嵌套, 可以是 For嵌套, While嵌套, For-While嵌套.
  (注意,这只是选择的特征之一, 不能说有嵌套循环的就是选择 )
• If 条件判断句中比较的两个元素一定是一个是数组里遍历的元素, 另一个是储存当前最值的元素
• 在外循环里一般有个 If语句, 里面是交换当前元素和最值元素位置的语句

上述条件都满足则就是选择排序.

• 插入排序

    在浙江高考中, 插入排序 出现的次数与前面的冒泡和选择排序差不多. 多藏于大题当中. 插入排序的灵感来源于我们日常生活中的扑克牌, 大家应该都有玩过, 那么请回忆一下, 当你每次被发到牌时, 是不是喜欢把拿到的牌按顺序插入到自己手里的牌堆里, 这就是插入排序的思想.

下面是插入的运行流程图

    交换前数据是: 9 7 8 2 5 1 3 6 4
    交换后数据是: 1 2 3 4 5 6 7 8 9

    通过上图我们可以发现插入排序的步骤为:

         1.将数组分为两部分, 默认左边是已排序区, 右边是未排序区
         2.取出下一个元素，在左边排序区从后往前扫描
         3.如果左区内的元素大于新元素，将该元素移到下一位置
         4.重复3.直到找到已排序的元素小于或等于新元素的位置
         5.将新元素插入
         6.循环1~5的做法, 直到排序结束

    其实, 插入排序一开始是将一个空数组填充成一个有序数组, 这样操作的话就需要两个数组了 (一个原数据数组, 一个最终有序数组). 这里, 处于对空间的考虑就使用了在一个数组中进行插入排序, 即左边当作是最终有序数组, 右边当作原数据组.
    对于插入排序来说, 因为也是两个嵌套的循环, 所以时间复杂度也为 $O$($n^2$).

上代码:

	Const n As Integer = 100
 	Dim i As Integer , j As Integer, x As Integer
 	Dim Arr(1 To n) As Integer
 	
	" 这里给Arr数组随机赋值,代码略.

	For i = 2 To n							" 排序范围, 为 2 ~ n
		x = Arr(i)							" x为当前指针指向的数, 也就是待排序的那个数, 位置处于右区第 1 个
		j = i - 1							" j 表示开始比较位置, 第一次和左区最后一个比, 也就是左区最大的
		DO While  j > 0 And Arr(j) > x		
			Arr(j + 1) = Arr(j)				" Arr(j)后移
			j = j - 1
		Loop
		Arr(j + 1) = x						" 将x的值插入, 为什么用j + 1 ? 而不是 j ? 因为while退出后,j是比条件的值小1
	Next i
  	" 该插入运行会把小的丢前面, 大的丢后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

    当然, 插入排序也有自己的优化, 叫做 二分法插入排序. 通过名字就直到, 又扯上了二分的思想, 它的运行原理和 二分查找 很像, 换句话说就是用了它的原理:

二分法插入排序原理

• 当在插入第 i 个元素的时候, 对左区的 0 ~ i - 1 个元素进行折半, 也就是说, 当前的元素与折中的那个数字比.
• 然后就是遵循二分查找的那个套路, 如果比折中的值小就在左区前面再折中, 反之就是向左区后面折中, 直到边界即左边指针 > 右边指针.
• 当待排序元素找到它的位置的时候, 它所有后面的左区元素向后移一位.

代码如下:

	Dim L As Integer, R As Integer, M As Integer
	" 这里定义了 L 二分左指针; R 二分右指针; M 二分折中指针
	
	For i = 2 To n
		x = Arr(i)
		L = 1 : R = i - 1
		Do While L <= R							" 二分查找
			M = Fix((L + R / 2))				
			" Fix() 是什么? 其实就是一个取整的函数,消去小数点(不遵守四舍五入,类似C系语言的int())
			" 在 VB 中 Int() 也是取整, 只不过是遵守四舍五入
			If x <= Arr(M)	Then	R = M - 1 Else	L = M + 1
		Loop
		j = i - 1								" 这里其实是插入排序的 "插入"功能代码, 其 "检测" 代码被上面的二分查找替换
		Do While j >= L							" 这里都是大于Arr(i)的数据, 全部后移 1 位
			Arr(j + 1) = Arr(j)
			j = j - 1
		Loop
		Arr(L) = x
	Next i
	" 该插入运行会把小的丢前面, 大的丢后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

   针对插入排序的知识点估计也就这些了, 当然考试中还会有许多变形, 但是都是基于原来功能上改变而来, 思想还是原来的思想. 所以一定要把握其原理和特征.

    通过上述代码, 基本了解了插入的思想和优化, 那么考试的时候怎么判断是插入排序呢?

插入排序在考试中特征

• 具有两个循环的嵌套, 主要是For-While嵌套, While具有检测的功能.
  (注意,这只是插入的特征之一, 不能说有嵌套循环的就是插入 )
• 插入排序中喜欢找一个中间变量, 也就是"哨兵值", 存储着待排序元素.
• While语句里写的是数组的移位, 并且在While循环体外有将 “哨兵值” 赋值给数组中的某一个位置

上述条件都满足则就是插入排序.

• 桶排序(浙考)

      桶排序 虽然其考试考到的频率比前面其他的排序要低一点, 课本上也没有详细的介绍. 但是作为最好理解的排序, 高考偶尔也会出现在选择题里.
      因为桶排序的本质上可以理解为是在构建一个二叉树, 所以网上的桶排序都以 CPP 和 JAVA 的代码居多, 最常看到的就是通过创建结构体指针, 模拟结点进行连接, 使用的方法是递归. 当然 VB 这种先进语言没有指针和结构体, 所以用最原始的方法实现, 什么方法? 用数组 + 循环呗!

  下面是桶排序(经典)的运行流程图
  
  
      交换前数据是: 7 12 56 23 19 33 35 42 42 2 8 22 39 26 17
      交换后数据是: 2 7 8 12 17 19 22 23 26 33 35 39 42 42 56

    通过上图我们可以发现桶排序(经典)的步骤为:

         1.首先有数组Arr(1) ~ Arr(n), 元素值的范围设为 [0, x]
         2.对 [0, x] 进行等范围划分, 分为几个范围, 这里我们把它们叫做"桶"
         3.把 Arr(i) 放入对应的桶中
         4.放入桶后和桶内的数据进行排序
         5.将每个桶连接起来, 形成的数组就是有序的数组了

    桶排序的时间复杂度是 $O$($N+C$), 其中 $C=N\ast (logN-logM)$, 这里是 N 个待排序数据, M 个桶. 是一个时间复杂度为线性函数的排序, 但是稳定的同时还有一个使用条件, 一般在 数据分布均匀 的数组中使用才能发挥到最优, 如果数据都被分到了一个桶里, 那么时间复杂度就是 $O$($nlogn$).
    如果上面没有看懂没有关系, 只是当作对桶排序(经典)性能的一种分析.

下面是桶排序(浙考)的运行流程图


    交换前数据是: 2 3 8 7 1 2 2 2 7 3 9 8 2 1 4 2 4 6 9 2
    交换后数据是: 1 1 2 2 2 2 2 2 2 3 3 4 4 6 7 7 8 8 9 9

上代码:

	Const n As Integer = 100
	Dim i As Integer, j As Integer, x As Integer
	Dim Index(1 To n) As Integer
	Dim Arr(1 To n) As Integer

	" 这里给Arr数组随机赋值,代码略.

	For j = 0 To x
		Arr(j) = 0									" 表示桶内含有数字的个数为 0
	Next j

	For i = 1 To n
		Arr(Index(i)) = Arr((Index(i)) + 1			" 统计当前数字的个数
	Next i

	For j = x To 0 Step -1
		For i = 1 To Arr(j)
			Print(j)				                " 打印, 这里代替里数组的合并
		Next i
	Next j
	" 该插入运行会把小的丢前面, 大的丢后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

    看完上述的代码, 很多小朋友会疑惑, 不是说要等范围划分吗? 不是要分组吗? 这不是统计吗? 没错在浙江高考中, 桶排序是被压缩过的, 它将范围直接圈在每个数字上, 也就是说, 每一个数字就是一个范围, 就是一个桶. 那么这个桶里只能装的是原始数组中同类数字的个数.而我们要做的是,仅仅只是将原始数据对号入桶, 最后按次序输出.
    当然, 内行人一眼看出这是披着 桶排序 的 计数排序, 但是一切为了考试先.

    通过上述代码, 基本了解了浙江高考中桶排序的思想, 那么考试的时候怎么判断是桶排序呢?

桶排序在考试中特征

• 一般先通过循环进行桶的初始化.
• 含有计数原理, 或划范围分组的思想
• 最后按常数顺序依次输出被计数数组的值

上述条件都满足则就是桶排序(浙考).

• 索引排序

    索引排序 ,可谓是浙考一大特色, 在考试前我都没听过这种排序. 其实的本质上, 就是在排序的过程中带入了 映射表 的概念, 其实通过英文名就能判断出来, "Hash" 多么让人虎躯一震的词. 很多小朋友可能看懵了, 毕竟浙江信息没教过 映射表(Hash Table). 首先先来了解下什么是映射.

下面是《要命导论》对于映射表的一张插图.


    结论: 对号入座
    这张图的解释:
       1.首先这张图里有这些元素: Universe of Keys(所有的关键数字), Actual Keys(正在使用的关键数字),Satellite Data(被映射数据)
       2.每一个 Actual Key 对应一个 Satellite Data, 这种关系在数学里叫做 映射 .
       3.而 Actual Key 在考试中被认为是数组下标

既然知道了什么是映射, 那么索引排序是怎么利用映射的呢? 怎么用索引排序呢?

首先来看个例子:

现在我们有三个朋友, 他们分别是大, 中, 小朋友. 现在,他们有一下属性:

• 姓名 ---- name数组
• 学号 ---- num数组
• 成绩 ---- score数组
• 排名 ---- sort数组

接下来假设我们想要按学校进行排序, 那么排名将会显示 小朋友是 1, 中朋友是 2, 大朋友是 3.
如果假设我们想要按成绩进行排序，那么排名将会显示 小朋友是 1，中朋友是 2，大朋友是 3

那怎么实现这样的功能呢? 其实很简单, 结合上面映射的思想, 我们先定义一个数组, 数组中存的数字表示指向当前属性的下标,而其数组下标是排名,比如说 index(4) = 3 表示的是指向原数组下标位3的元素,而且这个元素的排名是第 4.

上代码:

	Const n As Integer = 100
	Dim Arr(1 To n) As Integer
	Dim Index(1 To n) As Integer

	" 这里给Arr数组随机赋值,代码略.

	For i = 1 To n
		index(i) = i
	Next i

	For i = 1 To n
		For j = i To n
			If Arr(Index(i)) > Arr(Index(j))	Then
				Swap(Index(i), Index(j))
			End If
		Next j
	Next i

	Sub Swap(X1 As Integer,X2 As Integer)
		X1 = X1 - X2
		X2 = X2 + X1
		X1 = X2 - X1
	End Sub		" 采用加减法交换的 过程(Sub)
	" 该插入运行会把小的丢前面, 大的丢后面
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

上述代码是不是很像冒泡? 其实索引排序是 基于其他排序 的排序算法, 一般和它组合的还有选择和插入排序,但是与原排序不同的是加入了映射的概念.
索引是一种思想, 不止会出现在排序里, 比方说, 浙江高考神奇的数组嵌套(不肯用二维)来做贪心背包, 还有等等各种改编题目, 都会出现索引. 可以这么说, 只要考试, 肯定有索引.

    通过上述代码, 基本了解了索引的索引的思想, 那么考试的时候怎么判断是索引排序呢?

索引排序在考试中特征

• 决定特征: 具有映射思想
• 与前几种排序相搭配

上述条件都满足则就是索引排序.

总结

通过上述对各种排序的描述, 应该能够对这些算法有了初步的印象. 其实还有许多排序算法也会在考试中考到, 比如希尔排序 , 归并排序 但是考试并不会使用传统方法, 特别是含递归的算法, 都喜欢用数组和循环改编.