Relive classic sorting ideology - C language common sorting sentence

xiaoxiao2021-03-06 99

Source: http://blog.9cbs.net/rerli/archive/2003/12/15/19040.aspx/*======================= ======================== author: rerli time: 2003-12-15 Objective: To revisit the classic sort of thought, and implement sorting algorithms in C language pointer = ================================================================================================ * /

/ * ================================================================================================================================================================ ============================= Related knowledge introduction (all definitions only help readers understand the relevant concepts, is not strict definition): 1, Stable sorting and non-stable sorting briefly, after all equal numbers have been sorted, they can maintain their relative order before sorting, saying that this sorting method is stable. Conversely, it is non-stable. For example: a set of numbers are A1, A2, A3, A4, A5, where A2 = A4, after some sorting, the A1, A2, A4, A3, A5, then we say that this sort is stable because The A2 is sorted in front of A4, it is still in front of A4. If it turns into A1, A4, A2, A3, A5 is not stable.

2, ordering and exterior

In the sorting process, all the numbers that need to be sorted are in memory, and their storage sequence is adjusted in memory, referred to as within the ordering process, only the number of parts is transferred to memory, and the memory adjustment is in the outside. The storage order sorting method is referred to as external sorting.

3, the time complexity and spatial complexity of the algorithm

The time complexity of the so-called algorithm refers to the calculation workload required to perform an algorithm. An algorithm has a spatial complexity, generally refers to the memory space required to perform this algorithm. ============================================================================================================================================================================================================= ============================== * // * ======================= ================================ function: Select sort input: array name (that is, the first address), array Element number ================================================= = * // * ================================================ ======= Algorithm idea is simple description:

In a set of numbers to be sorted, the minimum number of numbers are selected with the first position; then in the remaining number, then the minimum number of exchanges with the second position is reserved, so looped to the second The number and the last number are relatively compared.

Selecting sorting is unstable. Algorithm complexity o (N2) - [square] ============================================================================================================================================================================================ ================== * / void select_sort (int * x, int N) {INT I, J, MIN, T;

For (i = 0; i

In a set of numbers to be sorted, it is assumed that the previous (N-1) [n> = 2] is already a row order, and now, insert the n number to in the front, the number of appearances, make this N The number is also the order of racing. This is repeatedly circulated until it is entirely ranked. Direct insertion sorting is stable. Algorithm time complexity O (N2) - [square] =================================== =================== * / void insert_sort (int * x, int N) {INT I, J, T;

For (i = 1; i = 0 && t <* (x j); j -) / * Note: j = i-1, J - Here is the number of subscripts of I, and there is a sequence in front of it to find the insertion position. * / {* (X J 1) = * (x j); / * If the condition is met, it will be moved. The worst case is that T is smaller than the number of subscripts, it is to be placed in front, j == - 1, exit loop * /} * (x j 1) = t; / * Find the subscript Placement position for the number of i * /}}

In a set of numbers to be sorted, all the numbers in the range of the currently not row, the two numbers are compared and adjusted from the top of the two numbers, so that the large number is down, more Small topless. That is, each time the two adjacent numbers are discovered, they interchange them when they are sorted and sorted. Below is an improved bubbling algorithm that records the position K of the last sinking number after scanning, which can reduce the number of outer cyclic scans.

Bubbling sort is stable. Algorithm time complexity O (N2) - [square] =================================== =================== * / void bubble_sort (int * x, int N) {INT J, K, H, T; for (h = n-1; h> 0; h = k) / * loop to no comparison range * / {for (j = 0, k = 0; j * (x j 1)) / * large placed behind, small placed in front * / {t = * (x j); * (x j) = * (x j 1); * (x j 1) = t; / * Complete switch * / k = j; / * Save the last sink position. This is to be ranked in this way. * /}}}}}}

/ * ================================================================================================================================================================ Function: Hill sort input: array name (that is, the first address), the number of elements in the array ============================ ==================== * // * ========================================================================================================================================== =========================== Algorithm idea: In the direct insertion sort algorithm, one number is inserted, enabling the ordered sequence only increases 1 node and no help is provided to insert the next number. If the number is compared to the number of distant distances (referred to as increment), the number can be exchanged for a comparison when moving the number, and a comparison may eliminate multiple elements exchange. D.L. SHELL realized this idea in the sorting algorithm named in his name in 1959. The algorithm first is divided into a number of groups to be sorted by a number of increments d. The subscripts recorded in each group are D. Sort all elements in each group, and then use a smaller increment to it. Sort in each group. When the increment is reduced to 1, the number to be sorted is divided into group one, sorted. The following function is an implementation of a Hill's sort algorithm, half of the first sequence is increment, and then halves each time until the increment is 1. Hill sort is unstable. ============================================================================================================================================================================================================= === * / void shell_sort (int * x, int N) {INT H, J, K, T;

For (h = n / 2; h> 0; h = h / 2) / * control increment * / {for (j = H; j = 0 && t <* (x k)); k- = h) {* (x k h) = * ( X K);} * (x k h) = t;}}} / * ============================ ==================== Function: Quick Sorting: Array Name (that is, the first address), the subscript of the end elements in the array ======= ====================================================================================================================================================================== =============================================== algorithm is simple description:

Rapid sorting is an essential improvement in bubble sorting. Its basic idea is to make the length of the sorting sequence greatly reduced by a scan. In the bubbling sort, a scan can only ensure the maximum number of values to the correct position, and the length of the sequence to be sorted may only be reduced by 1. Quickly sort by scanning, you can ensure that a number (with it is a reference point) is smaller than it, and the numbers on the right are larger than it. Then use the same method to handle the number of left and right sides until the left and right of the reference point is only one element. It was made by c.a.r.hoare in 1962. Obviously rapid sorting can be implemented in recursive, of course, can also be achieved with a stack. The following functions are implemented with recursive, interested friends can change to non-recursive.

Rapid sorting is unstable. Ideally Ideal Algorithm Time Combination O (NLOG2N), the worst O (N2) ================================ ===================== * / void Quick_Sort (int * x, int low, int high) {INT I, J, T; if (Low

While (i T) / * As long as the reference point is still on the right * / {J -; / * Front moves a position * /}

IF (i

While (i

IF (i

* (x i) = t; / * After scanning, put it in the appropriate position * / quick_sort (x, limited, i-1); / * Perform rapid sorting of the number left on the reference point * / Quick_Sort (X , i 1, high); / * Rapid sorting on the number of reference points * /}}

As can be seen from the definition of the heap, the pile element (ie the first element) is the biggest term. The full binary tree can be visually visually representing the structure of the heap. The top of the pile is root, the other is a left sub-tree, the right man tree. At the beginning, the sequence to be sorted as a sequence of sequentially stored binary trees, adjusting their storage order, making it a heap, the number of root nodes of the heap. Then exchange the root node with the last node of the heap. Then re-adjust the number of previous (N-1) makes it a heap. Since this type, until only two nodes are heaps, and they are exchanged, and finally the ordered sequences with n nodes are obtained.

From the algorithm description, the stacking requires two processes, one is to build a heap, and the other is the last element exchange location of the top and the heap. Therefore, the heap sort has two functions. The first is the penetration function of building a pile, and the other is a function of reseudently call the penetration function.

Stacking routine is unstable. Algorithm time complexity O (NLOG2N).

* // * Function: Penetration buildings Enter: Array name (that is, the first address), participate in the number of buildings, starting from the first elements * / void sift (int * x, int N, int S) {INT T, K, J;

T = * (x s); / * Temporary Start element * / k = S; / * Start element subscript * / j = 2 * k 1; / * Right sub-tree element subscript * /

While (j

/ * Function: Heap Sorting: Array Name (that is, the first address), the number of elements in the array * / void heap_sort (int * x, int N) {INT I, K, T; int * P;

For (i = n / 2-1; i> = 0; I -) {SIFT (x, n, i); / * initial build heap * /} for (k = n-1; k> = 1; K -) {t = * (x 0); / * Pile top to last * / * (x 0) = * (x k); * (x k) = T; SIFT (x, K, 0); / * The rest of the number and then built the pile * /}}

Void main () {#define max 4 int * p, i, a [max]; / * Retrieve test data * / P = a; printf ("INPUT% D Number for Sorting: / N", Max); for i = 0; i

/ * Test selection Sort * /

P = a; select_sort (p, max); / ** /

/ * Test direct insertion sort * /

/ * P = a; insert_sort (p, max); * /

/ * Test bubble sort * /

/ * P = a; insert_sort (p, max); * /

/ * Test rapid sort * /

/ * P = a; Quick_Sort (p, 0, max-1); * /

/ * Test Pile Sort * /

/ * P = a; heap_sort (p, max); * /

For (p = a, i = 0; i

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

9cbs

New Post(0)