Wrote two list sorting, random number to 50000, began to slower than selection sort insertion sort..
Selection sort is arguably not more sequential access, the list should be more bad, isn't it

CodePudding user response:

List only compare and assignment, without having to consider exchange:
Selection is each traversal without number, select a minimum of (more n * (n - 1)/2 times, each time the assignment (1 ~ n + assignment next (n)), inserted into the list (n)
Insertion sort time never sort of a (n) of the number of, inserted into the list (compare (1 ~ n) times, assignment next (n))

Compare + insert + + assignment set next
Selection sort: best n * (n - 1)/2 + n + n + n * (n - 1)/2; The worst: n * (n - 1)/2 + n + n * (n - 1);
Insertion sort: best n + n + 0; The worst: n * (n - 1)/2 + n + n * (n - 1)/2;

The more random data, the closer the out-of-order, worst case,
In view of the list, insert is superior to choose,

Specific issues to look at your code,
If the array is sorted, you can reference about the comparison of insertion sort and selection sort

CodePudding user response:

Singly linked lists insertion sort,,, really meaningful?
An array of insertion sort is look ahead, but singly linked lists are not meet the conditions of forward lookup,
Two-way chain table can also make a figure,

CodePudding user response:

refer to the second floor wowpH response:

singly linked lists insertion sort,,, really meaningful?
An array of insertion sort is look ahead, but singly linked lists are not meet the conditions of forward lookup,
Two-way chain table can also make a figure,

singly linked lists can also be scanned from the front to rear.