Quick sort

zhaozj2021-02-12 136

I have been studying the sequencing efficiency, and I will write some my own experience.

The following code is the implementation of the fast sorting algorithm, because I think about the reuse and structure of the comparison, so the inheritance system can be used to sort any Object, as long as you provide the basis of Sort.

Using system.collections; using system.diagnostics;

Namespace Malei.math.Sort {///

/// Enum of how to select piVot /// public enum pivotStyle {first = 0, Middle, Last, Random}

///

/// Implement of Quick Sort /// public class quicksort: csort {private random rand = new random (); public random rand {get {rand = value} set {rand = value ;}} Private pivotStyle pivotStyle = pivotStyle.middle; public pivotstyle pivotStyle {get {raetintstyle;} set {pivotstyle = value;}}

Public Quicksort () {}

Protected Virtual Int SelectPivot (int StartIndex, int endindex, ilist list) {INDEX = -1;

if (CheckBounds (list, startIndex, endIndex)) {switch (PivotStyle) {case PivotStyle.First: index = startIndex; break; case PivotStyle.Middle: index = (startIndex endIndex) / 2; break; case PivotStyle.Last: Index = endindex; break; caspotStyle.random: index = rand.next (startIndex, endindex); Break;}}

Return index;}

public override void Sort (IList list, int startIndex, int endIndex) {if (startIndex> = endIndex) {return;} else if (startIndex 1 == endIndex) {if (ItemSorter.Compare (list [startIndex], list [ EndIndex])> 0) SWAP (List, StartIndex, EndIndex);

Return;} else {int pieotindex = selectpivot (startIndex, endindex, list); object pivot = list [pivotindex];

Swap (List, StartIndex, PivotInDex);

INT scanup = startIndex 1; int Scandown = endindex; do {while (scanup <= scandown && itemsorter.compare (list [scanup], pivot) <= 0) scanup ;

While (itemsorter.compare (pivot, list [scandown]) <0) scandown -;

IF (scanup

SWAP (List, StartIndex, Scandown);

IF (StartIndex

IF (Scandown 1

///

/// Summary description for Sort /// public abstract class CSort {protected IComparer itemSorter = null;. Public IComparer ItemSorter {get {if (itemSorter == null) itemSorter = new DefaultComparer ( );

Return ItemsORTER;} set {itemsorter = value;}}

protected virtual bool CheckBounds (IList list, int startIndex, int endIndex) {/// check bounds if (startIndex <0 || startIndex> = list.Count) throw new IndexOutOfRangeException ( "start index is out of range.");

IF (EndIndex <0 || endindex> = list.count) throw new indexoutofrangeexception ("End Index Is Out of Range.");

IF (StartIndex> EndIndex) Throw New InvalidOperationException ("Start Index Must Large Than End Index.");

Return True;}

protected virtual void Swap (IList list, int index1, int index2) {object obj = list [index1]; list [index1] = list [index2]; list [index2] = obj;} public abstract void Sort (IList list, int StartIndex, int endindex;} public class defaultcomparer: iComparer {#Region iComparer Members

Public int compare (Object X, Object Y) {INT in = (int) x; int in = (int) y; return int_x.compareto (y);

#ndregion}

}

After careful test, sort millions of random numbers are around 3.7 s, more worth mentioning is that Microsoft's implementation is also Quicksort, but it can only sort the Array type, 100 There are only about 0.5 s routing, of course, there are many reasons for this, the most important thing is that I use a lot of type packages, this invisible, if sacrifices Generic feature, I think 0.5s Not too big.

As mentioned, rapid sorting is the fastest complexity is the fastest in Nlogn of NLOGN. The same is the number of millions of levels, compared to the plug-in more slower than him.

转载请注明原文地址:https://www.9cbs.com/read-7320.html

9cbs

New Post(0)