一、排序的基本概念
1、什么是排序？
排序是指把一组数据以某种关系（递增或递减）按顺序排列起来的一种算法。例如：数列 8、3、5、6、2、9、1、0、4、7递增排序后 0、1、2、3、4、5、6、7、8、9递减排序后 9、8、7、6、5、4、3、2、1、0
2、排序的过程
排序的过程中需要进行如下两种基本操作：（1）比较两个数据的大小；（2）移动两个数据的位置。
3、排序算法
排序算法按照其实现的思想和方法的不同，可以分为许多种。我们比较常用的排序算法有：
交换类排序：冒泡排序、快速排序
插入类排序： 直接插入排序、希尔排序（缩小增量排序）
选择类排序：简单选择排序、堆排序归并排序基数排序
二、冒泡排序
冒泡排序的规则：n个数据进行冒泡排序，首先将第一个数据和第二个数据进行比较，如果为逆序就交换两个数据的值，然后比较第二个和第三个数据，依此类推，直到第最后一个和倒数第二个比较完了为止。上述过程为冒泡排序的第一趟冒泡排序，其结果是最大或者最小的数据被放置在末尾的位置。然后进行第二趟排序，把第二大或者第二小的数放置在倒数第二的位置，之后每一趟排序都会使一个数据有序，直到此序列的全部数据都有序为止。冒泡排序的演示示例：
void BubbleSort(int x[],int n)//冒泡排序 { int i, j; for (i = 0;i<n-1;i++) for (j = 0; j <n-1-i; j++) { if (x[j] > x[j + 1]) { x[j] += x[j + 1]; x[j + 1] = x[j] - x[j + 1]; x[j] = x[j] - x[j + 1]; } } for (i=0;i<n;i++) printf("%d\t",x[i]); }
三、选择排序
对一个序列进行选择排序，首先通过一轮循环比较，从n个数据中找出最大或者最小的那个数据的位置，然后按照递增或者递减的顺序，将此数据与第一个或最后一个数据进行交换。然后再找第二大或者第二小的数据进行交换，以此类推，直到序列全部有序为止。选择排序与冒泡排序的区别在于，冒泡排序每比较一次后，满足条件的数据就交换，而选择排序是每次比较后，记录满足条件数据的位置，一轮循环过后再作交换。
选择排序的演示示例：
void SelectSort(int x[], int n)//选择排序 { int i, j, min,k; for (i = 0; i < n; i++) { min=i; for (j = i; j < n; j++) { if (x[min] > x[j]) min = j; } k = x[i]; x[i] = x[min]; x[min] = k; } for (i=0;i<n;i++) printf("%d\t",x[i]); }
四、查找的基本概念
我们常常需要在一个数列中查找我们所需要的数据，这里就需要用到查找算法了。
查找的目的，是在「已排序的数列」中寻找指定的数据，而当中顺序查找是最基本的查找算法，只要从数列的开头寻找到最后，看看是否找到指定数据即可。
常用的查找算法有顺序查找、折半查找。
五、顺序查找
顺序查找的基本思想：
从序列中的一端开始，逐个把需要查找的值与序列中的数据进行比较，如果找到一个数据与需要查找的数据值相等，则查找成功；如果整个序列中的数据都比较过，仍未找到需要查找的数，则说明此序列中不存在此数据，查找失败。
顺序查找的程序示例：
#define _CRT_SECURE_NO_WARNINGS #include <stdio.h> #include <stdlib.h> #include <time.h> //时间函数头文件 int main() { srand(time(NULL)); //随机数种子 int n = 1, m = 0, arr[100] = { 0 }, i = 0, index = -1; printf("请输入随机数的个数n（n<=100）："); scanf("%d", &n); for (i = 0; i < n; i++) { arr[i] = rand() % 100; //产生n个100以内的随机数，并存入数组 } for (i = 0; i < n; i++) { printf("%d\t", arr[i]); } putchar('\n'); printf("请输入要查找的数m："); scanf("%d", &m); //顺序查找Sequential search for (i = 0; i < n; i++) { if (arr[i] == m) { index = i; printf("此数在数组中下标为[%d]的位置出现！\n", index); } } if (index < 0) { printf("数组中未找到此数的位置！\n"); } system("pause"); return 0; }
六、折半查找（二分查找）
二分查找又称为折半查找，也就是对于一个已排序好的队列来说，利用它们已排序的特性，以减少比较的次数，这是查找的基本原则，二分查找是这个基本原则的代表。
在二分查找法中，从数列的中间开始查找，如果这个数小于我们所查找的数，由于数列已排序，则该数左边的数一定都小于要查找的数，所以无需浪费时间在左边的数；如果查找的数大于所查找的对象，则右边的数无需再查找，直接查找左边的数。 所以在二分查找法中，将数列不断的分为两个部份，每次从分割的部分中取中间数进行比较。
例如要查找92于以下的数列，首先中间数索引为(0+9)/2 = 4（索引由0开始）：
[3 24 57 57 67 68 83 90 92 95]
由于67小于92，所以转查找右边的数列：
3 24 57 57 67 [68 83 90 92 95
由于90小于92，再查找右边的数列，这次就找到所要的数了：
3 24 57 57 67 68 83 90 [92 95]
二分查找的程序示例：
int Binary_Search(int arr[], int size, int findVal) { //准备区间 int left = 0, right = size - 1; int mid; //开始搜索 while (left<=right) { //第一步 确定mid mid = ((right - left) >> 1) + left; //细节处理数据溢出 //第二步 比较 if (findVal == arr[mid]) return mid; //第三步 收缩区间 if (arr[mid] > findVal)//前半 right = mid - 1; if (arr[mid] < findVal)//前半 left = mid + 1; } //循环结束了 说明元素不存在 return -1; }
