顺序表处理

二分查找

二分查找原理

• 线性袁中的记录必须按关键码有序
• 必须采用顺序存储

基本思想

• 在有序表中，或中间记录作为比较对象，若给定值与中间记录的关键码相等，则查找成功；若给定值 小于中间记家的关键码，则在中间记灵的左半区继续查找；若给定值大于中间记录的关键码，则在中 间记录的右半区继续查找。不断重复上述过程，直到查找成功，或所查找的区域无记录，查找失购

二分查找举例

• 例如，考虑一个已经进行升序排列的整数序列，并且我们将要查找数字68：

• 我们对序列中目标值的位置感兴趣，因此我们把搜索空间看成序列的索引。

• 初始时，搜索空间包含从索引1到11。由于搜索的空间是一个区闻，它足够用来存储最低和最高两 个索引。正如上面所描述的，我们现在选择中间值，也就是萦引为6的值（1和11之间的中间点） 这个值是41，比目标值要小。

• 查找数字terage=68

  

  

  

  

• 二分查找流程图

#include "stdio.h"


int binarySearch(int array[], int targetNumber, int low, int high);
int main(){

    int array[] = {0, 4, 13, 19, 22, 41, 55, 68, 72, 81, 98};

    int targetNumber, result;

    int arrLength = sizeof(array)/sizeof(array[0]);
    printf("请输入在以下数组中要查找的数字：\n");

    for (int i = 0; i < arrLength; i++)
    {
        if(i != arrLength - 1)
            printf("%d ", array[i]);
        else
            printf("%d\n", array[i]);
    }
    scanf("%d", &targetNumber);

    result = binarySearch(array, targetNumber, 0, arrLength - 1);
    
    if (result == -1){
        printf("没有找到数字%d\n", targetNumber);
    }else{
        printf("找到了，%d是第%d个数字。\n",targetNumber, result);
    }






    return 0;
}

int binarySearch(int array[], int targetNumber, int low, int high){

    if (low > high){
        return -1;
    }

    int mid = (high + low)/2;

    if (array[mid] == targetNumber){
        return mid;
    }else if(array[mid] < targetNumber){
        low = mid + 1;
    }else{
        high = mid - 1;
    }
    return binarySearch(array, targetNumber, low, high);
}

小结

• 二分查找的前提条件 数据必须有序
• 二分查找的优势 比顺序查找速度快很多
• 二分查找可以解决的问题 查找数据 解决数学问题 解决几何问题

冒泡排序

冒泡排序的原理

• 冒泡排序和气泡在水中不断往上冒的情况有些类似。气泡大的（大的数搶，在下面，气泡小的小的数据）在上面。
• 冒泡排序的编程原理对存放原始数据的数组，按从前往后的方向进行多次扫描，每次扫描称为一趟。当戋现相祁两少数据的次序与排序要求的大小次序不符合时，即将这两个数据进行互换。这样，较小的数据就会逐个向前移动，好象气泡向上浮起一样。

冒泡排序的执行流程

• 例：用冒泡排序的方法将下面一组无序数组排成从小到大的顺序。

排成从小到大的顺序。

{49, 38, 65, 97, 76, 13, 27, 49}

• 分析：首先为了方便分析，我们把所给的数据先用一个表格列出来，如下：

原始数据和序号

第一次排序步骤：

问：为了使这一组无序数组完全按照要求排成从小到大，我们还需不需要再继续排序呢？

• 算法流程图
• 代码

#include "stdio.h"
#include "stdlib.h"

void printArray(int array[], int length);
void bubbleSort(int array[], int length);
int main(){

    int array[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int length = sizeof(array)/sizeof(array[0]);

    printf("待排序的数组是:");
    printArray(array, length);

    bubbleSort(array, length);

    printf("排序后的数组是:");
    printArray(array, length);    



    return 0;
}

void printArray(int array[], int length){
    for (int i = 0; i < length; i++)
    {
        if (i == 0)
            printf("%d", array[i]);
        else
            printf(" %d", array[i]);
    }
    printf("\n");
}
void bubbleSort(int array[], int length){
    
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            if (array[j] > array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }   
    }
}

//优化
void bubbleSort(int array[], int length){
    int flag = 0;
    for (int i = 0; i < length - 1; i++)
    {
        for (int j = 0; j < length - 1 - i; j++)
        {
            flag = 1;
            if (array[j] > array[j+1]){
                int temp = array[j];
                array[j] = array[j+1];
                array[j+1] = temp;
            }
        }
        if (!flag) break;
    }
}

冒泡排序的时间性能分析

选择排序

• 选择排序的主要操作是选择，其主要思想是：每趟排序在当前待排序房列中选出关键码最小的记录，添加到有序序列中。

选择排序的原理

• 基本思想：第i趟在n-i+l（i-1，2，n-1）个记录中选取关键码最小的记录作为有序序列中的第i个记录。 需要解决的关键问题？

  1. 如何在待排序序列中选出关键码最小的记录？ 解决方法： 定义一个整形变量min，用于记录在一趟比较的过程中关键码最小的记录位置。

     min = i;
     for(j=i+1;j<n;j++)
         if(r[j] < r[min])
             min = j;
     if(min != i)
         r[i]<-->r[index];
     

  2. 如何确定待排序列中关键码最小的记录在有序序列中的位置？

选择排序示例

#include "stdio.h"
#include "stdlib.h"

void printArray(int array[], int length);
void selectSort(int array[], int length);
int main(){

    int array[] = {49, 38, 65, 97, 76, 13, 27, 49};
    int length = sizeof(array)/sizeof(array[0]);

    printf("待排序的数组是:");
    printArray(array, length);

    selectSort(array, length);

    printf("排序后的数组是:");
    printArray(array, length);    



    return 0;
}

void printArray(int array[], int length){
    for (int i = 0; i < length; i++)
    {
        if (i == 0)
            printf("%d", array[i]);
        else
            printf(" %d", array[i]);
    }
    printf("\n");
}

void selectSort(int array[], int length){

    for (int i = 0; i < length - 1; i++)
    {
        int min = i;
        for (int j = i + 1; j < length - 1; j++)
        {
            if (array[min] > array[j]){
                min = j;
            }
        }
        if (i != min){
            int temp = array[i];
            array[i] = array[min];
            array[min] = temp;
        }
    }
}

选择排序的性能分析

插入排序

直接插入排序

基本思想：在插入第i（＞1）个记录时，前面的i-1个记录已经排好序。

• 需要解决的关键问题？

  1. 如何构造初始的有序序列？ 将第1个记录看成是初始有序表，然后从第2个记永起依次插人到这个有序表中，直到将笰n个记录插入。

     for(i = 2;i <= n;i++){
         //插入第i个记录，即第i趟直接插入排序
     }
     

  2. 如何查找待插入记录的插入位置？ 在i1个记录的有序区r(ll~rli-1]中插入记录r，首先顺序查找r的正确插入位置，然后将r插入到相 应位置。

     r[0]=r[i]; j=i-1;
     while(r[0] < r[j]){
         r[j+1] = r[j]
         j--;
     }
     r[j] = r[0]
     

直接插入排序的过程示例

#include "stdio.h"
#include "stdlib.h"

void printArray(int array[], int length);
void insertSort(int array[], int length);
int main(){

    int array[] = {0, 49, 38, 65, 97, 76, 13, 27, 49};
    int length = sizeof(array)/sizeof(array[0]);

    printf("待排序的数组是:");
    printArray(array, length);

    insertSort(array, length);

    printf("排序后的数组是:");
    printArray(array, length);    



    return 0;
}

void printArray(int array[], int length){
    for (int i = 1; i < length; i++)
    {
        if (i == 0)
            printf("%d", array[i]);
        else
            printf(" %d", array[i]);
    }
    printf("\n");
}

void insertSort(int array[], int length){

    for (int i = 2; i < length; i++)
    {
        array[0]  = array[i];
        int j  = i - 1;
        while(array[0] < array[j]){
            array[j+1] =  array[j];
            j--;
        }
        array[j+1] = array[0];
    }
    
}

直接插入排序算法性能分析

如何改进插入排序？

注意到，在插入第i(i＞1)个记录时，前面的以个记录已经排好序，则在寻找插八位置时，可以用二分（折半）查找来代替顺序查找，从而减少比较次数。

#include "stdio.h"
#include "stdlib.h"

void printArray(int array[], int length);
void insertSort2(int array[], int length);
int binarySearch(int array[], int target, int low, int high);

int main(){

    int array[] = {0, 1, 2, 1, 2};
    int length = sizeof(array)/sizeof(array[0]);

    printf("待排序的数组是:");
    printArray(array, length);

    insertSort2(array, length);

    printf("排序后的数组是:");
    printArray(array, length);    



    return 0;
}

void printArray(int array[], int length){
    for (int i = 1; i < length; i++)
    {
        if (i == 0)
            printf("%d", array[i]);
        else
            printf(" %d", array[i]);
    }
    printf("\n");
}


void insertSort2(int array[], int length){

    for (int i = 2; i < length; i++)
    {
        array[0]  = array[i];
        int target = binarySearch(array, array[i], 1, i - 1);
        int j;
        for(j = i - 1;j > target;j--)
            array[j+1] = array[j];
        array[j+1] = array[0];
    }
}

int binarySearch(int array[], int target, int low, int high){

    int mid = low + high >> 1;

    if (low > high){
        return mid;
    }

    if (target <  array[mid]){
         high = mid - 1;
    }else{
        low = mid + 1;
    }

    return binarySearch(array, target, low, high);
}