An example of the basic sorting algorithm in C language
- 2020-05-30 20:52:20
- OfStack
This paper illustrates the basic sorting algorithm of C in bucket sorting. I will share it with you for your reference as follows:
Bucket sort is an array a[n] with n integer elements, i for any value, 0 < = a[i] < = m special sorting algorithm.
n==m, n! = m. One thing to note when writing code is that a[i] accesses the i-1 element, not the i element.
/************************************************************************************/
/* Bucket_Sort.h Bucket sorting algorithm */
/* The problem: 1 a n An integer element a[0],a[1], ... ,a[n-1] Array sort, where 0 <= a[i] <= m, any i */
/* Program: the running time is O(m+n), The auxiliary space is O(m) */
/* when n=m , the running time is O(N), The auxiliary space is O(1) */
/************************************************************************************/
#include <vector>
/*m != n */
void Bucket_Sort_m(int *a, int n, int m)
{
std::vector<int> temp(m,0);
int i;
for(i = 0; i != n; ++i) // traverse a[]
++temp[a[i]-1]; // If there is a value corresponding to the subscript, mark as 1 , or for 0
i = 0;
for(int j = 1; j <= m; ++j) // traverse temp vector
if(temp[j-1]) a[i++] = j;
temp.clear();
}
/* m == n */
/* The end result is a[i-1] = i */
void Bucket_Sort(int *a,int n)
{
for(int i = 1; i <= n; ++i)
{
while(a[i-1] != i)
{
int temp = a[a[i-1]-1];
a[a[i-1]-1] = a[i-1];
a[i-1] = temp;
}
/* Pseudo code : If the hypothesis can pass a[i] Access the first part of the array i Elements, not the first i-1 a */
/*while(a[i] != i)
{
int temp = a[a[i]];
a[a[i]] = a[i];
a[i] = temp;
}
*/
}
}
I hope this article has been helpful to you in programming C.