排序与查找

int Sequential_Search(int *a,int n,int key)    //a为数组，n为要查找数组长度，key为待查找关键词
{
    int i;
    for(i = 1;i <= n;i++)    //遍历数组内的每一条记录,元素记录是从1开始
    {
        if(a[i] == key)    //如果查找到，则返回记录所在位置
            return i;
    }
    return 0;    //如果未查找到，则返回0
}

int a[N];
int ans;
for(int i = 1;i<N;i++){
    if(a[i] == ans) return true;
  else break;
}
if(a[N]!=ans) return false;

//1.定义双指针维护区域
l = -1,r = N; // 这里的数组是0-n-1的
while(l+1!=r) //l+1 = r的时候说明红蓝区域相融了
{
    m = (l+r)/2;
    // 2.如果m节点是蓝色节点
    if(isBlue(m)) l = m; // m节点是蓝色节点，其左侧都是蓝色
    else r = m; // m是红色节点，其右侧都是红色
}

return l or r // 最终找到的位置处，需要区分

#include <iostream>
#include <vector>
// 判断蓝色区域，反之就是红色区域
bool isBlue(const std::vector<int>& array, int m, int ans) {
  return array[m] < ans;
}
// 目的是填色找到《红蓝边界》
int binarySearch(const std::vector<int>& array, int ans) {
    int l = -1, r = array.size();

    while (l + 1 != r) {
        int m = (l + r) / 2;

        if (isBlue(array, m, ans)) {
            l = m;  // m左边都是蓝色
        } else {
            r = m;  // m右边都是红色
        }
    }

    return r;// 第一个大于或等于ans的元素，是红色
}

int main() {
    std::vector<int> array = {2,3,4,5,5,5,5,5,6}; // Sorted array
    int ans = 5; // The target value

    int index = binarySearch(array, ans);
    if (index != -1) {
        std::cout << "找到了值第一个>= " << ans << " 位置是: " << index
                  << " (值是: " << array[index] << ")" << std::endl;
    } else {
        std::cout << "找不到或者是输入有误" << ans << std::endl;
    }

    return 0;
}

#include <iostream>
#include <vector>
// 判断蓝色区域，反之就是红色区域
bool isBlue(const std::vector<int>& array, int m, int ans) {
  return array[m] < ans;
}
// 目的是填色找到《红蓝边界》
int binarySearch(const std::vector<int>& array, int ans) {
    int l = -1, r = array.size();

    while (l + 1 != r) {
        int m = (l + r) / 2;

        if (isBlue(array, m, ans)) {
            l = m;  // m左边都是蓝色
        } else {
            r = m;  // m右边都是红色
        }
    }

    return l; //最后一个<ans的元素，是蓝色
}

int main() {
    std::vector<int> array = {2,3,4,5,5,5,5,5,6}; // Sorted array
    int ans = 5; // The target value

    int index = binarySearch(array, ans);
    if (index != -1) {
        std::cout << "找到了值最后一个< " << ans << " 位置是: " << index
                  << " (值是: " << array[index] << ")" << std::endl;
    } else {
        std::cout << "找不到或者是输入有误" << ans << std::endl;
    }

    return 0;
}

#include <iostream>
#include <vector>
// 判断蓝色区域，反之就是红色区域
bool isBlue(const std::vector<int>& array, int m, int ans) {
  return array[m] <= ans;
}
// 目的是填色找到《红蓝边界》
int binarySearch(const std::vector<int>& array, int ans) {
    int l = -1, r = array.size();

    while (l + 1 != r) {
        int m = (l + r) / 2;

        if (isBlue(array, m, ans)) {
            l = m;  // m左边都是蓝色
        } else {
            r = m;  // m右边都是红色
        }
    }

    return r;
}

int main() {
    std::vector<int> array = {2,3,4,5,5,5,5,5,6}; // Sorted array
    int ans = 5; // The target value

    int index = binarySearch(array, ans);
    if (index != -1) {
        std::cout << "找到了第一个> " << ans << " 位置是: " << index
                  << " (值是: " << array[index] << ")" << std::endl;
    } else {
        std::cout << "找不到或者是输入有误" << ans << std::endl;
    }

    return 0;
}

#include <iostream>
#include <vector>
// 判断蓝色区域，反之就是红色区域
bool isBlue(const std::vector<int>& array, int m, int ans) {
  return array[m] <= ans;
}
// 目的是填色找到《红蓝边界》
int binarySearch(const std::vector<int>& array, int ans) {
    int l = -1, r = array.size();

    while (l + 1 != r) {
        int m = (l + r) / 2;

        if (isBlue(array, m, ans)) {
            l = m;  // m左边都是蓝色
        } else {
            r = m;  // m右边都是红色
        }
    }

    return l;
}

int main() {
    std::vector<int> array = {2,3,4,5,5,5,5,5,6}; // Sorted array
    int ans = 5; // The target value

    int index = binarySearch(array, ans);
    if (index != -1) {
        std::cout << "找到了最后一个<= " << ans << " 位置是: " << index
                  << " (值是: " << array[index] << ")" << std::endl;
    } else {
        std::cout << "找不到或者是输入有误" << ans << std::endl;
    }

    return 0;
}

#include <stdio.h>
#include <stdlib.h>

// 1.辅助结构体用于分块，这里是将整个数组分为三块
struct index
{
    // 定义块的结构
    int key;
    int start;
} newIndex[3];  // 定义结构体数组

int search(int key, int a[]);

int cmp(const void *a, const void *b)
{
    // 按照 key 进行排序
    return (*(struct index*)a).key > (*(struct index*)b).key ? 1 : -1;
}

int main()
{
    int i, j = -1, k, key;
    int a[] = {33, 42, 44, 38, 24, 48, 22, 12, 13, 8, 9, 20, 60, 58, 74, 49, 86, 53};

    // 确认模块的起始值和最大值
    for (i = 0; i < 3; i++)
    {
        newIndex[i].start = j + 1; // 确定每个块范围的起始值
        j += 6;
        newIndex[i].key = a[newIndex[i].start]; // 初始化最大值
        for (int k = newIndex[i].start; k <= j; k++)
        {
            if (newIndex[i].key < a[k])
            {
                newIndex[i].key = a[k];
            }
        }
    }

    // 2.对结构体按照 key 值进行排序，这里用的是快排
    qsort(newIndex, 3, sizeof(newIndex[0]), cmp);

    // 输入要查询的数，并调用函数进行查找
    printf("请输入您想要查找的数：\n");
    scanf("%d", &key);
    k = search(key, a);

    // 输出查找的结果
    if (k >= 0)
    {
        printf("查找成功！您要找的数在数组中的位置是：%d\n", k + 1);
    }
    else
    {
        printf("查找失败！您要找的数不在数组中。\n");
    }

    return 0;
}

int search(int key, int a[])
{
    int i = 0;

    // 3.二分查找确定在哪个块中
    while (i < 3 && key > newIndex[i].key)
    {
        i++;
    }

    if (i >= 3)
    {
        // 大于分得的块数，则返回-1
        return -1;
    }

    // 4.在找到的块中进行顺序查找
    int start = newIndex[i].start;
    int end = (i == 2) ? 17 : newIndex[i].start + 5;  // 确定块的结束位置

    while (start <= end && a[start] != key)
    {
        start++;
    }

    if (start > end)
    {
        return -1;
    }

    return start;
}

struct RA{
    int key;
    int value;
}

(4, A), (2, B), (3, C), (2, D), (4, E)

(2, B), (2, D), (3, C), (4, A), (4, E)

(2, D), (2, B), (3, C), (4, A), (4, E)

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#define N 10
// 1.交换操作
Swap(int *p1, int * p2)
{
    int tmp = *p1;
    *p1 = *p2;
    *p2 = tmp;
}
void Print(int *a)
{
    for (int i=0;i<N;i++)
    {
        printf("%d ",a[i]);
    }
}
// 2. 冒泡排序
void BubbleSort(int* a, int n)
{
    // 外部循环，维护排序区块和未排序区块
    for (int j=0;j<n;++j)
    {
        int size = 0;
        // 在未排序区块中，比较和交换直到最大值排列在排序完成的区块中
        for (int i=1;i<N-j;++i)
        {
            // 比较和交换
            if (a[i-1]>a[i])
            {
                Swap(&a[i-1],&a[i]);
                size =1;
            }
        }
        // 3.标记是否执行排序，未执行则提前跳出
        if (size==0)
        {
            break;
        }
    }
}
int main()
{
    int a[N] = {0};
    for (int i=0;i<N;++i)
    {
        a[i] = rand();
    }
    BubbleSort(a,N);
    Print(a);

    return 0;
}

void BubbleSort(ElemType A[],int n){
    for(int i = 0;i<n-1;i++){
        bool flag = false;
        // 这里改为正序也可以
        for(int j=n-1;j>i;j--){
            if(A[j-1]>A[j]) {
                swap(A[j-1],j[j]); //逆序交换
              flag = true;
            }
    }
         if(flag==false) return;
    }
}

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
//打印
void Print(int *a,int n)
{
    for (int i=0;i<n;++i)
    {
        printf("%d ",a[i]);
    }
}
//挖坑法
void QuickSort(int* a,int left,int right)//升序
{
    if (left < right)
    {
        int begin = left;
        int end = right;
        int pivot = begin;//记录坑位的下标
        int key = a[begin];//坑值
        while (begin < end)
        {
            //右边找小，放到左边
            while (begin < end && a[end] >= key)//与坑值比较
            {
                --end;
            }
            //小的放在左边的坑里，自己形成了新的坑位
            a[pivot] = a[end];
            pivot = end;
            //左边找大，放在右边
            while (begin < end && a[begin] <= key)//与坑值比较
            {
                ++begin;
            }
            //大的放在右边的坑里，自己形成了新的坑位
            a[pivot] = a[begin];
            pivot = begin;
        }
        //最后将坑值给到坑位
        a[pivot] = key;
        //[left,right]
        //[left,pivot-1]  [pivot+1,right]
        //左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归
        QuickSort(a, left, pivot - 1);
        QuickSort(a, pivot + 1, right);
    }
    else
    {
        return;
    }
}
int main()
{
    int a[10] = {0,9,5,6,3,2,1,7,8,4};
    //挖坑法
    QuickSort(a,0,sizeof(a)/sizeof(a[0])-1);
    //打印
    Print(a,sizeof(a) / sizeof(a[0]));
    return 0;
}

int begin = left;
int end = right;
//使用三数取中选“坑值”，用mid存储其下标
int mid = GetMidIndex(a, begin, end);
//将区间首值当作坑位
//坑值与首值交换，避免算法混乱
//一般我们会将区间首值作为坑值
Swap(&a[begin], &a[mid]);//传地址调用
//存储坑值
int key = a[begin];

int GetMidIndex(int *a,int left,int right)
{
    //二分
    int mid = (right - left) / 2;
    if (a[left]<a[mid])
    {
        if (a[left]<a[right])
        {
            if (a[mid]<a[right])
            {
                return mid;
            }
            else  //a[mid]>=a[right]
            {
                return right;
            }
        }
        else   //a[left]>=a[right]
        {
            return left;
        }
    }
    else  //a[left]>=a[mid]
    {
        if (a[mid]<a[right])
        {
            if (a[left]<a[right])
            {
                return left;
            }
            else  //a[left]>=a[right]
            {
                return right;
            }
        }
        else  //a[mid]>=a[right]
        {
            return mid;
        }
    }
}

//区间[left,right]
//左区间[left,pivot-1]  右区间[pivot+1,right]
//左子区间和右子区间有序，我们就有序了，如何让他们有序？分治递归
// 小区间优化
if (pivot - 1 - left > 10)//对当待处理数据大于于10的子序列进行快排递归排序
{
    //快排
    QuickSort(a,left,pivot-1);
}
else
{
    //采用直接插入排序，对当待处理数据低于10的子序列进行排序，避免递归
    InsertSort(a+left,pivot-1-left+1);//为什么最后要加1,例如：区间[0,9]实际上有10个数
}
if (right - (pivot + 1) > 10)
{
    QuickSort(a,pivot+1,right);
}
else
{
    InsertSort(a + pivot+1, right-(pivot+1)+1);
}

void QuickSort(int* a, int left, int right)
{
  if (left < right)
  {
    int begin = left;
    int end = right;
    //选坑位
    int mid = GetMidIndex(a, begin, end);//三数取中
    Swap(&a[begin], &a[mid]);
    int key = begin;
    while (begin < end)
    {
      while (begin < end && a[end] <= a[key])
        --end;
      while (begin < end && a[begin] >= a[key])
        ++begin;
      Swap(&a[begin], &a[end]);
    }
    Swap(&a[begin], &a[key]);
    //分治递归
    QuickSort(a, left, begin - 1);
    QuickSort(a, begin + 1, right);
  }
}

//左右指针法
void QuickSort(int* a, int left, int right)
{
  if (left < right)
  {
    //选坑位
    int mid = GetMidIndex(a, left,right);//三数取中
    Swap(&a[left], &a[mid]);
    int key = left;
    //初始化指向
    int prev = left, cur = left + 1;
    while (cur<=right)
    {
      if (a[cur] <= a[key])//&&++prev!=cur
      {
        ++prev;
        //避免无效操作
        if(cur!=prev)
        Swap(&a[prev],&a[cur]);
      }
      ++cur;
    }
    Swap(&a[key], &a[prev]);
    //分治递归
    QuickSort(a, left, prev - 1);
    QuickSort(a, prev + 1, right);
  }
}

void sort(int array[],int length){
    for(int i = 1;i < length;i++){
        //1.从无序牌堆中找到的牌
        int key = array[i];
        //2.变量指向的是有序牌堆
        int j = i-1;
     //3.从有序牌堆中找到适合key的位置插入,插入位置设置为j(已经排序完成)的前面
        while(j>=0 && array[j]>key){
            // 移动位置为插入腾出空间
            array[j+1] = array[j];
            j--;
        }
        //插入正确位置 - 完工
        array[j+1] = key;
    }
}

void InsertSort(ElemType A[], int n)
{
    int i, j, low, high, mid;

    // 1.i 从 2 开始，因为 A[1] 已经是自然有序的
    for (i = 2; i <= n; i++)
    {
        A[0] = A[i]; // 将 A[0] 作为哨兵变量，保存当前无序数据
        low = 1;
        high = i - 1;

        // 二分查找插入位置
        while (low <= high)
        {
            mid = (low + high) / 2;
            if (A[mid] > A[0])
                high = mid - 1; // 插入点在左侧
            else
                low = mid + 1;  // 插入点在右侧
        }

        // 2.移动元素，为插入留出空间。主要耗时间的部分
        for (j = i - 1; j >= low; --j)
        {
            A[j + 1] = A[j];
        }

        A[low] = A[0]; // 在 low 位置插入元素
    }
}

# include <stdio.h>

void shellsort(int arr[], int n) {
    int gap, i, j, temp;
  // 1.gap隔离整个数组，并逐步降低gap值
    for(gap = n/2; gap > 0; gap /= 2)
        // 对每一个分组进行插入操作，这一步不会改变整个数组！！
        for(i = gap; i < n; i++)
            for(j = i - gap; j >= 0 && arr[j] > arr[j+gap]; j -= gap) {
                temp = arr[j];
                arr[j] = arr[j+gap];
                arr[j+gap] = temp;
            }
}

int main() {
    int arr[] = {61, 109, 149, 111, 34, 2, 24, 119, 122, 27};
    int size = sizeof arr / sizeof arr[0];
    shellsort(arr, size);

    for(int i = 0; i < size; i++) {
        printf("i: %d\n", arr[i]);
    }
    return 0;
}

// 实现代码
void SelectSort(ElemType A[],int n){
    for(int i = 0;i<n-1;i++)
    {
        // 1.最小值位置 - 相对于未排序部分来说
        int min = i;
        for(int j = i+1;j<n;j++)
        {
            if(A[j]<A[min]) min = j; // 记录最小值位置
        }
        // 2.与最小值位置交换 - 作为已排序位置
        if(min!=i) swap(A[i],A[min]);
    }
}

#include <iostream>
#include <vector>
#include <algorithm>

// 构造大根堆
void adjustHeap(std::vector<int>& arr, int parent, int length) {
    int temp = arr[parent];  // 保存当前父节点的值
    int child = 2 * parent + 1;  // 左孩子节点索引

    while (child < length) {
        // 如果右孩子存在，且大于左孩子，选择右孩子
        if (child + 1 < length && arr[child] < arr[child + 1]) {
            child++;
        }

        // 如果子节点大于父节点，将子节点的值赋给父节点
        if (arr[child] > temp) {
            arr[parent] = arr[child];
            parent = child;
            child = 2 * parent + 1;  // 更新子节点，继续向下调整
        } else {
            break;  // 子树已经是大顶堆，退出循环
        }
    }
    arr[parent] = temp;  // 将原父节点的值放在最终位置
}

// 堆排序函数
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 1. 构建初始大顶堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, n);  // 从最后一个非叶子节点开始调整
    }

    // 2. 交换堆顶元素与末尾元素，调整堆
    for (int j = n - 1; j > 0; j--) {
        std::swap(arr[0], arr[j]);  // 将堆顶元素移到末尾，新树少一个节点
        adjustHeap(arr, 0, j);  // 调整剩余元素，重新堆化
    }
}

int main() {
    std::vector<int> arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    heapSort(arr);

    // 输出排序后的数组
    std::cout << "Sorted array: ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

// 调整小根堆
void adjustHeap(std::vector<int>& arr, int parent, int length) {
    int temp = arr[parent];  // 保存当前父节点的值
    int child = 2 * parent + 1;  // 左孩子节点索引

    while (child < length) {
        // 如果右孩子存在，且小于左孩子，选择右孩子
        if (child + 1 < length && arr[child] > arr[child + 1]) {
            child++;
        }

        // 如果子节点小于父节点，将子节点的值赋给父节点
        if (arr[child] < temp) {
            arr[parent] = arr[child];
            parent = child;
            child = 2 * parent + 1;  // 更新子节点，继续向下调整
        } else {
            break;  // 子树已经是小根堆，退出循环
        }
    }
    arr[parent] = temp;  // 将原父节点的值放在最终位置
}

// 堆排序函数（逆序）
void heapSort(std::vector<int>& arr) {
    int n = arr.size();

    // 1. 构建初始小根堆
    for (int i = n / 2 - 1; i >= 0; i--) {
        adjustHeap(arr, i, n);  // 从最后一个非叶子节点开始调整
    }

    // 2. 交换堆顶元素与末尾元素，调整堆
    for (int j = n - 1; j > 0; j--) {
        std::swap(arr[0], arr[j]);  // 将堆顶元素移到末尾
        adjustHeap(arr, 0, j);  // 调整剩余元素，重新构建小根堆
    }
}

int main() {
    std::vector<int> arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};
    heapSort(arr);

    // 输出逆序排序后的数组
    std::cout << "Sorted array (descending): ";
    for (int i : arr) {
        std::cout << i << " ";
    }
    std::cout << std::endl;

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

// 函数声明：归并排序和合并两个有序子数组
void mergeSort(vector<int>& arr, int left, int right, vector<int>& temp);
void merge(vector<int>& arr, int left, int mid, int right, vector<int>& temp);

int main() {
    // 初始化待排序数组
    vector<int> arr = {9, 8, 7, 6, 5, 4, 3, 2, 1};

    // 临时数组用于存放合并过程中的结果
    vector<int> temp(arr.size());

    // 对数组进行归并排序
    mergeSort(arr, 0, arr.size() - 1, temp);

    // 输出排序后的数组
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

// 1.归并排序函数
// 参数：arr - 待排序数组，left - 左边界，right - 右边界，temp - 临时数组
void mergeSort(vector<int>& arr, int left, int right, vector<int>& temp) {
    if (left < right) {
        // 防止(left + right)溢出，计算中间位置
        int mid = left + (right - left) / 2;

        // 递归对左右两部分进行归并排序
        mergeSort(arr, left, mid, temp);
        mergeSort(arr, mid + 1, right, temp);

        // 合并已排序的左右部分
        merge(arr, left, mid, right, temp);
    }
}

// 2.合并两个有序子数组
// 参数：arr - 待合并数组，left - 左边界，mid - 中间位置，right - 右边界，temp - 临时数组
void merge(vector<int>& arr, int left, int mid, int right, vector<int>& temp) {
    int i = left;      // 左半部分起始索引
    int j = mid + 1;   // 右半部分起始索引
    int t = 0;         // 临时数组索引

    // 合并两个子数组到临时数组
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[t++] = arr[i++];  // 左侧元素较小，存入temp
        } else {
            temp[t++] = arr[j++];  // 右侧元素较小，存入temp
        }
    }

    // 复制剩余的左半部分元素 - 如果有的话
    while (i <= mid) {
        temp[t++] = arr[i++];
    }

    // 复制剩余的右半部分元素 - 如果有的话
    while (j <= right) {
        temp[t++] = arr[j++];
    }

    // 将临时数组的元素拷贝回原数组
    t = 0;
    while (left <= right) {
        arr[left++] = temp[t++];
    }
}

#include <iostream>
#include <vector>
using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;

    // 找到数组中的最大值和最小值
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());

    // 创建计数数组，大小为最大值与最小值之间的差值 + 1
    vector<int> count(maxVal - minVal + 1, 0);

    // 统计每个元素的出现次数
    for (int num : arr) {
        count[num - minVal]++;
    }

    // 填回原数组
    int index = 0;
    for (int i = 0; i < count.size(); i++) {
        while (count[i] > 0) {
            arr[index++] = i + minVal;
            count[i]--;
        }
    }
}

int main() {
    vector<int> arr = {9, 4, 1, 7, 9, 1, 2, 0, 5, 8, 1, 4, 2};

    // 输出排序前的数组
    cout << "Before Sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // 进行计数排序
    countingSort(arr);

    // 输出排序后的数组
    cout << "After Sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;

    // 找到数组中的最大值和最小值
    int maxVal = *max_element(arr.begin(), arr.end());
    int minVal = *min_element(arr.begin(), arr.end());

    // 创建计数数组，大小为最大值与最小值之间的差值 + 1
    vector<int> count(maxVal - minVal + 1, 0);

    // 统计每个元素的出现次数
    for (int num : arr) {
        count[num - minVal]++;
    }

    // 计算前缀和，确定每个元素在最终排序中开始的位置
    for (int i = 1; i < count.size(); i++) {
        count[i] += count[i - 1];
    }

    // 创建一个临时数组存储排序结果
    vector<int> sortedArr(arr.size());

    // 从后往前遍历原数组，保证计数排序的稳定性
    for (int i = arr.size() - 1; i >= 0; i--) {
        int value = arr[i];
        int position = count[value - minVal] - 1;  // 根据前缀和确定位置
        sortedArr[position] = value;
        count[value - minVal]--;  // 更新计数数组
    }

    // 将排序后的结果拷贝回原数组
    arr = sortedArr;
}

int main() {
    vector<int> arr = {9, 4, 1, 7, 9, 1, 2, 0, 5, 8, 1, 4, 2};

    // 输出排序前的数组
    cout << "Before Sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    // 进行计数排序
    countingSort(arr);

    // 输出排序后的数组
    cout << "After Sorting: ";
    for (int num : arr) {
        cout << num << " ";
    }
    cout << endl;

    return 0;
}