6.Сортировка массива
ЗАДАЧА СОРТИРОВКИ МАССИВА
Отсутствие порядка существенно затрудняет поиск. А как можно достичь порядка? Сортировкой. Именно облегчение последующего поиска является главной причиной, по которой производится сортировка.
Пузырьком
#define SWAP(A, B) { int t = A; A = B; B = t; }
void bubblesort(int *a, int n)
{
int i, j;
for (i = n - 1; i >= 0; i--)
{
for (j = 0; j < i; j++)
{
if (a[j] > a[j + 1])
SWAP( a[j], a[j + 1] );
}
}
}
Вставкой
void intsertionsort(int *a, int n)
{
int i, j, temp;
for (i = 1; i < n; i++)
{
temp = a[i];
for (j = i - 1; j >= 0; j--)
{
if (a[j] < temp)
break;
a[j + 1] = a[j];
a[j] = temp;
}
}
}
Выбором
void selectionsort(int *a, int n)
{
for (int i = 0; i < n - 1; i++) {
/* устанавливаем начальное значение минимального индекса */
int min_i = i;
/* находим индекс минимального элемента */
for (int j = i + 1; j < n; j++) {
if (a[j] < a[min_i]) {
min_i = j;
}
}
/* меняем значения местами */
int temp = a[i];
a[i] = a[min_i];
a[min_i] = temp;
}
}
7.Быстрые алгоритмы сортировки
Разделяй и властвуй (англ. divide and conquer) в информатике — важная парадигма разработки алгоритмов, заключающаяся в рекурсивном разбиении решаемой задачи на две или более подзадачи того же типа, но меньшего размера, и комбинировании их решений для получения ответа к исходной задаче; разбиения выполняются до тех пор, пока все подзадачи не окажутся элементарными.
Быстрая сортировка
double * quicksort(double *s, int low, int hi)
{
double cnt, aux;
int i, j;
if (hi>low)
{
i = low;
j = hi;
cnt = s[i];
while (i < j)
{
if (s[i + 1] <= cnt)
{
s[i] = s[i + 1];
s[i + 1] = cnt;
i++;
}
else
{
if (s[j] <= cnt)
{
aux = s[j];
s[j] = s[i + 1];
s[i + 1] = aux;
}
j--;
}
}
quicksort(s, low, i - 1);
quicksort(s, i + 1, hi);
}
return(s);
}
Слиянием
void merge(int *a, int left, int mid, int right)
{
int *t = (int*)malloc((right - left + 1)*sizeof(int));
int i = left;
int j = mid;
int k = 0;
while (i < mid && j <= right)
{
if (a[i] < a[j])
{
t[k++] = a[i++];
}
else
{
t[k++] = a[j++];
}
while (i < mid)
{
t[k++] = a[i++];
}
while (j <= right)
{
t[k++] = a[j++];
}
for (k = 0; k < right - left + 1; ++k)
{
a[left + k] = t[k];
}
free(t);
}
}
void mergesort(int *a, int left, int right)
{
if (left >= right)
{
return;
}
int mid = (left + right) / 2 + 1;
mergesort(a, left, mid - 1);
mergesort(a, mid, right);
merge(a, left, mid, right);
}
Сортировка подсчётом
#define M 1000000
void countsort(int *a, int n)
{
int *count = (int*)malloc(M*sizeof(int));
for (int j = 0; j < M; ++j)
{
count[j] = 0;
}
for (int i = 0; i < n; ++i)
{
++count[a[i]];
}
int i = 0;
for (int j = 0; j < M; ++j)
{
for (int k = 0; k < count[j]; ++k)
{
a[i++] = j;
}
}
free(count);
}
8. Бинарный поиск
Бинарный поиск – для отсортированных массивов
int binary_search(int *a, int n, int k)
{
int left = 0;
int right = n - 1;
while (left < right)
{
int mid = (left + right) >> 1;
if (k <= a[mid])
{
right = mid;
}
else
{
left = mid + 1;
}
return (a[left] == k? left : -1)
}
int left = 0;
int right = 0;
int ans = -1;
while (left <= right)
{
int mid = ((left + right) >> 1);
if (k <= a[mid])
{
ans = mid;
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return (a[ans] == k ? left : -1);
}
int binary_search(int*a; int n; int k)
{
int left = 0;
int right = n - 1;
int ans = 1;
while (left <= right)
{
int mid = ((left*right) >> 1);
if (a[mid] == k)
{
ans = mid;
right = mid - 1;
}
else
{
left = mid + 1;
}
}
return ans;
}
Корень.
int sqrt(long long n)
{
long long left = 0;
long long right = n;
while (left < right)
{
long long mid = ((left+right)>>1)
if (mid*mid <= n)
{
left = mid;
}
else
{
right = mid - 1;
}
}
return left;
}