排序算法知识点和常见面试题

我好想睡觉啊 / 2023-09-04 / 原文

查找和排序算法知识点和常见面试题

查找

二分查找

1.low high两个指针分别指向数组头和尾
2.mid = (low + high) / 2,并将nums[mid]与target比较
3.如果相等，返回；如果小于，则low移动；如果大于，则high移动
4.否则返回-1

int binary_search(int array[], int value, int size)
{
    int low = 0;
    int high = size -1;
    int mid;
    while(low <= high)
    {
        mid = (low + high) / 2;     // 二分
        if(array[mid] == value)     // 中间数据是目标数据
            return mid;
        else if(array[mid] < value) // 中间数据比目标数据小
            low = mid + 1;
        else   // 中间数据比目标数据大
            high = mid - 1;
    }
    return -1;
}

class Solution {
public:
    int search(vector<int>& nums, int target) {
        int low = 0;
        int high = nums.size()-1;
        while(low <= high){
            int middle = (low + high) / 2; //int middle = left + ((right - left) / 2);//防止溢出

            if(nums[middle] < target){
                low =  middle + 1;
            }
            else if(nums[middle] > target){
                high = middle - 1;
            }
            else
                return middle;
        }
        return -1;
    }
};

排序算法知识点

冒泡排序

插入排序

选择排序

快速排序

二分思维+递归思维

# include <stdio.h>

int FindPos(int * a, int low, int high);
void QuickSort(int * a, int low, int high);

int main(void)
{
	int a[6] = {-2, 1, 0, -985, 4, -93};
	int i;

	QuickSort(a, 0, 5); //第二个参数表示第一个元素的下标  第三个参数表示最后一个元素的下标
	
	for (i=0; i<6; ++i)
		printf("%d  ", a[i]);
	printf("\n");

	return 0;
}

void QuickSort(int * a, int low, int high)
{
	int pos;

	if (low < high)
	{
		pos = FindPos(a, low, high);
		QuickSort(a, low, pos-1);
		QuickSort(a, pos+1, high);
	}	
}

int FindPos(int * a, int low, int high)
{
	int val = a[low];

	while (low < high)
	{
		while (low<high  && a[high]>=val)
			--high;
		a[low] = a[high];

		while (low<high && a[low]<=val)
			++low;
		a[high] = a[low];
	}//终止while循环之后low和high一定是相等的

	a[low] = val; 

	return high; //high可以改为low, 但不能改为val 也不能改为a[low]  也不能改为a[high]
}