C语言排序算法
1. 选择排序
- 升序即，将第一个元素与其他进行比较，要比第一个元素小的就交换，第一轮之后会得到最小元素，第二轮会第二个元素与其他进行比较，小的就交换，至到最后一轮比较交换结束之后就排序完在。
- 降序即，每次都找大的。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void select_sort() {
int number_list[] = {88,10,99,50,30,100,57,67,29};
int length = sizeof(number_list)/ sizeof(number_list[0]);
int tmp1;
for (int i = 0;i < length - 1; i ++) {
for (int j = i + 1; j <= length - 1;j ++ ) {
if (number_list[i] > number_list[j]) {
tmp1 = number_list[i];
number_list[i] = number_list[j];
number_list[j] = tmp1;
}
}
}
for (int k = 0; k < length;k ++) {
if (k != 0 && k % 3 == 0 ) {
printf("\n");
}
printf("%d ",number_list[k]);
}
}
|
2. 冒泡排序
- 升序，则从前面往后开始，依此比较相邻的两个元素的大小，较大的下沉，较小的上升。第一轮过
后，最大的元素就放在最后一位了。第二轮过后，次大的元素就放在倒数第二位了，之后依此类推。
- 降序，则从前面往后开始，依此比较相邻的两个元素的大小，较小的下沉，较大的上升。第一轮过
后，最小的元素就放在最后一位了。第二轮过后，次小的元素就放在倒数第二位了，之后依此类推。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| void bubble_sort() {
int number_list[] = {88,10,99,50,30,100,57,67,29};
int length = sizeof(number_list)/ sizeof(number_list[0]);
int tmp1;
for (int i = 0;i < length - 1;i ++) {
for (int j = 0;j < length - j - 1;j ++) {
if (number_list[j]>number_list[j+1]) {
tmp1 = number_list[j];
number_list[j] = number_list[j + 1];
number_list[j + 1] = tmp1;
}
}
}
for (int k = 0; k < length;k ++) {
if (k != 0 && k % 3 == 0 ) {
printf("\n");
}
printf("%d ",number_list[k]);
}
|
3.快速排序法
通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比另外一部分的所有数据都
要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数
据变成有序序列。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
| int run1224() {
int a[] = {88,10,99,50,30,100,57,67,29};
int len = sizeof(a)/ sizeof(a[0]);
quick_sort(a,0,len-1);
printList(a,len);
return 0;
}
void quick_sort(int* a,const int low,const int high) {
if (low < high) {
int h = high;
int j;
for (j = low;j < h;j++) {
if (a[j] > a[low]) {
for (; h > j; h --) {
if (a[h] < a[low]) {
a[j] += a[h];
a[h] = a[j] - a[h];
a[j]-=a[h];
break;
}
}
}
}
if (a[low] > a[h]) {
a[low] += a[h];
a[h] = a[low] - a[h];
a[low] -= a[h];
}
quick_sort(a,low,h-1);
quick_sort(a,h,high);
}
}
void printList(int *a, int len) {
for (int i = 0; i < len; i++) {
printf("%d ", a[i]);
}
printf("\n");
}
|
4. 直接插入排序法
每一步将一个待排序的元素,按其排序码的大小,插入到前面已经排好序的一组元素的适当位置上去,直到元素
全部插入为止。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
|
void direct_insert_sort_asc(int *number_list,int len) {
int temp;
for (int i = 0;i <= len - 1;i ++) {
temp = number_list[i];
for (int j = i - 1;j >= 0;j--) {
if (number_list[j] > temp) {
number_list[j+1] = number_list[j];
number_list[j] = temp;
}
}
}
printList(number_list,len);
}
void direct_insert_sort_desc(int *number_list, int len) {
int temp;
for (int i = 1; i < len; i++) {
temp = number_list[i];
int j;
for (j = i - 1; j >= 0 && number_list[j] < temp; j--) {
number_list[j + 1] = number_list[j];
}
number_list[j + 1] = temp;
}
printList(number_list, len);
}
|
C语言查找法
1. 顺序查找法
顺序查找又称线性查找，是最基本的查找方法。它的查找过程为：从第一个元素起，逐个与待查元素比较，
若与待查元素相等，则查找成功，返回待查元素在查找表中的位置；若与待查元素不等，则继续与
查找表中的下一个元素比较，直到查找结束为止。
1
2
3
4
5
6
7
8
9
|
int sequential_search(int *number_list,int len,int key) {
for (int i = 0;i < len;i ++) {
if (number_list[i] == key) {
return i;
}
}
return -1;
}
|
2. 二分查找法
二分查找法（Binary Search）又称折半查找法，它是一种在有序数组中查找特定元素的搜索算法。二分查找
法的基本思想是将待查元素与数组的中间元素进行比较，如果相等，则返回中间元素的索引；如果待查元素
小于中间元素，则在数组的左半部分继续查找；如果待查元素大于中间元素，则在数组的右半部分继续查找。重复这个过程，直到找到待查元素或查找范围为空。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
|
int binary_search(int *number_list,int len,int key) {
int low = 0;
int high = len - 1;
while (low <= high) {
int mid = (low + high) / 2;
if (number_list[mid] == key) {
return mid;
} else if (number_list[mid] > key) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return -1;
}
|
C语言栈
栈是一种后进先出（LIFO）的数据结构，它只允许在一端进行插入和删除操作。栈的基本操作包括压栈（Push）和弹栈（Pop）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| #include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int top;
} Stack;
void initStack(Stack *s) {
s->top = -1;
}
int isEmpty(Stack *s) {
return s->top == -1;
}
int isFull(Stack *s) {
return s->top == MAX_SIZE - 1;
}
void push(Stack *s, int value) {
if (isFull(s)) {
printf("Stack is full.\n");
return;
}
s->data[++s->top] = value;
}
int pop(Stack *s) {
if (isEmpty(s)) {
printf("Stack is empty.\n");
return -1;
}
return s->data[s->top--];
}
int main() {
Stack s; initStack(&s);
}
push(&s, 1);
push(&s, 2);
push(&s, 3);
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
printf("%d\n", pop(&s));
return 0;
}
|
C语言队列
队列是一种先进先出（FIFO）的数据结构，它只允许在一端进行插入操作，在另一端进行删除操作。队列的基本操作包括入队（Enqueue）和出队（Dequeue）。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| #include <stdio.h>
#include <stdlib.h>
#define MAX_SIZE 100
typedef struct {
int data[MAX_SIZE];
int front;
int rear;
} Queue;
void initQueue(Queue *q) {
q->front = 0;
q->rear = 0;
}
int isEmpty(Queue *q) {
return q->front == q->rear;
}
int isFull(Queue *q) {
return (q->rear + 1) % MAX_SIZE == q->front;
}
void enqueue(Queue *q, int value) {
if (isFull(q)) {
printf("Queue is full.\n");
return;
}
q->data[q->rear] = value;
q->rear = (q->rear + 1) % MAX_SIZE;
}
int dequeue(Queue *q) {
if (isEmpty(q)) {
printf("Queue is empty.\n");
return -1;
}
int value = q->data[q->front];
q->front = (q->front + 1) % MAX_SIZE;
return value;
}
int main() {
Queue q; initQueue(&q);
enqueue(&q, 1);
enqueue(&q, 2);
enqueue(&q, 3);
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
printf("%d\n", dequeue(&q));
return 0;
}
|
C语言链表
链表是一种动态数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的基本操作包括插入、删除和查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
| #include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
Node *createNode(int data) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
void insertNode(Node **head, int data) {
Node *node = createNode(data);
node->next = *head;
*head = node;
}
void deleteNode(Node **head, int data) {
Node *temp = *head;
Node *prev = NULL;
while (temp != NULL && temp->data != data) {
prev = temp;
temp = temp->next;
}
if (temp == NULL) {
printf("Node with data %d not found.\n", data);
return;
}
if (prev == NULL) {
*head = temp->next;
} else {
prev->next = temp->next;
}
free(temp);
}
void printList(Node *head) {
Node *temp = head;
while (temp != NULL) {
printf("%d ", temp->data);
temp = temp->next;
}
printf("\n");
}
int main() {
Node *head = NULL;
insertNode(&head, 3);
insertNode(&head, 2);
insertNode(&head, 1);
printList(head);
deleteNode(&head, 2);
printList(head);
return 0;
}
|
C语言树
树是一种非线性数据结构，它由一系列节点组成，每个节点包含数据和指向子节点的指针。树的基本操作包括插入、删除和查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
| #include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *left;
struct Node *right;
} Node;
Node *createNode(int data) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = data;
node->left = NULL;
node->right = NULL;
return node;
}
void insertNode(Node **root, int data) {
if (*root == NULL) {
*root = createNode(data);
return;
}
if (data < (*root)->data) {
insertNode(&(*root)->left, data);
} else {
insertNode(&(*root)->right, data);
}
}
void deleteNode(Node **root, int data) {
if (*root == NULL) {
printf("Node with data %d not found.\n", data);
return;
}
if (data < (*root)->data) {
deleteNode(&(*root)->left, data);
} else if (data > (*root)->data) {
deleteNode(&(*root)->right, data);
} else {
if ((*root)->left == NULL && (*root)->right == NULL) {
free(*root);
*root = NULL;
} else if ((*root)->left == NULL) {
Node *temp = *root;
*root = (*root)->right;
free(temp);
} else if ((*root)->right == NULL) {
Node *temp = *root;
*root = (*root)->left;
free(temp);
} else {
Node *temp = findMinNode((*root)->right);
(*root)->data = temp->data;
deleteNode(&(*root)->right, temp->data);
}
}
}
Node *findMinNode(Node *root) {
Node *temp = root;
while (temp->left != NULL) {
temp = temp->left;
}
return temp;
}
void printTree(Node *root) {
if (root == NULL) {
return;
}
printTree(root->left);
printf("%d ", root->data);
printTree(root->right);
}
int main() {
Node *root = NULL;
insertNode(&root, 5);
insertNode(&root, 3);
insertNode(&root, 7);
insertNode(&root, 2);
insertNode(&root, 4);
insertNode(&root, 6);
insertNode(&root, 8);
printTree(root);
deleteNode(&root, 4);
printTree(root);
return 0;
}
|
C语言图
图是一种非线性数据结构，它由一系列节点和边组成，每个节点可以与多个节点相连。图的基本操作包括插入、删除和查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
| #include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct Graph {
int numVertices;
Node **adjLists;
} Graph;
Node *createNode(int data) {
Node *node = (Node *)malloc(sizeof(Node));
node->data = data;
node->next = NULL;
return node;
}
Graph *createGraph(int numVertices) {
Graph *graph = (Graph *)malloc(sizeof(Graph));
graph->numVertices = numVertices;
graph->adjLists = (Node **)malloc(numVertices * sizeof(Node *));
for (int i = 0; i < numVertices; i++) {
graph->adjLists[i] = NULL;
}
return graph;
}
void addEdge(Graph *graph, int src, int dest) {
Node *newNode = createNode(dest);
newNode->next = graph->adjLists[src];
graph->adjLists[src] = newNode;
newNode = createNode(src);
newNode->next = graph->adjLists[dest];
graph->adjLists[dest] = newNode;
}
void printGraph(Graph *graph) {
int v;
for (v = 0; v < graph->numVertices; v++) {
Node *temp = graph->adjLists[v];
printf("\n Adjacency list of vertex %d\n ", v);
while (temp) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("\n");
}
}
int main() {
Graph *graph = createGraph(5);
addEdge(graph, 0, 1);
addEdge(graph, 0, 4);
addEdge(graph, 1, 2);
addEdge(graph, 1, 3);
addEdge(graph, 1, 4);
addEdge(graph, 2, 3);
addEdge(graph, 3, 4);
printGraph(graph);
return 0;
}
|
C语言堆
堆是一种特殊的树形数据结构，它满足堆属性，即每个节点的值都大于或等于（或小于或等于）其子节点的值。堆的基本操作包括插入、删除和查找。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
| #include <stdio.h>
#include <stdlib.h>
typedef struct Heap {
int *array;
int capacity;
int size;
} Heap;
Heap *createHeap(int capacity) {
Heap *heap = (Heap *)malloc(sizeof(Heap));
heap->array = (int *)malloc(capacity * sizeof(int));
heap->capacity = capacity;
heap->size = 0;
return heap;
}
void insert(Heap *heap, int data) {
if (heap->size == heap->capacity) {
printf("Heap is full\n");
return;
} else {
heap->array[heap->size] = data;
heap->size++;
int child = heap->size - 1;
while (child > 0) {
int parent = (child - 1) / 2;
if (heap->array[child] < heap->array[parent]) {
int temp = heap->array[child];
heap->array[child] = heap->array[parent];
heap->array[parent] = temp;
}
child = parent;
}
}
}
void delete(Heap *heap) {
if (heap->size == 0) {
printf("Heap is empty\n");
return;
} else {
heap->array[0] = heap->array[heap->size - 1];
heap->size--;
int parent = 0;
while (parent < heap->size) {
int leftChild = 2 * parent + 1;
int rightChild = 2 * parent + 2;
int min = parent;
if (leftChild < heap->size && heap->array[leftChild] < heap->array[min]) {
min = leftChild;
}
if (rightChild < heap->size && heap->array[rightChild] < heap->array[min]) {
min = rightChild;
}
if (min != parent) {
int temp = heap->array[min];
heap->array[min] = heap->array[parent];
heap->array[parent] = temp;
} else {
break;
}
parent = min;
}
}
}
void printHeap(Heap *heap) {
for (int i = 0; i < heap->size; i++) {
printf("%d ", heap->array[i]);
}
printf("\n");
}
int main() {
Heap *heap = createHeap(10);
insert(heap, 10);
insert(heap, 20);
insert(heap, 30);
insert(heap, 40);
insert(heap, 50);
printHeap(heap);
delete(heap);
printHeap(heap);
return 0;
}
|
