前段时间帮助一个同学完成了一道Visual FoxPro的排序算法作业题，在此记录一下。
一、题目要求：
程序先要求使用者输入N个数，最后依次输出原始输入数列、从小到大排列后的数列、从大到小排列后的数列、两端大中间小排列后的数列。
二、程序代码：
- CLEAR
- NumCount = 0
- INPUT " 请输入需要排序的N个数：" to NumCount
- IF NumCount<1
- ? " 输入的数据个数必须大于0!"
- RETURN
- ENDIF
- DIME NumArr(NumCount)
- * Accept numbers from keyboard
- FOR i=1 TO NumCount
- INPUT " 请输入第"+ALLTRIM( STR(i) )+"个数：" to NumArr(i)
- ENDFOR
- * Print Orginal numbers
- ? " 原始输入数列："
- FOR i=1 TO NumCount
- ?? ALLTRIM( STR( NumArr(i) ) ) + " "
- ENDFOR
- * Sort the array
- FOR curIndex = 2 TO NumCount
- curData = NumArr( curIndex )
- sortedMinIndex = 1
- sortedMaxIndex = curIndex - 1
- * query the positon that the curData should put in
- DO WHILE sortedMinIndex <= sortedMaxIndex
- midIndex = ( sortedMinIndex + sortedMaxIndex ) / 2
- IF NumArr( midIndex ) < curData
- sortedMinIndex = sortedMinIndex + 1
- ELSE
- sortedMaxIndex = sortedMaxIndex - 1
- ENDIF
- ENDDO
- *move data forward index from sortedMinIndex
- FOR j = curIndex - 1 TO sortedMinIndex STEP -1
- NumArr( j+1 ) = NumArr( j )
- ENDFOR
- * put curData to its position
- NumArr( sortedMinIndex ) = curData
- ENDFOR
- * Print data from min to max
- ? " 从小到大排序："
- FOR i = 1 TO NumCount
- ?? ALLTRIM( STR( NumArr(i) ) ) + " "
- ENDFOR
- * Print data from max to min
- ? " 从大到小排序："
- FOR i = NumCount TO 1 STEP -1
- ?? ALLTRIM( STR( NumArr(i) ) ) + " "
- ENDFOR
- * Print from both ends to center
- ? " 两端大中间小："
- FOR i = NumCount TO 1 STEP -2
- IF i>0
- ?? ALLTRIM( STR( NumArr(i) ) ) + " "
- ENDIF
- ENDFOR
- IF i=0
- startIndex = 1
- ELSE
- startIndex = 2
- ENDIF
- FOR i = startIndex TO NumCount STEP 2
- IF i <= NumCount
- ?? ALLTRIM( STR( NumArr(i) ) ) + " "
- ENDIF
- ENDFOR
三、编程思路：
首先，我们要用一个数组来接收用户输入的原始数据。根据用户指定的数据个数来定义数组维数，并逐个接收用户输入的数据保存到数组里。用户输入数据完毕，即可打印原始数列。
为了实现数据的从大到小、从小到大以及两头大中间小的排序，首先就要将该数组从小到大递增排序，然后实现另外两种排序就相对简单了。
对原始序列进行排序的方法很多，有冒泡排序、选择排序、希尔排序及插入排序等，这里选择使用插入排序算法。
总体的思路是假设已经有一个已经排序过的序列，向该序列中插入一个新的数据，新数据放在这个已经排序的序列中适当的位置，保证插入新数据后的序列还是一个有序序列。
对于一个长度为N的原始序列a [1]，a[2]，…a[N]，我们可以认为第一个数据a[1]是有序的（即这个有序序列只包含一个数据a[1]），这时我们将原始序列中第2个数据a[2]插入这个只包含一个数据的有序序列中，并保证插入后的序列“a[1],a[2]”仍然是有序的。至此，原始序列可以分为已排序和未排序的两个部分，第1个及第2个数据“a[1],a[2]”是有序的，第3个至第N个数据“a[3],a[4],…a[N]”仍然是未排序的。这时我们继续将第3个数据a[3]插入到有序序列中（包含第1个数据和第2个数据的序列“a[1],a[2]”）并保证插入后第1至第3个数据“a[1],a[2],a[3]”是有序的。依此类推，直到第N个数据插入到由第1个至第N-1个数据组成的 有序序列“a[1],a[2],…a[N-1]”中，并保证插入后这个N个数据都是有序的。
一般的，假设序列中第1个至第i（ 1<=i<N ）个数据“a[1],a[2],…a[i]”是已经排序的，我们将第i+1个数据插入到第1至i-1个数据组成的序列中,为了保证插入后的包含i+1个数据的序列仍然有序,就要将第i+1个数据a[i+1]放在有序序列中适当的位置。
由于序列“a[1],a[2],…a[i]”是已经排序的，我们可以将数据a[i+1]与已经排序的序列按递增或递减方向依次做对比，以找到a[i+1]在有序序列中应该处在的位置。例如，将数据a[i+1]依次与数据a[1]、a[2]、…a[i]做比较，如果a[i+1]比当前比较的数据a[j] （ 1<=j<=I ）小，则应将a[i+1]放在a[j]的位置，否则继续与下一个数据比较。
由于序列“a[1],a[2],…a[N]”是已经排序的，所以插入a[i+1]时可以采用“折中查找”算法，而不必将a[i+1]与有序数列中的数据逐个比较，大大减小比较次数，降低复杂度。将设m=(1+i)/2，即a[m]是a[1]…a[i]数列的中间数据，我们可以直接将a[i+1]与a[m]进行比较，如果a[i+1]>a[m]，则继续将a[i+1]与“a[m+1]…a[N]”的中间数据进行比较，反之则与“a[1]…a[m-1]”的中间数据进行比较。依次类推，直至最终找到a[i+1]的位置。
在进行a[1]…a[N]的排序后，就可以按1..N的顺序打印出递增数列及按从N…1的序列打印出递减数列。
为了打印出两头大中间小的序列，分两步打印。第一步从N..1的顺序间隔打印，即打印a[N]、a[N-2]、a[N-4]… a[3]、a[1]。（如果N是偶数则打印a[N]、a[N-2]、a[N-4]… a[4]、a[2]）。第二步从1…N的顺序间隔打印a[2]、a[4]…a[N-1]（如果N是偶数则打印a[1]、a[3]、…a[N-1]）。
四、 程序分析
1. 将用户输入的“数据个数”保存到变量NumCount，声明一个长度为NumCount的数组NumArr，依次接收用户输入的数据保存到数组NumArr里。
2. 用一个循环输出数组NumArr里的所有数据，即输出用户输入的原始数列。
3. 对数组NumArr进行递增排序。从第2个数据开始至最后一个数据循环插入到前面已经排序的数列中。
1） curIndex 为当前循环中待插入的数据，即到此循环时，第1个到curIndex-1个数据是已经排序的；sortedMinIndex和sortedMaxIndex为已经排序的序列的最小和最大的索引；
2） 用折中查找法在已经排序的数列中找到第curIndex个数据应该存放的位置（即最终sortedMinIndex所在的位置）；
3） 将sortedMinIndex的到curIndex-1的数据依次后移；
4） 将curIndex所在位置的原来数据放到sortedMinIndex位置上，从而达到从1到curIndex的数据都是排序过的目的。
4．将已经排序的数组NumArr从1到NumCount的顺序输出，即输出从小到大的数列；
5．将已经排序的数足从NumCount到1 的顺序输出，即输出从大到小的数列；
6．输出两头大中间小的数列：
1）从NumCount到1的顺序间隔输出数列，既循环变量i的步长为-2。
2) 第一步输出完毕后，最后一个输出的数据只能是NumArr数组的第一个数据或第二个数据，即循环终止后i的值是-1或0。如果i是0，则第一步最后输出的是NumArr的第2个数据，本次输出应该从第1个数据开始；否则上次最后输出的是NumArr的第1个数据，本次循环应该从2个数据开始输出。且本次循环直到NumCount间隔输出。