• 大学C语言程序设计
  • chapter 9 排序&查找
    • 1. 排序认识
    • 2. 冒泡排序
    • 3. 选择排序
    • 4. 插入排序
    • 5. 快速排序
    • 6. 归并排序
    • 7. 计数排序
    • 8. 顺序查找
    • 9. 二分查找

大学C语言程序设计

chapter 9 排序&查找

1. 排序认识

排序是指：将一个无序数列，经过一些处理，变成一个有序数列（非降序列/非增序列）的过程。

也可以形象化描述为：对于任意 i=a[j].

当对于任意 i

当对于任意 i=a[j]，那么称数列 {a[i]} 是一个非增序列，或递减序列。

稳定排序：对于 i 换个说法就是：a[i]=a[j], 排序前 a[i] 在 a[j] 前面，排序后 a[i] 仍然在 a[j] 前面，两者的相对位置不变。

而对于排序的方法按照基本原理主要分两种：

1. 基于比较的排序方法：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序、希尔排序。

2. 非基于比较的排序方法：计数排序、基数排序、桶排序。

2. 冒泡排序

它重复地走访过要排序的数列，一次比较两个元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。

冒泡排序算法的运作如下：（从后往前）

1.比较相邻的元素。如果第一个比第二个大，就交换他们两个。

2.对每一对相邻元素作同样的工作，从开始第一对到结尾的最后一对。在这一点，最后的元素应该会是最大的数。

3.针对所有的元素重复以上的步骤，除了最后一个。

4.持续每次对越来越少的元素重复上面的步骤，直到没有任何一对数字需要比较。

//冒泡排序：最大的下沉到最后，小的向上冒泡 
void BubbleSort(int arr[], int l, int r){
    for(int i=r; i>=l; i--){
        for(int j=l; ja[j+1]) {
                int temp=a[j];
                a[j]=a[j+1];
                a[j+1]=temp;
            }
        }
    }
}

3. 选择排序

初始时在序列中找到最小（大）元素，放到序列的起始位置作为已排序序列；
然后，再从剩余未排序元素中继续寻找最小（大）元素，放到已排序序列的末尾。
以此类推，直到所有元素均排序完毕。

//选择排序：每次选择最大的放在最后
void SelectSort(int a[], int l, int r){
    for(int i=r; i>=l; i--){
        int maxi=i;
        for(int j=l; j

//插入排序：向左边有序序列中插入一个元素 
void InsertSort(int a[], int l, int r){
    for(int i=l; i<=r; i++){
        int k=i;
        for(int j=i; j>=l; j--){
            if(a[k]

//快速排序：取一个基准值，大的放右边，小的放左边
void QuickSort(int a[], int l, int r){
    if(l>=r) return;
    int i=l, j=r, mid=a[l];
    while(imid) j--;//从左向右找到第一个小于基准值的下标
        a[i]=a[j];
        while(i

//归并排序：分治思想，将数据递归均分成两部分，直到数据元素个数为1，在回溯合并
void merge(int a[], int l, int mid, int r);
void MergeSort(int a[], int l, int r){
    if(l>=r) return;
    int mid=(l+r)/2;
    MergeSort(a, l, mid);
    MergeSort(a, mid+1, r);
    merge(a, l, mid, r);
}
//合并：两个有序序列合并，需要开一个临时空间 temp[]
void merge(int a[], int l, int mid, int r){
    int i=l, j=mid+1, cnt=0;
    while(i<=mid && j<=r){
        if(a[i]

#include
#define N 10000
int arr[N];
int main(){
    int n, minn=10001, maxn=0; scanf("%d", &n);
    for(int i=1; i<=n; i++){
        int x; scanf("%d", &x);
        arr[x]++;
        if(minn>x) minn=x;
        if(maxn

int binSearch(int arr[], int l, int r, int x){
    while(l<=r){
        int mid = (l+r)/2;
        if(x < arr[mid]) r=mid-1;
        else if(x > arr[mid]) l=mid+1;
        else if(x == arr[mid]) return mid;
    }
    return 0;
}