首页 > 编程语言 >c语言 排序算法

c语言 排序算法

时间:2023-07-19 21:12:24浏览次数:45  
标签:sort arr 语言 start int len ++ 算法 排序

// sort_algorituhm.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include<algorithm>
using namespace std;
#define elemtype int



//冒泡排序法,组个遍历,大数往后,每次都是"完全遍历",从0开始
void sort_bubbling(elemtype *p, int sort_len) {
    elemtype temp = 0;
    int i, j;
    for(i=0; i < (sort_len-1);i++)
        for (j = 0; j < (sort_len - 1 - i); j++)
        { 
            if (p[j] > p[j + 1]) 
            {
                temp = p[j];
                p[j] = p[j + 1];
                p[j + 1] = temp;
            }

        }
}
//选择最大的值放在序列最后,重点:记录当前轮询周期下数列最值下标,找出后直接与数列尾端交换
//每次比较后,因为已经找出了最大值放到最后,下一次数列比较只到最值之前一个数即可
void sort_select(elemtype* p, int sort_len) {
    elemtype temp = p[0];
 //   elemtype Min_num = p[0];
    int index = 0;
    int i,j;

    for (j = 0; j < (sort_len-1); j++)
    {
        for (i = 0; i < (sort_len-j); i++)
        {
            if (p[i] > temp)
            {
                temp = p[i];
                index = i;
            } 
        }
        temp = p[sort_len-j-1];
        p[sort_len-j-1] = p[index];
        p[index] = temp;
        index = 0;
        temp = p[index];
    }

}
//插入排序法,重点:记录当前正在比较的数组元素下标,逐次之前的元素比较交换位置,直达插入完成
void sort_insert(elemtype* p, int sort_len)
{
    int i, j, key;
    for (i = 1; i < sort_len; i++) {
        key = p[i];
        j = i - 1;
        while ((j >= 0) && (p[j] > key)) {
            p[j + 1] = p[j];
            j--;
        }
        p[j + 1] = key;
    }
}
//希尔排序算法
void sort_shell(elemtype* p, int sort_len)
{
    int gap, i, j;
    int temp;
    for (gap = sort_len >> 1; gap > 0; gap >>= 1) //获得每次的分隔数
        for (i = gap; i < sort_len; i++)//按照分隔数,将数组分割为多组分别进行插入排列,这里的i++使得不同分组的前几个数在下一个gap到来之前并行分别排序
        {
            temp = p[i];    //插入排序法中,正在比较的数组元素
            //按指定间隔遍历链表,寻找插入位置,因为for循环开始时,j = i - gap 
            //使得分的小组数列从建立起就是升序排列,即插入排序法
            for (j = i - gap; j >= 0 && p[j] > temp; j -= gap)
                p[j + gap] = p[j];
            p[j + gap] = temp;     
        }
}
elemtype min(elemtype x, elemtype y)
{
    return y > x ? x : y;
}
//归并排序 ,迭代法,将数组向下分割为单个元素,再对单个元素进行多次归并
void merge_sort(int arr[], int len) {
    int* a = arr;
    int* b = (int*)malloc(len * sizeof(int));
    int seg, start;
    for (seg = 1; seg < len; seg += seg) {
        for (start = 0; start < len; start += seg * 2) {
            //第一次归并,将数组排序为2个一组的(尾部单独算),升序排列的数列
            //第二次归并,将排序好的2个一组的数列,小端比小端开始,依次比较组合为4个一组的(尾部单独算),升序排列的数组
            //                           .............
            //第n次归并,将len/2长度的两个排序好的数组,小端开始,,依次比较完成归并
            int low = start, mid = min(start + seg, len), high = min(start + seg * 2, len);
            int k = low;
            int start1 = low, end1 = mid;
            int start2 = mid, end2 = high;//start1,start2为每次比较的有序数组的首地址
            //下面三句完成两个升序数组的升序合并
            while (start1 < end1 && start2 < end2)
                b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
            while (start1 < end1)   //因为是已经排序好的数列,小值已经比另一数列最大值大了,后面直接复制就行
                b[k++] = a[start1++];
            while (start2 < end2)
                b[k++] = a[start2++];
        }
        int* temp = a;
        a = b;
        b = temp;
    }
    if (a != arr) {
        int i;
        for (i = 0; i < len; i++)
            b[i] = a[i];
        b = a;
    }
    free(b);
}
//归并排序 递归法,将数组向下分割为单个元素,再对单个元素进行多次归并
void sort_merge_recursive(int* a, int* b,int start,int end) {
    if (start >= (end-1)) return; //start指向最后是,表示当前递归遍历完毕,开始返回
    int seg = (end - start)/2;
    int low = start, mid = min(start + seg, end), high = end;
    int start1 = low, end1 = mid;
    int start2 = mid, end2 = high;//start1,start2为每次比较的有序数组的首地址
    sort_merge_recursive(a, b, start1, end1);
    sort_merge_recursive(a, b, start2, end2);
    int k = start;
    int i = 0;
    //下面三句完成两个升序数组的升序合并
    while (start1 < end1 && start2 < end2)
        b[k++] = a[start1] < a[start2] ? a[start1++] : a[start2++];
    while (start1 < end1)   //因为是已经排序好的数列,小值已经比另一数列最大值大了,后面直接复制就行
        b[k++] = a[start1++];
    while (start2 < end2)
        b[k++] = a[start2++];
    for (i = start;i<end;i++)
    {
        a[i] = b[i];
    }
}
void sort_My_merge_recursive(int arr[], int len)
{
    int* b = (int*)malloc(len * sizeof(int));
    sort_merge_recursive(arr, b,0,len);
    free(b);
}

//快速排序,迭代法
typedef struct _Range {//用于记录当前分区起点与终点
    int start, end;
}Range;
Range new_Range(int s, int e)
{
    Range r = {0,0};
    r.start = s;
    r.end = e;
    return r;
}
void swap(int *x,int *y) {
    int t = *x;
    *x = *y;
    *y = t;
}
void sort_quick(int arr[], const int len)
{
    if (len <= 0) return;   // 避免len等於負值時引發段錯誤(Segment Fault)
    Range* r = (Range*)malloc(sizeof(Range) * len);           // r[]模擬列表,p為數量,r[p++]為push,r[--p]為pop且取得元素
    if (r == NULL) return;
    int ptop = 0;
    r[ptop++] = new_Range(0, len - 1);
    while (ptop)
    {
        Range range = r[--ptop];
        if (range.start >= range.end) continue;
        int mid = arr[(range.start + range.end) / 2];// 選取中間點為基準點
        int left = range.start, right = range.end;
        do
        {
            while (arr[left] < mid) left++;
            while (arr[right] > mid) right--;
            if (left <= right)
            {
                swap(&arr[left],&arr[right]);
                left++;
                right--; //移动指针以继续
            }
        } while (left <= right);
        if(range.start<right) r[ptop++] = new_Range(range.start, right);
        if(range.end> left) r[ptop++] = new_Range(left, range.end);        
    }
}
//快速排序,递归法
void sort_quick_rcursive(int arr[],int start,int end)
{
    if (start >= end)return;
    int left = start, right = end;
    int mid = arr[(start + end) / 2];
    do
    {
        while (arr[left] < mid) left++;
        while (arr[right] > mid) right--;
        if (left <= right)
        {
            swap(&arr[left], &arr[right]);
            left++;
            right--; //移动指针以继续
        }
    } while (left <= right);
    sort_quick_rcursive(arr, start, right);
    sort_quick_rcursive(arr, left, end);
}
void sort_My_quick_rcursive(int arr[], int len)
{
    sort_quick_rcursive(arr, 0, len - 1);
}
//堆排序
void my_heapify(int arr[],int dad_index,int len)//最大堆生成
{
    int son = dad_index * 2 + 1;
    while (len > son)//使用while遍历挂在该父节点之后所有节点,避免因为数值调换引起的最大堆出错
    {
        if ((son + 1) < len  && arr[son] < arr[son+1])//获取子节点中大值
        {
            son++;
        }
        if (arr[dad_index] >= arr[son])
            return;
        swap(&arr[dad_index],&arr[son]);
        dad_index = son;                            
        //父亲下标指向与之调换的儿子下标,进行以该儿子下标为父亲节点的最大堆生成,避免因为数值调换引起的最大堆出错(父节点值不是最大)
        son = dad_index * 2 + 1;
    }
}
void sort_heap(int arr[], int len)
{
    int i, j;
    for (i = len / 2 + 1; i >= 0; i--)
        my_heapify(arr, i, len);//建立最大堆
    for (i = len - 1; i > 0;i--)//在最大堆上操作
    {
        swap(&arr[0],&arr[i]);//将当前最低节点(较上层较小)与max值交换
        my_heapify(arr, 0,i-1);//从根节点0开始,交换后的小值不断向下沉淀,大值不断上浮,i-1是为排除有序数列
    }
}
//计数排序,用于0~99内计数
void counting_sort(int* ini_arr, int* sorted_arr, int n) {
    int* count_arr = (int*)malloc(sizeof(int) * 100);
    int i, j, k;
    for (k = 0; k < 100; k++)   //初始化count_arr,每个数据重复计数初始为0
        count_arr[k] = 0;
    for (i = 0; i < n; i++)
        count_arr[ini_arr[i]]++;//直接在数据范围内对重复数据进行重复计数
    for (k = 1; k < 100; k++)//
        count_arr[k] += count_arr[k - 1];//向后叠加计数值,后一个值储存全面所有值数量和,间接获得了每个值排序后的序号
    for (j = n; j > 0; j--)
        sorted_arr[--count_arr[ini_arr[j - 1]]] = ini_arr[j - 1];
    //填充每个数据到排序后数字应该到的位置
    //count_arr[ini_arr[j - 1]]:当前数据应在地址,同时地址减一,应对数据重复情况,向后填充
    free(count_arr);
}
//基数排序
void sort_radix(int* p, int len)
{
    int* sorted_arr = (int*)malloc(sizeof(int) * len);
    int BASE = 10;//取余10
    int exp = 1;//从1开始除,num/exp%BASE, 处理完一轮exp = exp*BASE 依次获得个位、十位...
    int max_num = p[0], i;
    for (i = 1; i < len; i++)//获取最大值,判断循环结束条件
    {
        if (p[i] > max_num) max_num = p[i];
    }
    while (max_num / exp >0) 
    {
        int count_arr[10] = {0};
        for (i = 0; i < len; i++)
        {
            count_arr[p[i] / exp % BASE]++;//直接在数据范围内对重复数据进行重复计数
        }
        for (i = 1; i < len; i++)
        {
            count_arr[i] += count_arr[i - 1];//向后叠加计数值,后一个值储存全面所有值数量和,间接获得了每个值排序后的序号
        }
        for (i = len-1; i >= 0; i--)
        {
            sorted_arr[--count_arr[p[i] / exp % BASE]] = p[i];
        }
        for (i = 0; i < len; i++)
        {
            p[i] = sorted_arr[i];
        }
        exp = exp * BASE;
    }
}

int main()
{
    elemtype arr[] = { 12,32,34,13,64,234,7,2,5652,34 };
    int loop = 0;
    int n = 10;
    sort_bubbling(arr,n);
for (; loop < n; loop++) { printf("%d ", arr[loop]); } printf("\n"); system("pause"); }

  

标签:sort,arr,语言,start,int,len,++,算法,排序
From: https://www.cnblogs.com/ysyyrps-hhl/p/17566749.html

相关文章

  • 初学C语言day03--数据类型及循环分支语句
    一、数据类型为什么要对数据进行分类?1、现实中的数据就是自带类别属性的2、对数据进行分类可以节约内存存储空间、提高运行速度存储空间的单位:Bit比特存储一个二进制位,只能存储0或者1,计算机存储数据的最小单位Byte字节存储八个二进制位,计算机存储数据的基本单位Kb102......
  • c语言学习7
    函数传参1、函数中定义的变量属于该函数,出了该函数就不能再被别的函数直接使用2、实参与形参之间是以赋值的方式进行传递数据的,并且是单向值传递3、return语句其实是把返回值数据放入公共区域内存中(调用者和被调用者都可以访问),调用者会从该区域获取返回值;如果不写return语句,......
  • 跟着Environmental Research学作图:R语言ggplot2堆积柱形图叠加折线图(1)
    跟着EnvironmentalResearch学作图:R语言ggplot2堆积柱形图叠加折线图(1)简介在环境研究领域,数据可视化是非常重要的工具,可以帮助我们更好地理解和解释复杂的数据。本篇文章将教会你如何使用R语言中的ggplot2包创建堆积柱形图叠加折线图,以展示不同组别之间的关系和趋势。环境设......
  • 多重检验校正R语言
    多重检验校正R语言在统计学和数据分析中,多重检验校正是一个非常重要的概念。当我们对大量的假设进行检验时,可能会出现错误的阳性结果(即拒绝了真实的假设)。为了减少这种错误,我们需要进行多重检验校正。什么是多重检验校正?多重检验校正是一种统计学方法,用于控制因进行多次检验而导......
  • 拓扑排序
    定义:对一个有向图构造拓扑序列,排序类似流程图那样按先干什么后干什么这样排序拿大学教学安排举个例子(图来自oiwiki)先不要考虑操作系统到数据结构那条蓝线。那么我们要先学程序设计才能学习后面的算法语言,离散数学等等。那么在拓扑序列中,程序设计就要在算法语言,离散数学......
  • 对UION结果进行排序 MYSQL
    对UION结果进行排序MYSQL在MySQL中,可以使用UNION操作符将多个SELECT语句的结果合并成一个结果集。但是,UNION操作符的结果默认是按照表达式顺序进行排序的。如果我们想要对UNION的结果进行排序,可以使用子查询或者别名的方式来实现。子查询排序子查询是将一个SELECT语句嵌套在另......
  • 单位根检验:ADF检验R语言
    单位根检验:ADF检验R语言介绍单位根检验是时间序列分析中常用的方法之一,用于确定一个时间序列是否具有单位根。单位根表示一个时间序列是非平稳的,即它的均值和方差随时间的推移而变化。平稳时间序列具有稳定的均值和方差,使得统计推断更加可靠。ADF(AugmentedDickey-Fuller)检验......
  • 在C语言中嵌入python,未定义的符号。PyExc_ImportError
    本文是小编为大家收集整理的关于在C语言中嵌入python,未定义的符号。PyExc_ImportError的处理/解决方法,可以参考本文帮助大家快速定位并解决问题,中文翻译不准确的可切换到English标签页查看源文。中文English问题描述点击免费获取 CRMEB开源商城系统源码 ......
  • 2023.7.19 周三:冒泡排序
    1importjava.sql.SQLOutput;2importjava.util.Arrays;3importjava.util.Scanner;4//冒泡排序5publicclasstest{6publicstaticvoidmain(String[]args){7int[]a={5,4,6,8,9,1,7,2,3};8intarray[]=sort(a);9S......
  • C语言内嵌Python import时提示undefined symbol错误及解决
    项目切gcc4.6版本时,C语言内嵌了python,运行bin文件import时出现importError错误,提示python-2.7.11/lib/python2.7/lib-dynload/_collections.so:undefinedsymbol:_Py_ZeroStruct. 基本代码如下: #include<Python.h>#include<stdio.h>#include<stdlib.h> intmain(......