Хорошая ссылочная карта / шпаргалка с основными алгоритмами сортировки в C? [закрытый]
Указатель NULL - это тот, который указывает на никуда. Когда вы разыскиваете указатель p, вы говорите «дайте мне данные в месте, хранящемся в« p ». Когда p является нулевым указателем, местоположение, хранящееся в p, является nowhere, вы говорите «Дайте мне данные в месте« нигде ». Очевидно, он не может этого сделать, поэтому он выбрасывает NULL pointer exception.
В общем, это потому, что что-то не было правильно инициализировано.
5 ответов
Я сделал это для моего друга, изучающего C, может быть, вы найдете это полезным:
#include <stdlib.h>
#include <string.h>
static void swap(int *a, int *b) {
if (a != b) {
int c = *a;
*a = *b;
*b = c;
}
}
void bubblesort(int *a, int l) {
int i, j;
for (i = l - 2; i >= 0; i--)
for (j = i; j < l - 1 && a[j] > a[j + 1]; j++)
swap(a + j, a + j + 1);
}
void selectionsort(int *a, int l) {
int i, j, k;
for (i = 0; i < l; i++) {
for (j = (k = i) + 1; j < l; j++)
if (a[j] < a[k])
k = j;
swap(a + i, a + k);
}
}
static void hsort_helper(int *a, int i, int l) {
int j;
for (j = 2 * i + 1; j < l; i = j, j = 2 * j + 1)
if (a[i] < a[j])
if (j + 1 < l && a[j] < a[j + 1])
swap(a + i, a + ++j);
else
swap(a + i, a + j);
else if (j + 1 < l && a[i] < a[j + 1])
swap(a + i, a + ++j);
else
break;
}
void heapsort(int *a, int l) {
int i;
for (i = (l - 2) / 2; i >= 0; i--)
hsort_helper(a, i, l);
while (l-- > 0) {
swap(a, a + l);
hsort_helper(a, 0, l);
}
}
static void msort_helper(int *a, int *b, int l) {
int i, j, k, m;
switch (l) {
case 1:
a[0] = b[0];
case 0:
return;
}
m = l / 2;
msort_helper(b, a, m);
msort_helper(b + m, a + m, l - m);
for (i = 0, j = 0, k = m; i < l; i++)
a[i] = b[j < m && !(k < l && b[j] > b[k]) ? j++ : k++];
}
void mergesort(int *a, int l) {
int *b;
if (l < 0)
return;
b = malloc(l * sizeof(int));
memcpy(b, a, l * sizeof(int));
msort_helper(a, b, l);
free(b);
}
static int pivot(int *a, int l) {
int i, j;
for (i = j = 1; i < l; i++)
if (a[i] <= a[0])
swap(a + i, a + j++);
swap(a, a + j - 1);
return j;
}
void quicksort(int *a, int l) {
int m;
if (l <= 1)
return;
m = pivot(a, l);
quicksort(a, m - 1);
quicksort(a + m, l - m);
}
struct node {
int value;
struct node *left, *right;
};
void btreesort(int *a, int l) {
int i;
struct node *root = NULL, **ptr;
for (i = 0; i < l; i++) {
for (ptr = &root; *ptr;)
ptr = a[i] < (*ptr)->value ? &(*ptr)->left : &(*ptr)->right;
*ptr = malloc(sizeof(struct node));
**ptr = (struct node){.value = a[i]};
}
for (i = 0; i < l; i++) {
struct node *node;
for (ptr = &root; (*ptr)->left; ptr = &(*ptr)->left);
a[i] = (*ptr)->value;
node = (*ptr)->right;
free(*ptr);
(*ptr) = node;
}
}
Необходимо определенно проверить страница Animated Sorting Algorithms . Это - удивительный ресурс для сортировки алгоритмов.
РЕДАКТИРОВАНИЕ Благодаря Петерино для новой ссылки!
Что вам нужно, так это книга Роберта Седжвика «Алгоритмы в Си».
http://www.amazon.com/Algorithms-C-paperback-Robert-Sedgewick/dp/0768682339/
Я бы, наверное, искал использованный. Новые стоят дорого (но все же стоят того).
Вообще говоря, люди не волнуются слишком много о различных алгоритмах, и многие люди пользуются стандартной библиотекой qsort() функция (который мог бы или не мог бы на самом деле использовать Quicksort) сделать их сортировку. Когда они не используют его, у них обычно есть более сложные требования. Это могло бы быть то, потому что им нужно к внешней сортировке (проливающий данные к диску), или по причинам, связанным с производительностью. Иногда, воспринятые издержки function-call-per-comparison, связанного с использованием qsort() (или, действительно, bsearch()), являются слишком большими. Иногда, люди не хотят рисковать потенциалом O (N^2) поведение худшего случая Quicksort, но большая часть производства qsort(), алгоритмы избегут этого для Вас.
Вполне кроме различных книг по алгоритмам - Sedgewick - один такой, но существуют многие другие - Вы могли также смотреть на "Программирование Jon Bentley Жемчуга" или "Большего количества книг" Жемчуга Программирования. Это было бы хорошо, так или иначе - они превосходны - но "Больше Жемчуга Программирования" также включает библиотеку простых алгоритмов, записанных в awk, включая вид вставки, пирамидальную сортировку и быструю сортировку. Это пропускает Пузырьковую сортировку, Вид Shell и BogoSort. Это также не включает Вид Основания.