面试常用排序查找算法

文章目录

1 二分查找

定义两个变量left和right，分别表示数组的左边界和右边界，初始值分别为0和len - 1，其中len是数组的长度。
计算数组的中间位置mid，公式为(left + right) / 2，并判断数组中该位置的元素num[mid]是否等于目标值target。
如果相等，说明找到了目标值，返回mid作为结果。
如果不相等，比较num[mid]和target的大小，如果num[mid] < target，说明目标值在数组的右半部分，因此将左边界更新为mid + 1；如果num[mid] > target，说明目标值在数组的左半部分，因此将右边界更新为mid - 1。
重复步骤2到4，直到左边界大于右边界，这时说明数组中不存在目标值，返回-1作为结果。

二分查找算法的优点是查找速度快，时间复杂度为 $O (l o g n)$ ，其中n是数组的长度。缺点是要求数组必须是有序的，并且对于动态变化的数组不适用。

int BinarySearch(int num[],int target,int len)
{
    int left = 0, right = len - 1;
    while(left <= right)
    {
        int mid = (left + right) / 2;
        if(num[mid]==target)
        {
            return mid;
        }
        else if(num[mid] < target)
        {
            left = mid + 1;
        }
        else
        {
            right = mid - 1;
        }
    }
    return -1;
}

2 冒泡排序

定义一个变量i，表示数组中未排序的部分的最后一个元素的位置，初始值为length - 1，其中length是数组的长度。
从数组的第一个元素开始，依次比较相邻的两个元素，如果前一个元素num[j]大于后一个元素num[j+1]，则交换它们的位置，这样可以将较大的元素向后移动。
重复步骤2，直到遍历到数组中未排序部分的最后一个元素，这时可以确定该元素是数组中最大的元素，并将其排在正确的位置。
将变量i减一，表示数组中未排序部分的长度减少了一个元素，然后回到步骤2，继续进行比较和交换。
重复步骤2到4，直到变量i小于等于1，这时说明数组中所有的元素都已经排好序，算法结束。

冒泡排序算法的优点是简单易懂，不需要额外的空间。缺点是效率低，时间复杂度为 $O(n^2)$ ，其中n是数组的长度。

void BubbleSort(int num[],int length)
{
    for(int i=length-1;i>1;i--)
    {
        for(int j=0;j<i;j++)
        {
            if(num[j] > num[j+1])
            {
                int tmp = num[j+1];
                num[j+1] = num[j];
                num[j] = tmp;
            }
        }
    }
}

3 堆排序

定义一个函数MaxHeap，它的作用是将一个数组中的一部分元素调整为一个大根堆，即满足父节点的值大于等于子节点的值的二叉树。函数的参数有三个，分别是num表示数组，start表示调整的起始位置，end表示调整的结束位置。
在函数MaxHeap中，定义两个变量dad和son，分别表示当前要调整的父节点和子节点的位置，初始值分别为start和start * 2 + 1（因为数组下标从0开始，所以左子节点是父节点乘以2再加1）。
判断子节点是否在调整范围内，如果是，则继续执行以下步骤；如果不是，则说明已经调整完毕，返回。
如果存在右子节点，并且右子节点的值大于左子节点的值，则将子节点更新为右子节点（即选择较大的子节点）。
比较父节点和子节点的值，如果父节点的值大于等于子节点的值，则说明已经满足大根堆的性质，返回；如果不是，则交换父节点和子节点的值，并将父节点更新为原来的子节点，子节点更新为原来父节点的左子节点（即向下一层继续调整）。
重复步骤3到5，直到调整完毕或者返回。
定义一个函数HeapSort，它的作用是对一个数组进行堆排序。函数的参数有两个，分别是num表示数组，len表示数组的长度。
从数组中间位置开始，依次对每个元素执行函数MaxHeap，这样可以将整个数组调整为一个大根堆（即第一个元素是最大的元素）。
从数组最后一个元素开始，依次执行以下步骤：
- 交换第一个元素和当前元素的值，这样可以将最大的元素放在正确的位置。
- 对除了当前元素之外的其他元素执行函数MaxHeap，这样可以将剩余部分重新调整为一个大根堆（即第一个元素是剩余部分最大的元素）。
重复步骤9，直到只剩下第一个元素，这时说明数组中所有的元素都已经排好序，算法结束。

堆排序算法的优点是效率高，时间复杂度为 $O (n l o g n)$ ，其中n是数组的长度。缺点是需要额外的空间来存储堆结构，并且对于稳定性要求高的场合不适用。

void MaxHeap(int num[],int start,int end)
{
    int dad = start;
    int son = dad * 2 + 1;
    while(son <=end)
    {
        if((son+1<=end) && (num[son]<num[son+1]))
        {
            son++;
        }
        if(num[son]<num[dad])
        {
            return;
        }
        else
        {
            int tmp = num[dad];
            num[dad] = num[son];
            num[son] = tmp;
            dad = son;
            son = dad * 2 + 1;
        }
    }
}

void HeapSort(int num[],int len)
{
    for(int i=len/2-1;i>=0;i--)
    {
        MaxHeap(num,i,len-1);
    }
    for(int i=len-1;i>0;i--)
    {
        int tmp = num[0];
        num[0] = num[i];
        num[i] = tmp;
        MaxHeap(num,0,i-1);
    }
}

4 插入排序

定义一个变量i，表示当前要插入的元素的位置，初始值为1，表示从数组的第二个元素开始。
将当前要插入的元素num[i]保存在一个临时变量tmp中，以免被覆盖。
定义一个变量j，表示已经排好序的部分的最后一个元素的位置，初始值为i - 1。
比较已经排好序的部分的最后一个元素num[j]和要插入的元素tmp的大小，如果前者大于后者，则将前者向后移动一位，即将num[j]赋值给num[j+1]，并将j减一；如果不是，则说明找到了要插入的位置，跳出循环。
将要插入的元素tmp赋值给找到的位置，即将tmp赋值给num[j+1]。
将变量i加一，表示要插入下一个元素，并回到步骤2，继续进行比较和移动。
重复步骤2到6，直到变量i等于数组的长度，这时说明数组中所有的元素都已经排好序，算法结束。

插入排序算法的优点是简单易懂，对于部分有序或者数据量较小的数组效率较高。缺点是效率低，时间复杂度为 $O(n^2)$ ，其中n是数组的长度。

void InsertSort(int num[],int length)
{
    for(int i=1;i<length;i++)
    {
        int tmp = num[i];
        int j = i - 1;
        while((j>=0) && (num[j]>tmp))
        {
            num[j+1] = num[j];
            j--;
        }
        num[j+1] = tmp;
    }
}

5 快速排序

定义一个函数QuickSort，它的作用是对一个数组的一部分进行快速排序。函数的参数有三个，分别是num表示数组，start表示排序的起始位置，end表示排序的结束位置。
判断是否需要排序，如果起始位置大于等于结束位置，则说明已经排好序，返回；如果不是，则继续执行以下步骤。
定义两个变量i和j，分别表示当前要划分的部分的左边界和右边界，初始值分别为start和end。
选择数组中第一个元素num[i]作为基准值，并将其保存在一个临时变量basenum中，以免被覆盖。
从右边界开始，向左寻找一个小于基准值的元素，如果找到，则将其赋值给左边界位置；如果没有找到，则将右边界减一，继续寻找。
从左边界开始，向右寻找一个大于基准值的元素，如果找到，则将其赋值给右边界位置；如果没有找到，则将左边界加一，继续寻找。
重复步骤5和6，直到左边界和右边界相遇或者交叉，这时说明已经完成了一次划分，并将基准值赋值给相遇或者交叉的位置。
对基准值左边的部分递归地执行函数QuickSort，对基准值右边的部分递归地执行函数QuickSort。
重复步骤2到8，直到所有的部分都排好序，算法结束。

快速排序算法的优点是效率高，时间复杂度为 $O (n l o g n)$ ，其中n是数组的长度。缺点是不稳定，并且对于极端情况（如数组已经有序或者逆序）效率低。

void QuickSort(int num[],int start,int end)
{
    if(start >= end) return;
    int i = start;
    int j = end;
    int basenum = num[i];
    while(i<j)
    {
        //从右往左找小值
        while((i<j) && (num[j]>=basenum))
        {
            j--;
        }
        if(i<j)
        {
            num[i] = num[j];
            i++;
        }
        //从左往右找大值
        while((i<j) && (num[i]<basenum))
        {
            i++;
        }
        if(i<j)
        {
            num[j] = num[i];
            j--;
        }
        num[i] = basenum;
    }
    QuickSort(num,start,i-1);
    QuickSort(num,i+1,end);
}

6 选择排序

定义一个变量i，表示当前要选择的位置，初始值为0，表示从数组的第一个元素开始。
定义一个变量min，表示当前最小元素的位置，初始值为i。
从当前位置开始，向后遍历数组中的每个元素，如果发现有比当前最小元素更小的元素，则将其位置赋值给min，这样可以找到当前范围内最小的元素。
交换当前位置和最小元素的值，即将num[min]赋值给num[i]，将num[i]赋值给num[min]，这样可以将最小的元素放在正确的位置。
将变量i加一，表示要选择下一个位置，并回到步骤2，继续进行选择和交换。
重复步骤2到5，直到变量i等于数组的长度减一，这时说明数组中所有的元素都已经排好序，算法结束。

选择排序算法的优点是简单易懂，不需要额外的空间。缺点是效率低，时间复杂度为 $O(n^2)$ ，其中n是数组的长度。

void SelectSort(int num[],int length)
{
    for(int i=0;i<length-1;i++)
    {
        int min = i;
        for(int j=i;j<length;j++)
        {
            if(num[j]<num[min])
            {
                min = j;
            }
        }
        int tmp = num[min];
        num[min] = num[i];
        num[i] = tmp;
    }
}

7 希尔排序

定义一个变量gap，表示当前要排序的元素的间隔，初始值为数组的长度length。
计算新的间隔，公式为gap = gap / 3 + 1，这样可以逐渐减小间隔，直到为1。
对每个间隔进行以下步骤：
- 定义一个变量i，表示当前要排序的间隔的起始位置，初始值为0。
- 从当前位置开始，向后遍历数组中的每个间隔内的元素，如果发现有比前一个间隔内的元素更小的元素，则将其保存在一个临时变量tmp中，并执行以下步骤：
  - 定义一个变量k，表示已经排好序的部分的最后一个间隔内的元素的位置，初始值为当前位置减去间隔，即k = j - gap。
  - 比较已经排好序的部分的最后一个间隔内的元素num[k]和要插入的元素tmp的大小，如果前者大于后者，则将前者向后移动一个间隔，即将num[k]赋值给num[k+gap]，并将k减去间隔，继续比较；如果不是，则说明找到了要插入的位置，跳出循环。
  - 将要插入的元素tmp赋值给找到的位置，即将tmp赋值给num[k+gap]。
- 将变量i加一，表示要排序下一个间隔，并回到步骤3.2，继续进行遍历和插入。
重复步骤2和3，直到变量gap等于1，这时说明数组中所有的元素都已经排好序，算法结束。

希尔排序算法的优点是效率高于简单插入排序，时间复杂度为 $O(n^{1.3})$ ，其中n是数组的长度。缺点是不稳定，并且对于不同的间隔选择效率有影响。

void ShellSort(int num[],int length)
{
    int gap = length;
    do
    {
        gap = gap / 3 + 1;
        for(int i=0;i<gap;i++)
        {
            for(int j=gap+i;j<length;j+=gap)
            {
                if(num[j] < num[j-gap])
                {
                    int tmp = num[j];
                    int k;
                    for(k=j-gap;(k>=0) && (num[k]>tmp);k-=gap)
                    {
                        num[k+gap] = num[k];
                    }
                    num[k+gap] = tmp;
                }
            }
        }
    } while(gap>1);
}