快速新的排序例程 - 人类排序
2.57/5 (28投票s)
2005年3月23日
3分钟阅读
122212
363
一个新的快速排序例程，适用于您的项目。
引言
下面的代码片段是一个原地排序例程，总的来说，它比 Shell 排序更快 - 几乎和快速排序一样快，在某些情况下甚至更快。 它稳定、易于实现、非递归且不使用堆栈。 无论列表/数组的排序方式如何，它的速度几乎没有差别。 总的来说，我相信您会发现它对于任何排序需求都非常有用。 欢迎提出任何反馈意见。
背景
一天晚上我躺在床上，想着最近的项目中使用的几个排序例程，我开始尝试创建自己的例程。 由于计算机很像一个没有视力的人，我试图想象（作为一个盲人）我如何对盲文项目列表进行排序。 几分钟之内，我想到了下面的算法。 我起床，以粗略的形式写下来，然后睡着了。 第二天早上，我设置了一个简单的程序来测试该算法 - 它运行得非常好。
如下面的代码注释所示，我们首先对列表进行简单扫描，以查看它是否已经排序。 如果没有，我们开始扫描第一个项目下面的列表，以找到最小的项目。 找到最小的项目后，我们将其与当前列表项目进行比较。 如果找到的最小项目小于当前项目，则执行交换。 然后，我们移动到列表/数组中的下一个项目并重复该过程，并一直这样做，直到完成。
这个过程如此简单，我很惊讶以前没有人想到它。 随着排序的进行，列表变得越来越短，速度也越来越快...
我认为您会发现，在这种方法中，项目的交换已减少到绝对最小值。 在未排序的列表上，它的表现确实非常好 - 但在几乎排序的列表上，您可能应该使用 Shell 排序。 我最初尝试合并 Shell 排序（及其修改/增强版本），但结果好坏参半（这取决于列表的排序程度）。
我很想得到关于我的方法的反馈 - 尤其是如果您能提出任何改进建议。 随意使用代码，并下载示例演示程序和源代码并进行实验。
请注意，我使用了 Microsoft 的新 Visual Basic .NET 2005 beta 程序来编写和编译代码。 稍作调整，它应该可以很容易地在其他软件平台上运行。
使用代码
下面的代码按升序格式（A 到 Z）排序。 将其转换为降序格式相当容易（这个练习将留给您 - 除非您需要帮助）。 如下所示，该代码设置为对 ListBox 中的字符串进行排序，但可以很容易地将其修改为对数字或记录或您想要排序的任何内容进行排序。
Private Sub HumanSort()
'HumanSort - Intellectual copyright of Clark Hay - created on 02/15/2005
'This is a unique and very fast in-place sort.
'I wanted something that sorts like
'a blind human might, but at computer speeds.
'The basic idea is to scan the list/array
'first to see if it is already sorted.
'If it is, then we're done.
'If the list/array is almost sorted then you can use the Shell sort.
'Otherwise use the Human sort.
'Starting with the item below the current item in our list/array -
'we scan our list/array to find the smallest item.
'When the smallest item is found, we compare it to our current item.
'If the smallest item found is smaller
'than our current item then we perform a swap.
'We then move down to the next item in
'or list/array and repeat the process.
'We keep doing this till we are done.
'This is a simple and quick process.
'I'm surprised no one has thought of it before.
'As the sort progresses, the list gets shorter and goes faster and faster ...
'The swapping of items is reduced to the absolute minimum in this method.
'On unsorted lists it performs very well indeed, -
'but on lists that are very nearly sorted, you should use the Shell sort.
'The Human Sort does not use recursion
'& doesn't have stack overflow problems.
Dim i As Integer
Dim numRecs As Integer
Dim tempRec As String
Dim NextSmallRec As String
Dim NextSmallIndex As Integer
Dim CurrentRec As String
Dim numsorted As Integer
Dim Ascending As Integer
'===> Get number of records in database
numRecs = ListBox1.Items.Count - 1
'Set our counter to 0
numsorted = 0
'***************************************************
'* Here is where we see if our items are sorted *
'***************************************************
'Set our counter to zero
Ascending = 0
If numRecs < 2 Then
GoTo VeryEnd '===> if only 1 or 0 items, then there is nothing to sort
Else
'===> See how many items are in descending or ascending order:
For i = 0 To numRecs - 1
If ListBox1.Items(i) <= ListBox1.Items(i + 1) Then
Ascending = Ascending + 1
End If
Next
End If
'===> if our list is already sorted in ascending order,
' then there is nothing to sort
If Ascending = numRecs Then GoTo VeryEnd
'I've commented out the next 4 lines for a reason:
'As you play with the demo sort program,
'you will notice there are times -
'when the ShellSort out-performs
'the Human Sort and the ShellSortEnhanced.
'I haven't yet determined which sort to use.
'It all depends on a number of factors that I have yet to figure out.
'If Ascending > Int(numRecs * 0.9) Then
'ShellSort()
'GoTo VeryEnd
'End If
'===> otherwise we'll default to our ascending Human sort routine:
'***************************************************
'* This is the ascending version of the Human sort *
'***************************************************
Do While numsorted < numRecs
'===> Get the zip code from the current record in our list
CurrentRec = ListBox1.Items(numsorted)
NextSmallIndex = numsorted
NextSmallRec = ListBox1.Items(NextSmallIndex)
For i = (numsorted + 1) To numRecs
'===> see if the next zipcode down
' is > than what we've found so far
If NextSmallRec > ListBox1.Items(i) Then
'===> If we've found something
' smaller or = then get it's index
NextSmallIndex = i
'===> and record it's value to see
' if anything is smaller than it
NextSmallRec = ListBox1.Items(i)
End If
Next
If NextSmallIndex >= numsorted + 1 Then
'===> Now that we know the smallest item
' in our list, we see if we need to swap
If CurrentRec > NextSmallRec Then
tempRec = ListBox1.Items(numsorted)
ListBox1.Items(numsorted) = ListBox1.Items(NextSmallIndex)
ListBox1.Items(NextSmallIndex) = tempRec
ElseIf CurrentRec = NextSmallRec Then
numsorted = numsorted + 1 '
tempRec = ListBox1.Items(numsorted)
ListBox1.Items(numsorted) = ListBox1.Items(NextSmallIndex)
ListBox1.Items(NextSmallIndex) = tempRec
End If
End If
'===> Now we can increment the number of records we have sorted
numsorted = numsorted + 1
'===> and we keep going till we are done
Loop
VeryEnd:
End Sub
关注点
如果您下载演示代码，您还会发现 Shell 排序的两种实现方式。 一种是相当通用的，但另一种使用一组预定的间隔大小，其性能优于我见过的任何其他此类预定的间隔列表。
该演示程序允许您使用人工排序、通用 Shell 排序和增强的 Shell 排序对 10,000 个数字的列表（排序为字符串）进行排序。 您可以选择随机生成的列表、降序列表、升序列表、半升序半降序列表、75% 降序和 25% 随机列表以及 75% 升序和 25% 随机列表。
每种方法的排序时间以秒和毫秒显示。 正如我一开始所说，人工排序的排序时间相当恒定 - 无论列表/数组的排序方式如何。
历史
这是 1.0 版本。