登录
目录
当前位置： 首页 > 文档资料 > C 语言程序设计 >

排序与查找算法

优质
小牛编辑
147浏览
2023-12-01

排序

堆排序

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

void show(int * arr, int n)
{
    for (int i = 0; i < n; ++i)
    {
        printf("%4d", arr[i]);
    }
    printf("\n");
}

//01.堆排序:
//  1.用途:获取极值+极值排序
//  2.分类:小顶锥(极小值)+大顶锥(极大值)
//02.堆排序详解:
//  1.从二叉树状结构的底部开始,逐步往上层进行比较!
//  2.这里面儿的每一句代码都有含义!
//03.堆排序求极值!
void maximum(int * arr, int size)//arr:int类型的一维数组作为函数形参将会退化为(int *)类型的指针
{
    for (int i = size - 1; i > 0; --i)//size-1:表示模拟从二叉树最底层最右边的一个元素开始进行遍历;i>0:表示空余数组首元素位置留作为登顶元素+(+1:只有一个元素无需极值!)
    {
        int child = i;//从最后一个元素-->第一个元素:进行遍历-->空余第0号元素用于登顶
        int parent = i / 2;//求取父节点索引
        if (i < size - 1 && arr[i] < arr[i + 1])//i<size-1:保证绝对存在右索引;arr[i]<arr[i+1]:表示左元素一定小于右元素
        {
            ++child;//让左元素跳至到右元素
        }//否则:左元素大于右元素-->推出最大子元素
        if (arr[child] > arr[parent])//比较最大子元素和父元素:如果子元素大于父元素,则进行元素交换,否则保持原样!
        {
            int temp = arr[child];
            arr[child] = arr[parent];
            arr[parent] = temp;
        }
    }
}

//04.堆排序极值排序!
//  起始位置不变+长度不断减少
void heapSort1(int * arr, int size)
{
    for (int i = size; i > 1; --i)//i>1:排除只有一个元素无需排序!
    {
        maximum(arr, i);
        int temp = arr[0];//极值交换
        arr[0] = arr[i - 1];
        arr[i - 1] = temp;
    }
}

//05.堆排序极值排序!
//  起始位置后移+长度不断减少
//注:要想修改数组当中的元素,就得传递数组当中元素的地址!
void heapSort2(int * arr, int size)
{
    for (int i = 0; i < size; ++i)
    {
        maximum(arr + i, size - i);//得到一个极值,然后就进行极值位移动:分多次进行极值的求取操作!
    }
}

int main01(void)
{
    int arr[10] = { 10, 13, 120, 12, 30, 114, 50, 19, 60, 29 };
    show(arr, 10);

    //01.堆排序求极值
    //maximum(arr, 10);
    //show(arr, 10);

    //02.堆排序极值排序!
    //heapSort1(arr, 10);
    heapSort2(arr, 10);
    show(arr, 10);

    system("pause");
}

快速排序

#include <stdio.h>

//快速排序
void QuickSort(int *arr, int left, int right)
{
    //如果数组左边的索引大于或等于右边索引，说明该序列整理完毕
    if (left >= right)
        return;
    int i = left;
    int j = right;
    int key = *(arr + i);            //使用key来保存作为键值的数据
    //本轮排序开始，当i=j时本轮排序结束，将值赋给arr[i]
    while (i < j)
    {
        while ((i < j) && (key <= arr[j]))
            j--;                    //不符合条件，继续向前寻找
        *(arr + i) = *(arr + j);
        //从前往后找一个大于当前键值的数据
        while ((i < j) && (key >= arr[i]))
            i++;                    //不符合条件，继续向后寻找
        //直到i<j不成立时while循环结束，进行赋值
        *(arr + j) = *(arr + i);
    }
    *(arr + i) = key;
    QuickSort(arr, left, i - 1);
    QuickSort(arr, i + 1, right);
}
//输出数组
void print(int *arr, int n)
{
    for (int i = 0; i < n; i++)
        printf("%d ", *(arr + i));
}

int main()
{
    int arr[10] = { 3, 5, 6, 7, 2, 8, 9, 1, 0, 4 };
    printf("原数组：\n");
    print(arr, 10);
    QuickSort(arr, 0, 9);            //排序算法
    printf("\n排序后的数组：\n");
    print(arr, 10);                    //输出数组
    return 0;
}

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

#define EN 1024
int flag = 0;
char * filePath = "E:\\Resource\\TestData\\BigDB\\Test.txt";

//数组赋值
int intArr[EN];
void initArr(int intArr[EN])
{
    //time_t te;
    //unsigned int seed = (unsigned int)(time(&te));
    //srand(seed);
    srand((unsigned int)(time(NULL)));
    for (int i = 0; i < EN; ++i)
    {
        intArr[i] = rand() % EN + 1;
    }
}

//数组显示
void showArr(int intArr[EN])
{
    for (int i = 0; i < EN; ++i)
    {
        printf("%4d \n", intArr[i]);
    }
}

//冒泡排序
void bubbleSortArr(int intArr[EN])
{
    for (int i = 0; i < EN - 1; ++i)
    {
        for (int j = 0; j < EN - 1 - i; ++j)
        {
            if (intArr[j] > intArr[j + 1])
            {
                intArr[j] = intArr[j] ^ intArr[j + 1];
                intArr[j + 1] = intArr[j] ^ intArr[j + 1];
                intArr[j] = intArr[j] ^ intArr[j + 1];
            }
        }
    }
}

//选择排序
void selectSortArr(int intArr[EN])
{
    int minIndex = 0;
    int minNum = 0;
    for (int i = 0; i < EN - 1; ++i)
    {
        minIndex = i;
        minNum = intArr[i];
        for (int j = i + 1; j < EN; ++j)
        {
            if (minNum > intArr[j])
            {
                minIndex = j;
                minNum = intArr[j];
            }
        }
        if (i != minIndex)
        {
            intArr[i] = intArr[i] ^ intArr[minIndex];
            intArr[minIndex] = intArr[i] ^ intArr[minIndex];
            intArr[i] = intArr[i] ^ intArr[minIndex];
        }
    }
}

//插入排序
void insertSortArr(int intArr[EN])
{
    int currentIndex = 0;
    int currentValue = 0;
    for (int i = 1; i < EN; ++i)
    {
        currentIndex = i;
        currentValue = intArr[currentIndex];
        while (0 < currentIndex && intArr[currentIndex - 1] > currentValue)
        {
            intArr[currentIndex] = intArr[currentIndex - 1];
            --currentIndex;
        }
        intArr[currentIndex] = currentValue;
    }
}

//二分查找
int binarySearch(int intArr[EN], int value)
{
    int minIndex = 0;
    int midIndex = 0;
    int maxIndex = EN - 1;
    while (minIndex <= maxIndex)
    {
        midIndex = (minIndex + maxIndex) / 2;
        if (value == intArr[midIndex])
        {
            return midIndex;
        }
        else if (value < intArr[midIndex])
        {
            maxIndex = midIndex - 1;
        }
        else
        {
            minIndex = midIndex + 1;
        }
    }
    return -1;
}

//拉格朗日查找
int lagrangeSearch(int intArr[EN], int value)
{
    int minIndex = 0;
    int ratioIndex = 0;
    int maxIndex = EN - 1;
    while (minIndex <= maxIndex)
    {
        //midIndex = minIndex + (maxIndex - minIndex) / 2;
        ratioIndex = minIndex + (maxIndex - minIndex)*(value - intArr[minIndex]) / (intArr[maxIndex] - intArr[minIndex]);
        if (value == intArr[ratioIndex])
        {
            return ratioIndex;
        }
        else if (value < intArr[ratioIndex])
        {
            maxIndex = ratioIndex - 1;
        }
        else
        {
            minIndex = ratioIndex + 1;
        }
    }
    return -1;
}

int main01(void)
{
    initArr(intArr);
    showArr(intArr);

    insertSortArr(intArr);
    printf("binSearch Index = %d \n", binarySearch(intArr, 880));
    printf("lagrangeSearch index = %d \n", lagrangeSearch(intArr, 880));

    system("pause");
}

查找

二分查找

void ShowArray(int a[], int n)  
{  
       for (int i = 0; i < n; i++)  
       {  
              printf("%d,", a[i]);  
       }  
       printf("\n");  
}  

void Sort(int a[], int n) // 冒泡排序
{  
       for (int i = 0; i < n - 1; i++)  
       {  
              for (int j = 0; j < n - 1 - i; j++)  
              {  
                     if (a[j]>a[j+1])  
                     {  
                            int temp = a[j];  
                            a[j] = a[j + 1];  
                            a[j + 1] = temp;  
                     }  
              }  
       }  
}  

//num为所要查找的数据,返回数组下标  
int SearchFor(int a[], int n, int num)  
{  
       for (int low = 0, high = n - 1, mid = (low + high) / 2; 
            low <= high; mid=(low+high)/2)  
       {  
              printf("\n开始查找%d,%d,%d", low, high, mid);  
              if (a[mid] == num)  
              {  
                     return mid;  
              }  
              else   if (a[mid]>num)  
              {  
                     high = mid - 1;  
              }  
              else  
              {  
                     low = mid + 1;  
              }  
       }  
}  

int BinarySearch(int a[], int n, int num)  
{  
       int low = 0;  
       int high = n - 1;  
       int mid = (low + high) / 2;  
       while (low <= high)  
       {  
              printf("\n开始查找%d,%d,%d", low, high, mid);  
              if (a[mid] == num)  
              {  
                     return mid;  
              }  
              else   if (a[mid]>num)  
              {  
                     high = mid - 1;  
                     mid = (low + high) / 2;  
              }  
              else  
              {  
                     low = mid + 1;  
                     mid = (low + high) / 2;  
              }  
       }  
}  

void main()  
{  
       int a[50] = { 0 };  
       time_t ts;  
       srand((unsigned int)time(&ts));//随机数种子  
       for (int i = 0; i < 50; i++)  
       {  
              a[i] = rand() % 100;  
              //printf("%d,", a[i]);  
       }  

       Sort(a, 50);  
       ShowArray(a, 50);  

       int num;  
       printf("plesae input your find num:");  
       scanf("%d", &num);  //扫描数据接收输入  
       //int ret = SearchFor(a, 50, num);  
       int ret = BinarySearch(a, 50, num);  
       if (ret == -1)  
       {  
              printf("not find\n");  
       }  
       else  
       {  
              printf("find [%d]\n", a[ret]);  
       }  
       system("pause");  
}
免责声明： 以上内容版权归原作者所有，如有侵犯您的原创版权请告知，我们将尽快删除相关内容。感谢每一位辛勤著写的作者，感谢每一位的分享。
@小牛知识库 xnip.cn