1.冒泡排序
冒泡排序是一种简单的排序算法，分为大数下沉和小数上浮两种。
冒泡排序步骤（大数下沉）：
1）比较相邻的元素。如果第一个比第二个大，就交换他们两个。
2）对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。这时，最后的元素就是最大的数。
3）针对所有的元素重复以上步骤，除了最后一个。
实例：输入一组数据，使用冒泡排序法进行排序，并输出。
#include <stdio.h>
// 冒泡排序
void maopao(int arr[],int len){
int temp;
for (int i =0; i < len -1; i ++) {
for (int j =0; j < len -1 - i ; j ++) {
if (arr[j] > arr[j + 1] ) {
temp = arr[j];
arr[j] = arr[j +1];
arr[j +1] = temp;
}
}
}
}
int main(int argc,constchar * argv[]) {
//定义并初始化一个数组
int a[6] = {21,23,8, 0, -98,7656};
//输出排序前的元素
for (int i =0; i <6; i ++) {
printf("%d\t", a[i]);
}
// 换行
printf("\n");
// 排序
maopao(a, 6);
//输出排序后的元素
for (int i =0; i <6; i ++) {
printf("%d\t", a[i]);
}
return 0;
}
2.选择排序
选择排序（selection sort）是一种简单直观的排序算法。它的工作原理如下：首先在未排序序列中找到最小元素，存放到排序序列中的起始位置，然后，再从剩余未排序元素中继续寻找最小元素，然后放到排序序列末尾。以此类推，直到所有元素均排序完毕。
选择排序需要两层循环，外层len - 1次，里层：j = i + 1, j < len 交换：if (a[i] > a[j])则交换a[i]和a[j]的值。
实例：输入一组无序数据，使用选择排序法进行排序，并输出。
#include <stdio.h>
// 定义选择排序函数
void selectionSort(int arr[],int len){
//定义变量，交换位置的时候用
int temp;
// 两层循环
for (int i =0; i < len - 1; i ++) {// 外层循环len - 1次
for (int j = i +1; j < len; j ++) { // 里层j = i +1 , j < len
if (arr[i] > arr[j]) { // 如果后面的元素比未排序的第一个元素小
// 则交换位置
temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}
}
}
int main(int argc,const char * argv[]) {
//定义并初始化一个数组
int a[6] = {23, -78,0, 5346, -5432,2333};
//输出排序前的数组
for (int i =0; i < 6; i ++) {
printf("%d\t",a[i]);
}
// 换行
printf("\n");
//使用选择排序法进行排序
selectionSort(a,6);
//输出排序后的数组
for (int i =0; i < 6; i ++) {
printf("%d\t",a[i]);
}
return 0;
}
3.折半查找
基本思路：在有序表中，取中间元素作为比较对象，若给定值与中间元素的值相等，则查找成功；若给定值小于中间元素，则在中间元素的左半区进行查找；若给定值打印中间元素，则在中间元素右半区继续查找。不断重复以上查找过程，直到查找成功，或所查找的区域无数据元素，查找失败。
代码实现1：输入一组有序数据，使用折半查找法查找一个数据，并输出其位置。
#include <stdio.h>
// 定义折半查找函数
int searchItem(int arr[],int len, int key){
//定义变量，存放元素位置
int low = 0,high = len -1,mid;
// 如果，low < high,循环
while (low <= high) {
// 计算mid位置
mid = (low + high) /2;
// 比较key和arr[mid]
// 如果key > arr[mid],low = mid + 1
if (key > arr[mid]) {
low = mid +1;
}
// 如果key < arr[mid],high = mid - 1
else if (key < arr[mid]) {
high = mid -1;
}
// 如果key == arr[mid],返回mid
else if (key == arr[mid]) {
return mid;
}
}
// 如果low > high,则查找不到，返回-1
return -1;
}
int main(int argc,const char * argv[]) {
//定义并初始化一个有序数组
int a[7] = {1,25, 38, 97, 122, 213,435};
//使用折半查找法查找数据
int p = searchItem(a, 7, 213);
// 输出其位置
printf("%d",p);
return 0;
}
代码实现2：输入一组有序数据，使用折半查找法插入一个数据，返回要插入数据的位置。
#include <stdio.h>
// 定义折半查找函数
int insertItem(int arr[],int len, int key){
//定义变量，存放元素位置
int low = 0,high = len -1,mid;
// 如果，low < high,循环
while (low <= high) {
// 计算mid位置
mid = (low + high) /2;
// 比较key和arr[mid]
// 如果key > arr[mid],low = mid + 1
if (key > arr[mid]) {
low = mid +1;
}
// 如果key < arr[mid],high = mid - 1
else if (key < arr[mid]) {
high = mid -1;
}
// 如果key == arr[mid],返回mid
else if (key == arr[mid]) {
return mid +1;
}
}
//如果low > high,则数组中不存在与要插入的值相同的值，返回-1
return low;
}
int main(int argc,const char * argv[]) {
//定义并初始化一个有序数组
int a[7] = {1,25, 38, 97, 122, 213,435};
//使用折半查找法插入数据
int p = insertItem(a,7, 212);
//输出要插入的位置
printf("%d",p);
return 0;
}