数据结构—查找与排序算法（c语言版）_数据结构查找和排序算法c语言

查找算法声明

排序算法声明

代码实现

查找算法

//顺序查找
bool Select_Seq(int A[], int n,int k) {
	for (int i = 0; i < n; i++) {
		if (A[i] == k) {
			return true;
		}
	}
	return false;
}

//折半查找
bool Select_Half(int A[], int n,int k) {
	int low = 0, high = n - 1, mid;
	while (low <= high) {
		mid = (low + high) / 2;
		if (A[mid] > k)
			high = mid - 1;
		else if (A[mid] < k)
			low = mid + 1;
		else
			return true;
	}
	return false;
}
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 Sort_Inssert(int A[], int n) {
	int num;
	int i, j;
	for (i = 1; i < n; i++) {
		num = A[i];
		if (num < A[i - 1]) {
			for (j = i-1; num < A[j] && j>=0; j--) {
				A[j+1] = A[j];
			}
			A[j+1] = num;
		}
	}
}

//折半插入排序
void Sort_Insert_Half(int A[], int n) {
	int low,high, mid, num;
	for (int i = 1; i < n; i++) {
		num = A[i];
		low = 0; high = i - 1;
		while (low <= high) {
			mid = (low + high) / 2;
			if (A[mid] > num)
				high = mid - 1;
			else
				low = mid + 1;
		}
		for (int j = i - 1; j >=low; j--) 
			A[j + 1] = A[j];
		A[low] = num;
	}
}

//希尔排序
void Sort_Shell(int A[], int n) {
	int num;//用来存储数据
	int i, j;
	for(int dk=n/2;dk>=1;dk/=2)
		for(i=dk;i<n;i++)
			if (A[i] < A[i - dk]) {
				num = A[i];
				for (j = i - dk; j >= 0 && num < A[j]; j -= dk)
					A[j + dk] = A[j];
				A[j + dk] = num;
			}
}

//交换值函数
//注意这里要用引用，否则不能影响外部调用参数
void Swap(int& a, int& b) {
	int k = a;
	a = b;
	b = k;
}
//冒泡排序，向后冒泡
void Sort_Bubble(int A[], int n) {
	bool flag;//用于判断是否已经有序,true表示已经有序
	for (int i = 0; i < n-1; i++) {
		flag = true;
		for (int j = 0; j < n-i-1; j++)
			if (A[j] > A[j + 1]) {
				flag = false;
				Swap(A[j], A[j + 1]);
			}
		if (flag == true)
			return;
	}
}

//快速排序一次定位
int _Partition(int A[], int low, int high) {
	int pivot = A[low];
	while (low < high) {
		while (low < high && A[high] >= pivot)
			high--;
		A[low] = A[high];
		while (low < high && A[low] <= pivot)
			low++;
		A[high] = A[low];
	}
	A[low] = pivot;
	return low;
}
//快速排序 ,不稳定算法
void Sort_Quick(int A[],int low,int high) {
	if (low < high) {
		int pivot = _Partition(A, low, high);
		Sort_Quick(A, low, pivot - 1);
		Sort_Quick(A, pivot + 1, high);
	}
}

//简单选择排序,不稳定算法
void Sort_Select(int A[], int n) {
	int min;
	for (int i = 0; i < n - 1; i++) {
		min = i;
		for (int j = i + 1; j < n; j++) 
			if (A[j] < A[min])
				min = j;
		if (min != i)
			Swap(A[min], A[i]);
	}
}

//大根堆一次调整
void Head_Adjust(int A[], int k, int len) {
	int num = A[k];
	for (int i = 2 * k+1; i < len; i =i* 2+1) {
		if (i < len && A[i] < A[i + 1]) 
			i++;
		if (num >= A[i])
			A[k] = num;
		else {
			A[k] = A[i];
			k = i;
		}
	}
	A[k] = num;
}
//建立大根堆
void Build_Max_Heap(int A[], int len) {
	for (int i = (len - 1) / 2; i >= 0; i--) {
		Head_Adjust(A, i, len);
	}
}
//堆排序
void Sort_Heap(int A[], int n) {
	Build_Max_Heap(A, n);
	for (int i = n - 1; i > 0; i--) {
		Swap(A[i], A[0]);
		Head_Adjust(A, 0, i - 1);
	}
}
//将数组的两部分合并成一部分
void Merge(int A[],int low,int mid,int high,int B[]) {
	for (int i = low; i <= high; i++)
		B[i] = A[i];
	int i = low, j = mid+1, k = low;
	while (i <= mid && j <= high) {
		if (B[i] <= B[j])
			A[k++] = B[i++];
		else
			A[k++] = B[j++];
	}
	while (i <= mid)A[k++] = B[i++];
	while (j <= high)A[k++] = B[j++];
}
//归并排序
void Sort_Merge(int A[], int low,int high,int B[]) {
	if (low < high) {
		int mid = (low + high) / 2;
		Sort_Merge(A, low, mid, B);
		Sort_Merge(A, mid + 1, high, B);
		Merge(A, low, mid, high, B);
	}
}
//归并排序测试函数
void Sort_Merge_Test(int A[], int n) {
	int* B = new int[n];
	int low = 0,high = n - 1;
	Sort_Merge(A, low, high, B);
}
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
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164