3.6排序&查找

• 3.6排序&查找
  • 1. 排序认识
  • 2. 冒泡排序
  • 3. 选择排序
  • 4. 插入排序
  • 5. 快速排序
  • 6. 归并排序
  • 7. 计数排序
  • 8. 顺序查找
  • 9. 二分查找

1. 排序认识

排序是指将一个无序数列，经过一些处理，变成一个有序数列的过程。
有序序列也可以形象化描述为：
当对于任意 i, 有 a[i]<=a[i+1]，那么称数列 {a[i]} 是一个非降序列，或递增序列。
当对于任意 i, 有 a[i]>=a[i+1]，那么称数列 {a[i]} 是一个非增序列，或递减序列。
稳定排序：对于 i<j, 有 a[i]=a[j]，排序后仍然满足：i<j，则称排序为稳定排序。
换个说法就是：a[i]=a[j], 排序前 a[i] 在 a[j] 前面，排序后 a[i] 仍然在 a[j] 前面，两者的相对位置不变。

而对于排序的方法按照基本原理主要分两种：
基于比较的排序方法：冒泡排序，选择排序，插入排序，归并排序，堆排序，快速排序、希尔排序。
非基于比较的排序方法：计数排序、基数排序、桶排序。

2. 冒泡排序

它重复地走访过要排序的数列，一次比较两个相邻的元素，如果它们的顺序错误就把它们交换过来。走访数列的工作是重复地进行直到没有再需要交换，也就是说该数列已经排序完成。
假设要升序排序：也就是a[i]<=a[i+1]，那么如果出现 a[i]>a[i+1]的时候就交换。
（这个假设思想是一种反向思考问题的方式，很不错哦！）

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

3. 选择排序

初始时在序列中找到最大元素，放到序列的末尾位置作为已排序序列；
然后，再从剩余未排序元素中继续寻找最大元素，放到未排序序列的末尾。
以此类推，直到所有元素均排序完毕。
这里我们选择记录最大值所在下标，一次遍历完成后，对比下标是否发生变化，如果发生变化，就交换；（每一次比较后进行交换与冒泡相差无几，不推荐）

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

4. 插入排序

每步将一个待排序的纪录，按其关键码值的大小插入前面已经排序的文件中适当位置上，直到全部插入完为止。

//插入排序：向左边有序序列中插入一个元素 
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]<a[j]){
                swap(a[k], a[j]); k=j; //记录现在插入元素的位置
            }
        }
    }
}

5. 快速排序

快速排序是C.R.A.Hoare于1962年提出的一种划分交换排序。
它采用了一种分治的策略，通常称其为分治法(Divide-and-ConquerMethod)。
该方法的基本思想是：

1. 先从数列中取出一个数作为基准数。
2. 将比这个数大的数全放到它的右边，小于或等于它的数全放到它的左边。
3. 再对左右区间重复第二步，直到各区间只有一个数。

//快速排序：取一个基准值，大的放右边，小的放左边
void QuickSort(int a[], int l, int r){
    if(l>=r) return;
    int i=l, j=r, mid=a[l];
    while(i<j){
        while(i<j && a[j]>mid) j--;//从左向右找到第一个小于基准值的下标
        a[i]=a[j];
        while(i<j && a[i]<=mid) i++;//从右向左找到第一个大于基准值的下标
        a[j]=a[i];
    }
    a[i]=mid; QuickSort(a, l, i-1); QuickSort(a, i+1, r);//递归分区，就只有i排好序
}

6. 归并排序

归并排序(MERGE-SORT)是建立在归并操作上的一种有效的排序算法。
该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。
将已有序的子序列合并，得到完全有序的序列；
即先使每个子序列有序，再使子序列段间有序。
若将两个有序表合并成一个有序表，称为二路归并。
归并排序是一种稳定的排序方法。

//归并排序：分治思想，将数据递归均分成两部分，直到数据元素个数为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]<a[j]) temp[++cnt]=a[i++];
        else temp[++cnt]=a[j++];
    }
    while(i<=mid) temp[++cnt]=a[i++];
    while(j<=r)   temp[++cnt]=a[j++];
    for(int i=1; i<=cnt; i++) a[l++]=temp[i];
}

7. 计数排序

对各个元素出现次数进行计数，最后依次输出。（桶距为 1 时的桶排序）

int main(){
    int n, minn=2e9, 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<x) maxn=x; //最大值和最小值决定了桶的范围
    }
    for(int i=minn; i<=maxn; i++){
        while(arr[i]--) printf("%d ", i);
    }
    return 0;
}

8. 顺序查找

通过遍历无序数组，一个一个对比数组中的值与目标值是否相同。
对于数据没有任何要求，但是时间复杂度 O(n)。

9. 二分查找

二分查找是基于一个有序序列而言，使用二分查找前需要对该序列排序处理。
二分查找，又称折半查找，基本思想是将 n 个元素分成大致相等的两部分，
取a[n/2] 与 x 做比较，如果 x=a[n/2]，则找到 x，算法中止；
如果 x<a[n/2]，则只要在数组a的左半部分继续搜索 x，
如果 x>a[n/2]，则只要在数组a的右半部搜索 x。

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 -1; //未找到
}

由于冒泡排序/选择排序/插入排序的时间复杂度均为O(n^2)，一般不使用。
快速排序的时间复杂度为O(nlogn)，快是快，但不稳定且会被卡，不过sort挺好。
归并排序的时间复杂度为O(nlogn)，快且稳定，推荐。
计数排序，对数据范围大小要求很高，不过计数思想要掌握。
顺序查找枚举暴力的首选，其外无用；二分查找神器，有趣的思想，一定要会。

总结：解决题目时，可以使用sort（内部封装快排），但是注意要不要稳定排序，可以结合结构体实现稳定排序。但是不要认为sort天下第一，毕竟别人写的不如自己的，归并神器要会。其余O(n^2)的排序掌握原理，自己能实现即可。