Experiment 6 Sorting algorithms

1. Purpose of the experiment

Master the common sorting methods, and master the method of using high-level language to realize the sorting algorithm;

2.Essential basic knowledge

Definition of sorting:Sort a sequence of objects according to a keyword.

Stable: if A is in front of B and A = B, A is still in front of B after sorting;

Unstable: if A is in front of B and A = B, A may appear after B after sorting;

Inner sort: all sort operations are completed in memory;

External sorting: because the data is too large, the data is put on the disk, and sorting can only be carried out through the data transmission of disk and memory;

Time complexity: the amount of time an algorithm takes to execute.

Space complexity: the amount of memory needed to run a program.

3. Experimental content

To input n numbers from the keyboard, it is required to use a common sorting method, such as simple selection sorting, bubble sorting and other sorting algorithms to sort and output the N numbers in the order of large to small and small to large.

4.Program code

You can program your own programs, or refer to the following procedures. If you refer to the code I gave, please translate the Chinese text in the code into English.

#include

#include

void swap(int k[], int low, int high)

{

int temp = k[low];

k[low] = k[high];

k[high] = temp;

}

//Exchange the subtable records in the sequence table, the fork axis record is in place, and return its location

// At this time, the records before (after) him are not larger (smaller) than it on average

int Partition(int k[], int low, int high)

{

int pivot key;

pivotkey = k[low]; //Use the first record of the subtable to record the left branch axis

while (low

{

while (low= pivotkey)

High - ;

swap(k,high,low); //swap records smaller than branch axis records to low end

while (low < high&&k[low] <= pivotkey)

Low++;

swap(k,low,high); //swap records larger than branch axis records to high side

}

Return to the low point; //Return to the position of the node axis

}

void Qsort(int k[], int low, int high)

{

int pivot;

if (low < high)

{

pivot = partition(k,low,high);

Qsort(k, low, pivot-1); // recursively sort the low sublist

Qsort(k, pivot + 1, high); // recursively sort the high subtable

}

}

main function()

{

int i;

int a[10] = { 5, 2, 6, 0, 3, 9, 1, 7, 4, 8 };

Qsort(a, 0, 9);

For (i = 0; i < 10; i++)

printf("%d", a[i]);

system("Pause");

return 0;

}

5.Operation results

Please give the result of the program.