Eric Sosman於 2013年3月17日星期日UTC+8上午3時41分20秒 寫道：

> On 3/16/2013 2:39 PM, Robert Wessel wrote:

>

> > On Sat, 16 Mar 2013 15:40:23 +0100, David Brown

>

> > <(E-Mail Removed)> wrote:

>

> >

>

> >> On 16/03/13 14:10, Nick Keighley wrote:

>

> >>> On Mar 16, 10:29 am, David Brown <(E-Mail Removed)>

>

> >>> wrote:

>

> >>>> On 15/03/13 23:55, BartC wrote:

>

> >>>>

>

> >>>>> I've provided some code below. Note that this uses the world's worst sort

>

> >>>>> method, so won't get you many marks. But it's also my favourite sort.

>

> >>>>

>

> >>>> Bubblesort has a lot of real-world uses. It has a worse complexity

>

> >>>> scaling than the "big" sorting algorthims (mergesort, heapsort,

>

> >>>> quicksort, etc.), but run speed is not always the most important issue.

>

> >>>> /Correctness/ is far more important - and it is much easier to write a

>

> >>>> correct bubblesort than a correct heapsort. For small samples,

>

> >>>> especially on more limited systems (such as embedded systems),

>

> >>>> bubblesort will often be significantly faster than using a generic

>

> >>>> library "qsort" function - and very much smaller in code space.

>

> >>>>

>

> >>>> Anyway, I thought the world's worst sort method was this:

>

> >>>>

>

> >>>> <http://en.wikipedia.org/wiki/Bogosort>

>

> >>>

>

> >>> but insert sort is as simple *and* better

>

> >>>

>

> >>

>

> >> Insert sort is not "as simple /and/ better" than bubblesort. To do an

>

> >> efficient insertion sort (and it has to be efficient, or it is not

>

> >> "better"), you need to use a binary search to find the insertion point

>

> >> for each element, and you need to hold your elements in a linked list

>

> >> rather than a static array (otherwise you need to move half your data

>

> >> for every insertion, which is not "better").

>

> >>

>

> >> Of course, this is for a general sort - for some kinds of applications,

>

> >> insertion sort is very well suited.

>

> >>

>

> >> Unless you meant that insert sort is as simple and better than bogosort...

>

> >

>

> >

>

> > No, ordinary insertion sort requires neither of those, and can sort an

>

> > array with no additional storage, just like bubble sort. The basic

>

> > idea is that you take each element and then move it back one spot at a

>

> > time in the array (by swapping with the prior element) until it's in

>

> > the correct spot. It's still O(n**2), but usually runs about twice as

>

> > fast as bubble sort, and the code is usually shorter too.

>

> >

>

> > for(i=1; i<N; i++)

>

> > for(j=i; j>0; j--)

>

> > {

>

> > if (a[j-1] > a[j])

>

> > swap(a[j-1], a[j]);

>

> > else

>

> > break;

>

> > }

>

>

>

> A simple change will speed this up significantly on most

>

> machines. The problem is with the swap() operation: It will

>

> exchange (for example) items [10] and [9], then [9] and [8],

>

> then [8] and [7] -- six memory writes to slide the original

>

> [10] element three places to the left. By holding the "moving"

>

> element in a temporary throughout, you can avoid almost half

>

> the writes:

>

>

>

> for (i = 1; i < N; ++i) {

>

> int temp = a[i];

>

> for (j = i; --j >= 0; ) {

>

> if (a[j] > temp)

>

> a[j+1] = a[j];

>

> else

>

> break;

>

> }

>

> a[j+1] = temp;

>

> }

>

>

>

> For the same rearrangement, this code loads temp from [10],

>

> then copies [9] to [10], [8] to [9], [7] to [8] and finally

>

> stores temp in [7] -- four writes instead of six. (Assuming

>

> that temp winds up in a register; if it doesn't, there'll

>

> be five writes instead of nine because swap() will need an

>

> additional internal write, too.)

>

>

>

> --

>

> Eric Sosman

>

> (E-Mail Removed)d
This is the classical insertion sort of inserting the last one

into the sorted list before the current inserting element.

Of course, it is possible to insert 2 elements at a time

to speed up slightly for reducing the loop overheads.