二分查找

int binary_search8(int* arr,int l,int r,int value){
	if(l>r){
		return -1;
	}
	int mid = (l+r)>>1;
	if(arr[mid] == value){
		//为了找最左边匹配元素的索引
		int pos = mid;
		while(l<=pos && arr[pos] == arr[mid]){
			pos--;
		}

		return pos+1;
	}

	if(arr[mid] > value){
		return binary_search8(arr,l,mid-1,value);
	}
	if(arr[mid] < value){
		return binary_search8(arr,mid+1,r,value);
	}
}

---

快排

void quicksort11(int* arr,int l ,int r){
	if(l>=r){
		return;
	}
	int i = l;
	int j = r;
	int mid = arr[(l+r)>>1];
	while(i<j){
		while(arr[i] < mid){
			i++;
		}
		while(arr[j] > mid){
			j--;
		}
		if(i<=j){
			std::swap(arr[i],arr[j]);
			i++;
			j--;
		}
	}
	quicksort11(arr,l,j);
	quicksort11(arr,i,r);
}

---

插入排序

void insert_sort3(int* arr ,int n){
	for(int i = 1;i<n;i++){
		int key = arr[i];
		int j = i-1;
		while(j >=0 && arr[j] > key){
			arr[j+1] = arr[j];
			--j; 
		}
		arr[j+1] =key;
	}

}

---

冒泡排序

void bubble_sort3(int* arr,int n){
	for(int i = 0;i<n;i++){
		for(int j = i+1;j<n;j++){
			if(arr[i]>arr[j]){
				swap(arr[i],arr[j]);
			}
		}
	}
}

---

选择排序

void select_sort2(int* arr,int n){
	for(int i = 0;i<n;++i){
		int min = i;
		for(int j = i+1;j<n;++j){
			if(arr[min] > arr[j]){
				min = j;
			}
		}
		swap(arr[i],arr[min]);
	}
}

---

堆排序

void heapify5(int *arr, int n, int i)
{
	int l = i * 2 + 1;
	int r = i * 2 + 2;
	int max = i;
	if (r < n && arr[max] < arr[r])
	{
		max = r;
	}
	if (l < n && arr[max] < arr[l])
	{
		max = l;
	}
	if (max != i)
	{
		swap(arr[max], arr[i]);
		heapify4(arr, n, max);
	}
	return;
}

void heap_sort5(int *arr, int n)
{
	if (n <= 1)
	{
		return;
	}
	// 建堆
	int last_index = n / 2 - 1;
	for (int i = last_index; i >= 0; --i)
	{
		heapify5(arr, n, i);
	}
	// 排序
	for (int i = n - 1; i >= 0; --i)
	{
		swap(arr[0], arr[i]);
		heapify5(arr, i, 0);
	}
}

---

归并排序

void merge2(int* arr,int l ,int mid,int r ){
    int j = mid+1;
    int m = l;
    int* temp = new int[r-l+1];
    int n = 0;
    while(l<=mid &&  j<=r){
        if(arr[l] < arr[j]){
            temp[n] = arr[l]; 
            n++;
            l++;
        }else{
            temp[n] = arr[j]; 
            n++;
            j++;
        }
    }
    while(l <= mid){
        temp[n] = arr[l];
        n++;
        l++;
    }
    while(j <= r){
        temp[n] = arr[j];
        n++;
        j++;
    }
    for(int i=0;i<n;i++){
        arr[i+m] = temp[i];
    }
    delete temp;
}

void mergeSort2(int* arr,int l, int r){
    if(l>=r){
        return;
    }
    int mid = (l+r)/2;
    mergeSort2(arr,l,mid);
    mergeSort2(arr,mid+1,r);
    merge2(arr,l,mid,r);
}

---

基数排序

void stable_counting_sort(int* arr,int n){
    int min = arr[0];
    int max = arr[0];
    for(int i=0;i<n;++i){
        if(arr[i] < min){
            min = arr[i];
        }
        if(arr[i] > max){
            max = arr[i];
        }
    }

    int* temp = new int[max+1]{0};

    //计数
    for(int i=0;i<n;++i){   
        temp[arr[i]]++;
    }

    int k = 0;
    for(int i=min;i<=max;++i){ 
        while (temp[i]>0)
        {
           arr[k++] = i;
           temp[i]--;
        }
          
    }
}

---

排序测试框架

int main()
{
	int num = 1000;
	srand(time(0));
	int *arr = new int[num];
	for (int i = 0; i < num; i++)
	{
		arr[i] = rand() % num + 1;
	}
    cout << "开始排序\n";
	排序算法(arr, num);
	cout << "检查是否正确排序\n";
	int max = arr[0];
	for (int i = 0; i < num; i++)
	{
		if (arr[i] < max)
		{
			break;
		}
		else
		{
			max = arr[i];
		}
		cout << arr[i] << " ";
	}
	if (max != arr[num - 1])
	{
		cout << "\n"<< "排序失败"<< "\n";
	}
	else
	{
		cout << "排序成功\n\n";
	}
	return 0;
}