Merge sorting algorithm free pascal detailed explanation, plus the source program Thanks.

Quick sort is an improvement on bubbling sorting. Its basic idea is: divide the data to be sorted into two independent parts by lying sorting, all the data of one part are smaller than all the data of the other part, and then quickly sort the two parts of the data according to the secondary method, and the whole sorting process can be carried out recursively, so as to achieve that the whole data becomes an ordered sequence.

Suppose the array you want to sort is a[1] ......a[n], first select an arbitrary data (usually the first data) as the key data, and then put all the numbers larger than it in front of it, and all the numbers larger than it behind it, this process is called a lying quick sort. The algorithm for a lying quicksort is:

1) Set two variables i and j, i:=1 and j:=n at the beginning of sorting;

2) Take the first array element as the key data and assign a value to x, that is, x:=a[1];

5) Repeat step until i>j;

An example of the detailed process is as follows:

Original order: [26 5 37 1 61 11 59 15 48 19].

I: [19 5 15 1 11] 26 [59 61 48 37].

II: [11 5 15 1] 19 26 [59 61 48 37].

Three: [1 5] 11 [15] 19 26 [59 61 48 37].

IV: 1 5 11 [15] 19 26 [59 61 48 37].

V: 1 5 11 15 19 26 [59 61 48 37].

Xx: 1 5 11 15 19 26 [37 48] 59 [61].

VII: 1 5 11 15 19 26 37 48 59 [61].

VIII: 1 5 11 15 19 26 37 48 59 61

The quicksort method is the fastest and most efficient of all sorting methods. The procedure is as follows:

var a:array[0..10] of integer；

n:integer;

procedure qsort(l,r:longint);

var i,j,m:longint;

beginm:=a[l];

i:=l;j:=r;

repeat

while a[i]m do dec(j);

if i<=j then begin

a[0]:=a[i];

a[i]:=a[j];

a[j]:=a[0];

inc(i);

dec(j);

end;until i>j;

if lif iend;

beginfor n:=1 to 10 do read(a[n]);

qsort(1,10);

for n:=1 to 10 do write(a[n]:4);

end.

1. Algorithmic thinking.

Quick sort is a type of division exchange sort proposed in 1962. It uses a divide-and-conquer strategy, often referred to as the divide-and-conquer method.

1) The basic idea of the partition method.

The basic idea of the partition method is to decompose the original problem into a number of sub-problems that are smaller in size but similar in structure to the original problem. Solve these subproblems recursively, and then combine the solutions of these subproblems into the solution of the original problem.

2) The basic idea of quicksorting.

Let the current unordered area to be sorted be r[low..high], using divide and conquer, the basic idea of quicksort can be described as:

Decomposition: in r[low..high], and use this benchmark to divide the current disorder into two smaller sub-intervals, left and right, r[low..pivotpos-1) and r[pivotpos+1..

high], and make all records in the left sub-compartment have keywords less than or equal to the keywords of the baseline record (presumably referred to as pivot), and all records in the right sub-interval have keywords greater than or equal to, and the base record pivot is in the correct position (pivotpos), and it does not need to participate in subsequent sorting.

Note: The key to partitioning is to ask for the location of the baseline record pivotpos. The result of the partition can be simply expressed as (note pivot=r[pivotpos]):

r[low..pivotpos-1].keys≤r[pivotpos].key≤r[pivotpos+1..high].keys

where low pivotpos high.

Solve: Recursively call quicksort to the left and right sub-intervals r[low..pivotpos-1) and r[pivotpos+1..high] to sort quickly.

Combination: Because when"Solve"At the end of the two recursive calls in the step, their left and right sub-intervals are ordered. For quicksorts,"Combination"The step doesn't need to do anything, it can be seen as a no-operation.

The best case for quicksort is n(log2(n)), and the worst case is n 2