数组的常用算法介绍（数组元素查找、插入数组元素、删除数组元素、数组排序）

大家好，欢迎来到IT知识分享网。

目录

一、数组元素查找

二、插入数组元素

三、删除数组元素

四、数组排序

一、数组元素查找

查找算法是为了获得待查询元素在数组中是否存在在，如果存在其具体位置的信息。

最简单的方法就是从第一个元素开始依次与待查找的元素进行比较，如果相等就查找成功，输出元素及对应下标; 如果与所有元素都比较结束仍没有相等的元素，则输出“元素不存在”的提示信息。

【例】从键盘上输入n(≤n≤10)个整数作为数组a的元素值，再读人一个待查找的整数x，在a数组中查找入 如果存在输出它的下标，否则提示:”Not present! “

#include <stdio.h> #define SIZE 10 int find(int a[],int n,int x); /*函数声明*/ int main() { int array[SIZE], i = 0, n, x; int pos; do { printf("Please input n(1<=n<=%d):", SIZE); scanf("%d", &n); } while (n<1 || n>SIZE); /*保证读入的n满足1≤n≤SIZE*/ printf("Please input %d elements:", n); for (i = 0; i < n; i++) scanf("%d", &array[i]); /*读入数组元素*/ printf("Please input x be searched:"); scanf("%d", &x); /*读入待查找数据*/ pos = find(array, n, x); /*调用函数完成查找*/ if (pos < n) printf("value=%d,index=%d\n", x, pos); else printf("Not present!\n"); return 0; } /*函数功能:完成一维数组的查找算法 函数参数：3个形式参数分别对应于待查找的数组、数组的有效元素个数以及 待查找的值 函数返回值：返回查询结果，若查询成功，返回数组元素所在下标，不成功 则返回数组长度值n*/ int find(int a[], int n, int x) { int i = 0; while (i < n) /*循环条件为:如果未找到且未搜索完元素*/ { if (x == a[i]) /*如果查找成功，i的值正好是元素下标*/ break; i++; } return i; }

二、插入数组元素

插入是指在原有序列中插入一个新的值。有的时候是指定位置的插入，更多情况下是向有序 
数组中插入一个数组元素，使得插入后的数组仍保持原序。

插入算法的一般步骤如下：

1、定位:即确定新元素的插入位置。在给定插入位置的插入算法中该步骤可以省略;但是如果是向有序数组中插入，则首先必须寻找待插入的位置，即得到新元素插入的下标 i 。

3、插入：在下标为 i 的位置上插入新元素，即做一次赋值操作，将待插入数据赋值给下标为 i 的数组元素。

【例】整型数组a中的元素值已经按照非递减有序排列（非严格的递增，相邻两数可以相等），再读入一个待插入的整数x，将x插入数组中。使a数组中的元素仍然保持非递减有序排列。

#include <stdio.h> #define SIZE 7 void print(int a, int n); void insert(int a[], int n, int x); int main() { int array[SIZE] = {12, 23, 34, 45, 56, 67}; /*用6个递增数值初始化数组元素*/ int x; print(array ,SIZE - 1); /*输出插入前数组元素*/ printf("Please input x be inserted:\n"); scanf("%d", &x); /*读人待插入的值x*/ insert(array ,SIZE - 1,x ); /*插入*/ print(array, SIZE); /*输出插入后数组元素,长度加1*/ return 0; } /*函数功能: 完成一维数组的输出 函数参数: 两个形式参数分别表示待输出的数组、实际输出的元素个数 函数返回值:无返回值*/ void print(int a[], int n) { int i; printf("The array is:\n"); for (i = 0; i < n; i++) printf("%5d", a[i]); printf("\n"); } /*函数功能: 完成一维数组的插入算法 函数参数:3个形式参数分别对应于待指入的数组、现有元素个数、待插入元素 函数返回值:无返回值*/ void insert(int a[], int n, int x) { int i, j; for (i = 0; i < n && a[i] < x; i++); //注意，该语句到这里就已经结束了，因为已经有了一个； /*定位 : 查找待插入的位置i，循环停止时的i就是*/ for (j = n - 1; j >= i; j--) /*移位:用递诚循环移位，使下标元素可被覆盖*/ a[j + 1] = a[j]; a[i] = x; /*插入:数组的i下标元索值赋值为插入的x*/ }

三、删除数组元素

内存空间中的数据只能修改，不能“擦除”。所谓“删除”其实是通过将需要删除的元素“覆盖”完成的，也就是将待删除元素后面的元素依次赋值给前一个元素。

删除算法的一般步骤如下。

#include <stdio.h> #define SIZE 5 /*函数功能: 完成一维数组的输出 函数参数: 两个形式参数分别表示待输出的数组、实际输出的元素个数 函数返回值:无返回值*/ void print(int a[], int n) { int i; printf("The array is:\n"); for (i = 0; i < n; i++) printf("%5d", a[i]); printf("\n"); } /*函数功能: 完成从一维数组中删除特定元素 函数参数:3个形式参数分别对应于待删除的数组、现有元素个数、待删除的元素值 函数返回值:返回删除是否成功的标志，1表示成功，0表示待删除元素不存在*/ int delArray(int a[], int n, int x) { int i, j; int flag = 1;/*是否找到待删除元素的标志位，1找到，0未找到*/ for (i = 0; i < n && a[i] != x; i++); /*定位 : 查找待删除元素x是否存在，此处循环体为空语句*/ if (i == n)/*循环停止时如果i==n，则说明元素不存在*/ flag = 0; else { for (j = i; j < n - 1; j++)/* 前移，覆盖i下标元素*/ a[j] = a[j + 1]; } return flag; } int main() { int array[SIZE] = { 12, 23, 34, 45, 12 }; /*初始化数组元素*/ int x; print(array, SIZE); /*输出删除前的数组元素*/ printf("Please input x be inserted:\n"); scanf("%d", &x); /*读入待删除的值x*/ if (delArray(array, SIZE, x)) /*调用delArray函数删除元素x*/ print(array, SIZE - 1); else printf("can not delete x!\n");/*否则给出未删除的提示信息*/ return 0; } 

当然，这个程序有它的局限性，只能实现删除第1个值等于x的元素，如果存在多个与x值相同的元素要怎么改进方法呢？

【分析与解答】例题中的删除函数delArray在找到待删除的值为x的元素后，将后面的数组元素依次向前覆盖一次，数组有效长度减1。如果数组中存在多个值为x的元素，即找到第一个值为x的元素，完成覆盖后、应在该元素所在位置开始继续上述的查找、删除过程，直到所有元素全部遍历。参考程序如下:

#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #define SIZE 10 /*函数功能: 完成一维数组的输出 函数参数: 2个形式参数分别表示待输出的数组、实际输出的元素个数 函数返回值:无返回值*/ void print(int a[], int n) { int i; printf("The array is:\n"); for (i = 0; i < n; i++) printf("%5d", a[i]); printf("\n"); } /*函数功能: 完成从一维数组中删除特定元素 函数参数: 3个形式参数分别对应于待删除的数组、现有元素个数、待删除的元素值 函数返回值:返回删除的个数 */ int delArray2(int a[], int n, int x) { int i, j; int count = 0; /*存储删除的个数*/ for (i = 0; i < n - count; i++) //每删除一个数x.数组有效长度会减少一个* / { if (a[i] == x) { count++; for (j = i; j < n - count; j++) /*找到删除的x，把后续数组元素向前覆盖一个*/ a[j] = a[j + 1]; i--; /*前移的位置减1*/ } } return count; } int main() { int array[SIZE] = { 23,45,23,12,56,23,67,13,65,23 }; int x, count; print(array, SIZE); /*输出删除前的数组*/ printf("Please input x be deleted:\n"); scanf("%d", &x); count = delArray2(array, SIZE, x); /*调用 delArray删除元素 x，并返回删除的个数*/ if (count) print(array, SIZE - count); /*如果成功，输出删除后的数组元素*/ else printf("can notdelet x!\n"); return 0; }

四、数组排序

排序可以用很多种方法实现，我们先来介绍其中的一种——冒泡排序。

冒泡排序的算法思想是:

在排序过程中对元素进行两两比较,越小的元素会经由交换慢慢“浮”到数组的前面(低下标处)，像气泡一样慢慢浮起，由此得名。假设对长度为n的数组进行冒泡排序，算法可以描述如下：

【例】从键盘上输入n(1≤n<10)个整数，用冒泡法将元素按从小到大的顺序排房，然后输出排序后元素。

#include <stdio.h> #define SIZE 10 /*函数功能: 完成一维数组的输出 函数参数:表示待输出的数组、实际输出的元素个数 函数返回值:无返回值*/ void print(int a[], int n) { int i; printf("The array is:\n"); for (i = 0; i < n; i++) printf("%5d", a[i]); printf("\n"); } /*函数功能: 完成一维数组的冒泡排序算法 函数参数:两个参数分别是待排序数组及当前元素个数 函数返回值:无返回值*/ void BubbleSort(int a[], int n) { int i, j, temp; for (i = 0; i < n - 1; i++) /*共进行n-1趟排序*/ for (j = n - 1; j > i; j--) /*递减循环，从后往前比较*/ if (a[j] < a[j - 1]) /*两两比较，若后一个元素小则交换该组相邻元素*/ { temp = a[j - 1]; a[j - 1] = a[j]; a[j] = temp; } } int main() { int array[SIZE], i = 0, n; do { printf("Please input n(1<=n<=%d):", SIZE); scanf("%d", &n); } while (n<1 || n>SIZE); /*保证读入的n满足1≤n≤SIZE*/ printf("Please input %d elements:", n); for (i = 0; i < n; i++) scanf("%d", &array[i]); /*读入数组元素*/ BubbleSort(array, n); /*调用函数完成排序*/ print(array, n); return 0; }

当然，这个冒泡排序还可以更简化，上面这种方法是最容易理解的，写得最详细的，但是它的局限性就在于每次比较都要遍历整个数组，一共要遍历n-1趟，这样会使得整个代码的效率变得极低。

我们可以在这个代码的基础上可以这样优化：

1、将遍历的趟数减到最少，即增加一些代码，用来判断后续数据是否已经是顺序排好了，如果后续数据已然有序，那么我们可以直接退出排序，不必再进行遍历；

2、在1的基础上，再次简化代码，遍历数据时增加一个记忆点，使得下一次遍历的数据可以从记忆点开始，不用从头再来。

这两个优化后的冒泡排序的实现过程我已经写在另一篇关于排序方法的博客里了，链接如下：

https://mp.csdn.net/mp_blog/creation/editor/