算法

insert_sort.c

#include <stdio.h>

void insert_sort(int arr[], int n) {
  int tmp;
  for (int i = 1; i < n; i++) {
    int tmp = arr[i];
    for (int j = i - 1; j >= 0 && tmp < arr[j]; j--) {
      arr[j+1] = arr[j];
      arr[j] = tmp;
    }
  }
}

int main() {
  int arr[] = {6, 2, 3, 7, 5, 1};
  insert_sort(arr, 6);
  for (int i = 0; i < 6; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}

linkedlist.c

/* 单向链表 */
/*
linkedlist.h

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

typedef struct _llist_node
{
  int value;
  struct _llist_node *next;
} llist_node;

typedef struct _llist
{
  struct _llist_node *head;
} llist;

// Constructor & Destructor
llist_node *llist_node_create(int value);
llist *llist_create(llist_node *head);
void llist_destroy(llist *list);

// Operation
llist *llist_append(llist *list, llist_node *node); 
int llist_length(llist *list); // 求表长
llist *llist_remove(llist *list, int i); // 删除第i个位置元素
int llist_search(llist *list, int value); // 搜索某个元素在线性表中是否出现
llist_node *llist_get(llist *list, int i); // 访问线性表中第i个元素
void llist_loop(llist *list); // 遍历线性表
llist *llist_insert(llist *list, int i, llist_node *prenode); // 第i个位置插入元素
// 链表反转
llist_node *llistReverse(llist_node *head);
llist *llist_reverse(llist *list);

#endif
*/

#include "linkedlist.h"
#include <stdlib.h>
#include <stdio.h>

llist_node *llist_node_create(int value) {
  llist_node *node = malloc(sizeof(llist_node));
  if (node == NULL) {
    printf("Create linked list node failed! \n");
    return NULL;
  }
  node->value = value;
  node->next = NULL;

  return node;
}

llist *llist_create(llist_node *head) {
  if (head == NULL) {
    printf("Node is invalid. \n");
    return NULL;
  }
  llist *list = malloc(sizeof(llist));
  if (list == NULL) {
    printf("Create linked list failed! \n");
    return NULL;
  }
  list->head = head;
  return list;
}

void llist_destroy(llist *list) {
  if (list == NULL) {
    printf("List is not exist. \n");
    return NULL;
  }
  if (list->head != NULL) {
    llist_node *node = list->head;
    llist_node *next;

    // free every nodes
    while (node != NULL) {
      next = node->next;
      free(node);
      node = next;
    }
  }
  free(list);
}

llist *llist_append(llist *list, llist_node *node) {
  if (list == NULL){
    printf("List is not exist. \n");
    return NULL;
  }
  if (node == NULL) {
    printf("Node is invalid. \n");
    return NULL;
  }
  if (list->head == NULL) {
    printf("List is empty. \n");
    return NULL;
  }

  llist_node *next = list->head;
  while (next->next != NULL) {
    next = next->next;
  }
  next->next = node;
  return list;
}

int llist_length(llist *list) {
  if (list == NULL) {
    printf("List is not exist. \n");
    return NULL;
  }

  int length = 0;
  if (list->head != NULL) {
    llist_node *node = list->head;

    while (node != NULL) {
      length++;
      node = node->next;
    }
    return length;
  }
}

void llist_loop(llist *list) {
  if (list == NULL) {
    printf("List is not exist. \n");
    return NULL;
  }

  int length = 0;
  if (list->head != NULL) {
    llist_node *node = list->head;

    while (node != NULL) {
      printf("%d ", node->value);
      node = node->next;
    }
    printf("\n");
  }
}

llist *llist_remove(llist *list, int i)
{
  if (list == NULL) {
    printf("List is not exist. \n");
    return NULL;
  }
  if (i > llist_length(list)) {
    printf("i beyond list's length. \n");
    return NULL;
  }

  int count = 0;
  if (list->head != NULL) {
    llist_node *node = list->head;
    llist_node *prv_node;
    llist_node *next_node;

    while (count < i - 1) {
      prv_node = node;
      node = node->next;
      next_node = node->next;
      count++;
    }

    if (next_node != NULL) {
      prv_node->next = next_node;
    } else {
      prv_node->next = NULL;
    }
    free(node);
  }
  return list;
}

int llist_search(llist *list, int value) {
  if (list == NULL) {
    printf("List is not exist. \n");
    return NULL;
  }

  if (list->head != NULL) {
    llist_node *node = list->head;

    while (node != NULL) {
      if (node->value == value) {
        return 1;
      }
      node = node->next;
    }
    return 0;
  }
}

llist_node *llist_get(llist *list, int i)
{
  if (list == NULL) {
    printf("List is not exist. \n");
    return NULL;
  }
  if (i > llist_length(list)) {
    printf("i beyond list's length. \n");
    return NULL;
  }

  int count = 0;
  if (list->head != NULL) {
    llist_node *node = list->head;

    while (count < i - 1) {
      node = node->next;
      count++;
    }
    return node;
  }
}

llist *llist_insert(llist *list, int i, llist_node *prenode) {
  if (list == NULL) {
    printf("List is not exist. \n");
    return NULL;
  }
  if (i > llist_length(list) + 1) {
    printf("i beyond list's length. \n");
    return NULL;
  }
  if (prenode == NULL) {
    printf("Node is not valid. \n");
    return NULL;
  }


  int count = 0;
  if (list->head != NULL) {
    llist_node *node = list->head;
    llist_node *next_node;

    while (count < i - 2) {
      node = node->next;
      next_node = node->next;
      count++;
    }

    node->next = prenode;
    if (next_node != NULL) {
      prenode->next = next_node;
    }
  }
  return list;
}

llist_node *llistReverse(llist_node *head) {
  if (head == NULL || head->next == NULL) {
    return head;
  } else {
    llist_node *newhead = llistReverse(head->next);
    head->next->next = head;
    head->next = NULL;
    return newhead;
  }
}

llist *llist_reverse(llist *list) {
  if (list == NULL) {
    printf("List is not exist. \n");
    return NULL;
  }
  if (list->head != NULL) {
    llist_node *head = llistReverse(list->head);
    list = llist_create(head);
    return list;
  }
}

quick_sort.c

#include <stdio.h>

/* 交换数组中的两个数 */
void swap(int *p, int *q)
{
  int temp = *p;
  *p = *q;
  *q = temp;
}

/* 将数组中的最后一个数作为主元，并按主元分区 */
/* 数组中小于住主元的数移动到数组最前面 */
/* 最后将主元移动到storeIndex的位置，使得主元将数组隔开 */
int partition(int a[], int l, int r)
{
  int pivotValue = a[r];
  int storeIndex = l;
  for(int i = l; i < r; i++)
  {
    if(a[i] <= pivotValue)
    {
      swap(&a[storeIndex], &a[i]);
      storeIndex++;
    }
  }
  swap(&a[r], &a[storeIndex]);
  return storeIndex;
}

/* 对分区的数组递归进行分区，实现排序 */
void quicksort(int a[], int l, int r)
{
  if (r > l)
  {
    int pivotNewIndex = partition(a, l, r);
    quicksort(a, l, pivotNewIndex - 1);
    quicksort(a, pivotNewIndex + 1, r);
  }
}

/* 通用接口 */
void quick_sort(int a[], int n)
{
  quicksort(a, 0, n - 1);
}

int main()
{
  int a[10] = {0, 1, 4, 5, 7, 3, 6, 8, 2, 9};
  quick_sort(a, 10);
  for(int i = 0; i < 10; i++)
  {
    printf("%d ", a[i]);
  }
}

select_sort.c

#include <stdio.h>

/*
 * 选择排序
 */
void select_sort(int arr[], int n) {
  for (int i = 0; i < n; i++) {
    /* 将第一个未排序数设定为最小值 */
    int min = arr[i];
    int idx = i;
    for (int j = i + 1; j < n; j++) {
      if (arr[j] < min) {
        /* 找到未排序数中的最小值，并记录位置 */
        min = arr[j];
        idx = j;
      }
    }
    /* 将最小值移动到已排序数末尾，并将末尾的数移到最小值的位置 */
    arr[idx] = arr[i];
    arr[i] = min;
  }  
}

int main() {
  int arr[] = {6, 4, 3, 7, 10, 2};
  select_sort(arr, 6);
  for (int i = 0; i < 6; i++) {
    printf("%d ", arr[i]);
  }
  printf("\n");
}