数据结构—查找与排序算法（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;
}

排序算法

//直接插入排序
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);
}

最后

以上就是阳光含羞草为你收集整理的数据结构—查找与排序算法（c语言版）的全部内容，希望文章能够帮你解决数据结构—查找与排序算法（c语言版）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。